Mathematical induction problem. Let $S_{n}=\left (3+\sqrt{5}\right)^{n}+\left(3-\sqrt{5}\right)^{n}$

Question

Let $S_{n}=\left (3+\sqrt{5}\right)^{n}+\left(3-\sqrt{5}\right)^{n}$then, by mathematical induction, show that $S_{n}$ is an integer. Also, prove that the next integer greater than $\left(3+\sqrt{5}\right)^{n}$ is divisible by $2^{n}$. Note: please do not use binomial theorem to prove the first part.

Answer 1

$3+\sqrt{5}$ and $3-\sqrt{5}$ are roots of the polynomial $r \mapsto r^2 - 6r + 4$, and by the form of $S_n$ it tells us that it is a solution to the recurrence relation $f(n+2) - 6f(n+1) + 4f(n) = 0$. Now all you need to do is to check that $S_0$ and $S_1$ are integers to prove that $S_n$ is an integer for any natural $n$. The next part is equally simple as you can see a factor of $2$ popping out every time you turn the recurrence crank. All you need to check is that $(3-\sqrt{5})^n < 1$.

Answer 2

Hint: $$A^{n+1} + B^{n+1} = (A + B)(A^n + B^n) - AB(A^{n-1} + B^{n-1})$$