Show that the elements of the sequence are divisible by $2^n$

Question

I am trying to prove the following:

Consider the sequence defined by $A_{n+2}=6A_{n+1}+2A_n, A_0=2, A_1=6$. Show that $2^n|A_{2n-1}$ but $2^{n+1}\nmid A_{2n-1}$.

The first terms of this sequence are 2, 6, 40, 252, 1592, 10056, 63520. In fact, the maximal exponent of $2$ that divides $A_n$ seems to follow a pattern with a period of 4:

1, 1, 3, 2, 3, 3, 5, 4, 5, 5, 7, 6...

But I haven't been able to prove this.

Answer 1

Using induction, it's easy to prove that $A_n=(3+\sqrt{11})^n+(3-\sqrt{11})^n$ (roots of the characteristic polynomial of the corresponding recurrence $t^2-6t-2$ are $3\pm\sqrt{11}$). Define $$ B_n:=A_{2n+1}~\text{for}~n\geq 0. $$ Then, $$ B_n=(3+\sqrt{11})^{2n+1}+(3-\sqrt{11})^{2n+1}. $$ It's easy to check that $B_0=6$, $B_1=252$ and $$ B_{n+2}=40B_{n+1}-4B_n $$ (because $(3\pm\sqrt{11})^2=20\pm 6\sqrt{11}$ are roots of $t^2-40t+4$).

Now, define $C_n:=\frac{B_n}{2^{n+1}}$. Then, we can rewrite previous equality as $$ 2^{n+3}C_{n+2}=40\cdot 2^{n+2}C_{n+1}-4\cdot 2^{n+1} C_n. $$ or $$ C_{n+2}=20C_{n+1}-C_n. $$ Also, $C_0=3$ and $C_1=63$. It's clear from the recurrence relation for $\{C_n\}$ that all $C_n$ are integers. Moreover, each $C_n$ is odd (because $C_0,C_1$ are odd and from the recurrence relation: $C_{n+2}\equiv C_n\pmod 2$).

Therefore, $A_{2n+1}=2^{n+1}\cdot C_n$ for some odd $C_n$. Thus, $2^{n+1}\mid A_{2n+1}$ and $2^{n+2}\not\mid A_{2n+1}$, as desired.

Answer 2

By repeatedly applying the recurrence relation $k$ times we obtain following relation with only odd indexed terms, except for the last one: $$ A_{2n-1}=2A_{2n-3}+9\sum_{i=0}^{k-1} 2^{i+2}A_{2n-3-2i}+6\cdot2^{k}A_{2n-2k-2} $$ for $k \leq n-1$ (you can prove this result by induction). Now if $k=n-1$, the last term has $A_0=2$, and so $$ A_{2n-1}=2A_{2n-3}+9\sum_{i=0}^{n-2} 2^{i+2}A_{2n-3-2i}+6\cdot2^{n}. $$ The claim $2^{n} \mid A_{2n-1}$ and $2^{n+1} \nmid A_{2n-1}$ now follows as an application of strong induction. Base case $n=1$ is trivial. For induction step, let's assume that $A_{2r-1}=2^{r}d_r$ where $2 \nmid d_r$ for $r=1,\dots,n-1$. Then \begin{align} A_{2n-1} &=2(2^{n-1}d_{n-1})+9\sum_{i=0}^{n-2} 2^{i+2}(2^{n-1-i}d_{n-1-i})+6\cdot2^{n}\\ &=2^{n}d_{n-1}+9\sum_{i=0}^{n-2} 2^{n+1}d_{n-2-i}+6\cdot2^{n}\\ &=2^{n}\left(d_{n-1}+18\sum_{i=0}^{n-2} d_{n-2-i}+6\right). \end{align} Since $d_{n-1}$ is odd, expression in the brackets is odd and the claim follows.

Answer 3

We can't do induction on just the odd terms without generalizing something about the even terms.

Let's try a few terms and see why this seems to occur...and to see what else we will need to assure this will always be true:

$2^1|a_{2*1-1} =a_1 = 6$ because ... it does and $2^2\not \mid a_1 = 6$ because ... it doesn't.

$a_{2*2 -1} = a_3 = 6a_1 + 2a_2$. Now $2^2|6a_1$ because $2^1|a_1$ and $2^3\not \mid 2a_1$ because $2^2\not \mid a_1$.

So $2^2|6a_1 + 2a_2$ if and only if $4|2a_2$ or if $2|a_2$ . But if $2|a_2$ but $4\not \mid a_2$ we would have $a_1 = 2odd_1$ and $a_2=2odd_2$ for twe odd integers $odd_1$ and $odd_2$, and $a_3=6a_1 + 2a_2=3*4odd_1 + 4odd_2 = 4(3odd_1+odd_2)$ which would be divisible by $8$ because $3odd_1 + odd_2$ would be even.

So for this to be true we need $2^2|a_2$. And as $a_2 = 6a_0 + 2a_1 = 6*2+2*6=24$ we do have $4|a_2$.

But for our induction step to work we will always need $2^{k+1}|a_{2k}$.

So that's what we are going to need to have induction work:

$P(n) =2^n\mid a_{2n-1}$ but $2^{n+1}\not \mid a_{2n-1}$ and $2^{n+1}\mid a_{2n}$.

Base case: $n = 1$.

This is true for $k=1$ and $2|a_1=6$ but $4\not \mid a_1=6$ and $4|a_2 = 24$.

Induction case: Assume true for $n = k$. Show is true for $n=k+1$

Assuming that is true for some $k$ so that $2^k|a_{2k-1}$ but $2^{k+1}\not \mid|a_{2k-1}$ and $2^{k+1} |a_{2k}$ so there exist an odd integer $b$ and and integer $c$ so that $a_{2k-1} = 2^kb$ and $a_{2k}=2^{k+1}c$ then

$a_{2(k+1)-1}=a_{2k+1} = 6a_{2k-1} + 2 a_{2k}=$

$6*2^{k}b + 2*2^{k+1}c=$

$2^{k+1}(3b + 2c)$

So $2^{k+1}|a_{2(k+1)-1}$ but $2^{k+2}\not \mid a_{2(k+1)-1}$ as $3b+2c$ is odd.

And $a_{2(k+1)}=a_{2k+2}= = 6a_{2k} + 2a_{2k+1}=$

$6*2^{k+1}c + 2(2^{k+1}(3b + 2c))=$

$3*2^{k+2}c + 2^{k+2}(3b+2c)$ .

So $2^{k+2}|a_{2(k+1)}$

So we are done.