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