Prove that the next integer greater than $(3+\sqrt{5})^n$ is divisible by $2^n$ where $n$ is a natural number. The problem is given in a chapter of induction. It is actually a part of this whole question:
If $S_n = (3+\sqrt{5})^n + (3-\sqrt{5})^n$, show that $S_n$ is an integer and that $S_{n+1} = 6S_n - 4S_{n-1}$. Deduce that the next integer greater than $(3+\sqrt{5})^n$ is divisible by $2^n$.
I could do the first two parts. The first part I have done by induction and the second part by simply using the given formula. I cannot proceed at all in the third part. I think it may need induction. Please give any solutions regarding the third one and see whether the second one can be proved using induction.
If we denote $a:=3+\sqrt{5}$ and $b:=3-\sqrt{5}$, then $a$ and $b$ are the roots of the polynomial $$x^2-6x+4$$
Therefore , the number $s_n:=a^n+b^n$ satisfies the recursion :
$$s_1=6$$
$$s_2=28$$
$$s_n=6s_{n-1}-4s_{n-2}$$
Because of $0<b^n<1$ for $n\ge 1$, we have $\lceil a^n \rceil=s_n$
Suppose $s_n$ is divisble by $2^n$ and $s_{n-1}$ is divisible by $2^{n-1}$ (This claim is true for $n=2$) . Then, $s_{n+1}=6s_n-4s_{n-1}$ is divisble by $2^{n+1}$ because $6s_n$ and $4s_{n-1}$ are both divisble by $2^{n+1}$. Therefore, the induction step is completed.