0
$\begingroup$

Let $S _ { n } = 2 \cdot S _ { n - 1 } + S _ { n - 2 }$ with $S _ { 1 } = 3$ and $S _ { 2 } = 7$. Prove that for every integer $n \geq 1$ $$S _ { n } = \frac { 1 } { 2 } ( 1 + \sqrt { 2 } ) ^ { n + 1 } + \frac { 1 } { 2 } ( 1 - \sqrt { 2 } ) ^ { n + 1 }$$

Hint: What are the solutions of the equation $x ^ { 2 } = 2 x + 1 ?$ Using these solutions will simplify the proof.

My working:

$$\frac { S _ { n } } { S _ { n - 2 } } = 2 \frac { S _ { n - 1 } } { S _ { n - 2 } } + 1$$

$$x ^ { 2 } = 2 x + 1$$

$$x = \frac { - ( - 2 ) \pm \sqrt { ( - 2 ) ^ { 2 } - 4 ( 1 ) ( - 1 ) } } { 2 ( 1 ) }= \frac { 2 \pm \sqrt { 8 } } { 2 }$$ that is $1 + \sqrt { 2 }$ or $1 - \sqrt { 2 }$.

Question. I'm stuck here. Someone suggested proof by complete induction but if I test $n=1$ I will get $S_{0}$ which is outside the range $n \geq 1$.

$\endgroup$
  • $\begingroup$ You haven't supplied initial conditions for the $S_n$. Assuming you set them so that they match those of the Geometric Sequence then all you have to show is that the latter satisfies the same recursion as the former. $\endgroup$ – lulu Feb 11 at 15:26
  • $\begingroup$ First of all, if we don't know $S_1$ and $S_2$, we can't deduce any term. $\endgroup$ – enedil Feb 11 at 15:27
  • $\begingroup$ I had edited the question and added $S _ { 1 } = 3$ and $S _ { 2 } = 7$ $\endgroup$ – Tariro Manyika Feb 11 at 15:31
  • $\begingroup$ I'm not sure what you might mean by "if I test $n=1$ I will get $S_0$ which is outside the range $n \ge 1$". If you test $n=1$ you get $S_1=\frac{1}{2}(1+\sqrt{3})^2 + \frac{1}{2}(1-\sqrt{3})^2=3$. $\endgroup$ – Lee Mosher Feb 11 at 15:44
  • 1
    $\begingroup$ The recursion formula $S_n = 2 S_{n-1} + S_{n-2}$ is intended to apply only for $n \ge 3$. $\endgroup$ – Lee Mosher Feb 11 at 15:45

Your Answer

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

Browse other questions tagged or ask your own question.