<s>[INST] 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.
 [/INST] 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.
</s>