# 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

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$

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.

• Interesting method. Worth remembering. – Pedro Tamaroff Feb 26 '13 at 4:48

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.

• In spite of my first sentence, this answer, except for the first part, is quite basic. – awllower Feb 25 '13 at 14:08