Prove $\lceil(3 + \sqrt{5})^n\rceil$ is divisible by $2^n$ for all natural numbers $n$

Question

This sub-question is part of a larger question:

If $S_n = \left(3 + \sqrt{5}\right)^n + \left(3 - \sqrt{5}\right)^n$, 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$.

I was able to prove the first part easily using induction, but for the second part, I have no clue. If I use induction, I get stuck with the ceil function, which, for me, is difficult to manipulate.

How do I prove the second part?

Answer 1

I’m going with $S_n=(3+\sqrt5)^n+(3-\sqrt5)^n$ since in the case of ‘’minus’’ instead of ‘’+’’ $S_1$ is not an integer Let $r_1=3+\sqrt5$ and $r_2=3-\sqrt5$. Note that $r_1+r_2=6$ and $r_1r_2=4$ therefore $r_1$ and $r_2$ are roots of the polynomial $r^2-6r+4=0$.

From this above, we deduce that $S_n$ satisfies the linear recurrence relation: $S_{n+2}-6S_{n+1}+4S_n=0$ with $S_0=2$ and $S_1=6$

I let you finish by induction.

Answer 2

You know that $S_n$ is an integer and $3-\sqrt 5<1\iff (3-\sqrt 5)^n<1\;\forall n\in\Bbb N$ so $(3+\sqrt 5)^n=S_n-(3-\sqrt 5)^n\implies \lceil (3+\sqrt 5)^n\rceil =S_n=(3+\sqrt 5)^n+(3-\sqrt 5)^n$ Then if you calculate the $n$-th powers you obtain thesis.

You can also use induction since $S_{n+2}-6S_{n+1}+4S_n=0$