<s>[INST] Prove by induction that $\left [ \left (3+\sqrt{5} \right )^{n} + \left (3-\sqrt{5} \right )^{n} \right ]$ is multiple of $2^{n}$ Prove by induction that :
$\left [ \left (3+\sqrt{5} \right )^{n} + \left (3-\sqrt{5} \right )^{n} \right ]$ is multiple of $ 2^{n}$
My proof is :
At $n=1$
$$\frac{\left ( 3+\sqrt{5} \right )+\left ( 3-\sqrt{5} \right )}{2} = \frac{6}{2} = 3 \in \mathbb{Z}$$
Assume $P(k)$ is true
$$\frac{\left ( 3+\sqrt{5} \right )^{k}+\left ( 3-\sqrt{5} \right )^{k}}{2^{k}} = m \in \mathbb{Z}$$
$$\Rightarrow \left ( 3+\sqrt{5} \right )^{k}+\left ( 3-\sqrt{5} \right)^{k} = 2^{k}.m \rightarrow (*)$$
At $n=k+1$
$$\left ( 3+\sqrt{5} \right )^{k+1}+\left ( 3-\sqrt{5} \right )^{k+1} = \left [ \left ( 3+\sqrt{5} \right )^{k}+\left ( 3-\sqrt{5} \right )^{k} \right ]\left [ \left ( 3+\sqrt{5} \right )+\left ( 3-\sqrt{5} \right ) \right ]-\left [ \left ( 3+\sqrt{5} \right )^{k}\left ( 3-\sqrt{5} \right )+\left ( 3-\sqrt{5} \right )^{k}\left ( 3+\sqrt{5} \right ) \right ]$$
from $(*) $:
$$\left ( 3+\sqrt{5} \right )^{k+1}+\left ( 3-\sqrt{5} \right )^{k+1} =2^{k}.m.6-\left ( 3+\sqrt{5} \right )\left ( 3-\sqrt{5} \right ) \left [ \left ( 3+\sqrt{5} \right )^{k-1}+\left ( 3-\sqrt{5} \right )^{k-1} \right ] $$
but i can't resume my proof .. i can't do any thing with $\left [ \left ( 3+\sqrt{5} \right )^{k-1}+\left ( 3-\sqrt{5} \right )^{k-1} \right ]$ .
 [/INST] Another way to solve this problem is to define $a_n = (3 + \sqrt{5})^n + (3-\sqrt{5})^n$ and note that the characteristic equation of this sequence is $x^2 - 6x + 4 = 0$. Therefore $a_{n+2} = 6a_{n+1} - 4a_n$
Obviously we have that $2 \mid a_1$ and $4 \mid a_2$. Now assume that $2^n \mid a_n$ for all $n \le k$ for some integer $k$. Then we have:
$$2^{k+1} \mid 6a_{k} - 4a_{k-1} = a_{k+1}$$
Hence the proof. 
</s>