# Prove the formula using “complete induction”

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$$.

• 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. – lulu Feb 11 at 15:26
• First of all, if we don't know $S_1$ and $S_2$, we can't deduce any term. – enedil Feb 11 at 15:27
• I had edited the question and added $S _ { 1 } = 3$ and $S _ { 2 } = 7$ – Tariro Manyika Feb 11 at 15:31
• 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$. – Lee Mosher Feb 11 at 15:44
• The recursion formula $S_n = 2 S_{n-1} + S_{n-2}$ is intended to apply only for $n \ge 3$. – Lee Mosher Feb 11 at 15:45