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 ]$ .
 A: 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. 
A: 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}$?
A: An idea for you assuming the claim's true for exponents up to $\;k\;$ . Observe that I begin from the middle of your work:
$$\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 ]=$$
$$=2^km\cdot6-(3+\sqrt5)(3-\sqrt5)\overbrace{\left[(3+\sqrt5)^{k-1}+(3-\sqrt5)^{k-1}\right]}^{=2^{k-1}\cdot r\,,\,\,r\in\Bbb Z}=$$
$$=2^{k+1}\cdot3m-(9-5)\cdot2^{k-1}\cdot r=2^{k+1}(3m+r).\;\;\;\;\;\square$$
