<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] You're on the right track, but you need to use a slightly extended form of induction for this problem.  Note that to prove $P(k+1)$, you don't have to limit yourself to $P(k)$; you can also use $P(i)$ for $i\leq k$.  In this case, the proposition $P(k-1)$ will prove helpful for dealing with the last term.  (But note that this means that you're going to have to prove two base cases, rather than just one!)
To be a little more explicit, let's write $s_n=(3+\sqrt{5})^n+(3-\sqrt{5})^n$.  Then the relation that you've discovered is that $s_{k+1}=6s_k-4s_{k-1}$.  (Note that you have a small mistake where you write $2^k\cdot m\cdot 4$; that $4$ should be a $6$, because it's $(3+\sqrt5)+(3-\sqrt5)$.  The $4$ in the second term here arises as the product $(3+\sqrt5)\cdot(3-\sqrt5)$.)  Now, we know that there are $a$ and $b$ such that $s_k=a\cdot 2^k$ and $s_{k-1}=b\cdot 2^{k-1}$; what does the relation then say about $s_{k+1}$?
</s>