Show that the elements of the sequence are divisible by $2^n$ 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.
 A: 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.
A: 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.
A: 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.
