divisibility problem using induction If $S_n=(3+\sqrt{5})^n+(3-\sqrt{5})^n$ show that $S_n$ is integer and that $S_{n+1}=6S_n-4S_{n-1}$. Further deduce that the next integer greater than $(3+\sqrt{5})^n$ is divisible by $2^n$.
My work so far:  I have done part 1 using mathematical induction but it is part 2 of divisibility where I am stuck 
 A: First argue that $\lceil (3+\sqrt{5})^n\rceil=S_n$ (hint: $(3-\sqrt{5})^n<1$ and $S_n\in\mathbb{N}$), so we actually want to show that $S_n$ is divisible by $2^n$.
Prove the rest by induction using the relation you deduced, noting that $6=2\cdot 3$ and $4=2^2$
A: Perhaps it should be mentioned that the matrix
$$
A 
=
\begin{bmatrix}
3 + \sqrt{5} & 0\\
0 & 3 - \sqrt{5}
\end{bmatrix}
$$
has minimal polynomial over $\mathbf{Q}$ given by $x^{2} - 6 x + 4$, so that
$$
A^{2} - 6 A + 4 = 0
$$
and thus
$$
A^{n+2} - 6 A^{n+1} + 4 A^{n} = 0.
$$
Taking traces, and noticing that $S_{n} = \operatorname{tr}(A^{n})$, one gets part one.
A: This is not elementary, but, for the sake of completeness, I would like to put it here.
Since $S_n\in \mathbb Q(\sqrt5)$ and $\sigma (S_n)=S_n$, where $\sigma$ is the qutomorphism of $\mathbb Q(\sqrt5)$ that sends $\sqrt5$ to $-\sqrt5$, $S_n\in \mathbb Q$. Moreover, $3+\sqrt5$ and $3-\sqrt5$ are both algebraic integers, hence so is $S_n$. So $S_n$ is a rational algebraic integer, By this theorem, $S_n$ is thus an integer. Next notice that, since $(3+\sqrt5)^2=14+6\sqrt5$, the relation follows for $A_n:=(3+\sqrt5)^n$, and also for $B_n:=(3-\sqrt5)^n$, hence for $S_n=A_n+B_n$. Now, for the last part, notice that, as L.F. pointed out, it is enough to prove that $2^n\mid S_n$.
Write $A_n=p_n+q_n\sqrt5$, then $B_n=p_n-q_n\sqrt5$, so $S_n=2p_n$. By calculations we find that  

$p_{n+1}=3p_n+5q_n$ and $q_{n+1}=p_n+3q_n$.  

For $n=1$, we know that both $p_n$ and $q_n$ are divisible by $2^{n-1}$. By the above relations, this tells us that, for all $n$, both $p_n$ and $q_n$ are divisible $2^{n-1}$. Consequently $S_n$ is always divisible by $2^n$.
Q.E.D.
