# Tower-of-squares sequence divides linear recurrent A001921 sequence?

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.

• Does any enlightenment occur when you write the a-recurrence in matrix form? Gerhard "Or Maybe Tilt Your Head" Paseman, 2014.11.06 – Gerhard Paseman Nov 6 '14 at 18:28
• @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 … – Ewan Delanoy Nov 6 '14 at 19:46
• 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 – Gerhard Paseman Nov 6 '14 at 19:56
• @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 – Ewan Delanoy Nov 6 '14 at 20:00
• 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. – 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).
• Very nice. May I ask how you discovered the factorization of $a_n$ ? Did you use some sort of systematic method ? – Ewan Delanoy Nov 7 '14 at 7:32