Let $(a_n)$ be the A001921 sequence

$$ a_0 = 0,\ a_1 = 7, \quad a_{n+2} = 14a_{n+1} - a_n + 6. $$

Let $(b_k)$ be the (almost)"tower-of-squares" sequence defined by

$$ b_0=2, \quad b_{k+1}=2b_k^2-1 $$

Is it true that $a_{2^kn+2^{k-1}-1}$ is always divisible by $b_k$, for any $k,n\geq 0$ ?

I have checked this up to $k=6$. For example :

  • $a_{2n}$ is always divisible by $b_0=2$.

  • $a_{4n+1}$ is always divisible by $b_1=7$.

  • $a_{8n+3}$ is always divisible by $b_2=97$.

  • Etc. Up to : $a_{128n+65}$ is always divisible by $b_6=2011930833870518011412817828051050497$.

    This is a cross-post from a MSE question.

  • $\begingroup$ Does any enlightenment occur when you write the a-recurrence in matrix form? Gerhard "Or Maybe Tilt Your Head" Paseman, 2014.11.06 $\endgroup$ – Gerhard Paseman Nov 6 '14 at 18:28
  • $\begingroup$ @GerhardPaseman When I write $X_n=(1,a_n,a_{n+1})$ and $X_{n+1}=\left(\begin{array}{ccc} 1 & 0 & 0 \\ 0 & 0 & 1 \\ 6 & -1 & 14 \end{array}\right)X_n$, no flash occurs in my brain. But maybe I am being blind on this one … $\endgroup$ – Ewan Delanoy Nov 6 '14 at 19:46
  • $\begingroup$ OK. I was thinking 2x2 matrices with a' = (6 0) + Aa, and then calling this operation Va and trying V iterated to a high power. I haven't followed it up though. Gerhard "Maybe Smaller Will Be Better" Paseman, 2014.11.06 $\endgroup$ – Gerhard Paseman Nov 6 '14 at 19:56
  • $\begingroup$ @GerhardPaseman The closed-form formula for $a_n$ is of the form $-\frac{1}{2}+c(7- 4\sqrt{3})^n+d(7+ 4\sqrt{3})^n$. Not very helpful for integer divisibility properties it seems $\endgroup$ – Ewan Delanoy Nov 6 '14 at 20:00
  • 1
    $\begingroup$ Some thoughts that can be helpful: 1) you perhaps prefer to consider the sequence $d_n=2a_n+1$, as it satisfies a homogeneous linear recurrence $d_{n+1}=14d_n-d_{n-1}$ -- and prove the congruence to 1 modulo the sequence $c_n=2b_n$ ; 2) for the latter, the recurrence relation is also simplified: $c_{n+1}=c_n^2-2$. 3) It would be natural to expect that $A^{2^n}=id$ mod $c_n$, where $A=\left(\begin{smallmatrix} 14 & -1 \\ 1 & 0 \end{smallmatrix}\right) $ is the corresponding transition matrix. $\endgroup$ – Victor Kleptsyn Nov 6 '14 at 20:00

The elements of your sequence are $$a_n=\left(\frac{\alpha^n-\beta^n}{2\sqrt{3}}\right)\left(\frac{\alpha^{n+1}+\beta^{n+1}}{2}\right)$$ where $\alpha=2+\sqrt{3}$ and $\beta=2-\sqrt{3}$. Notice that both factors are integers. We can also compute that $$b_n=\frac{\alpha^{2^n}+\beta^{2^n}}{2}.$$ Now your statement that $b_k$ always divides $a_{2^{k+1}n+2^k-1}$ follows from the fact that $\frac{\alpha^{2^k}+\beta^{2^k}}{2}$ divides $\frac{\alpha^{2^k(2n+1)}+\beta^{2^k(2n+1)}}{2}$, which is very easy to check (the ratio is a polynomial in $\alpha, \beta$ and symmetric in both).

| cite | improve this answer | |
  • $\begingroup$ Very nice. May I ask how you discovered the factorization of $a_n$ ? Did you use some sort of systematic method ? $\endgroup$ – Ewan Delanoy Nov 7 '14 at 7:32
  • $\begingroup$ I think I see already : the initial recurrence has eigenvalues that happen to be fourth powers. So, one looks for factor sequences that satisfy a reccurence whose eigenvalues are the fourth roots of the initial roots. $\endgroup$ – Ewan Delanoy Nov 7 '14 at 7:36
  • $\begingroup$ By the factorization a_n is composite, except for finite exceptions? $\endgroup$ – joro Nov 7 '14 at 8:57
  • $\begingroup$ @joro: indeed both factors diverge, and satisfy a linear recurrence $\endgroup$ – Pietro Majer Nov 7 '14 at 9:06
  • $\begingroup$ @PietroMajer Indeed. so a_n is the product of two lower order recurrences. $\endgroup$ – joro Nov 7 '14 at 9:17

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.