5
$\begingroup$

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

$\endgroup$
0
9
$\begingroup$

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$

$\endgroup$
5
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ Interesting method. Worth remembering. $\endgroup$ – Pedro Tamaroff Feb 26 '13 at 4:48
2
$\begingroup$

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.

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.