Proof $a_{n}$ by induction This topic is a continuation of Prove that $a_{n} = a_{n-1} + a_{n-2}$.
I need to prove that $a_{n} = (\frac{5+3\sqrt{5}}{10})(\frac{1+\sqrt{5}}{2})^{n} + (\frac{5-3\sqrt{5}}{10})(\frac{1-\sqrt{5}}{2})^{n}$ for all $n \geq 1$.
This is how I tried to prove this.
Basic step: $a_{1} = (\frac{5+3\sqrt{5}}{10})(\frac{1+\sqrt{5}}{2})^{1} + (\frac{5-3\sqrt{5}}{10})(\frac{1-\sqrt{5}}{2})^{1}$ which is equal to $2$ and is correct.
Inductive step: Let $k \geq 1$ and let the statement apply to each $k$ where $1 \geq j \geq k$. From the previous topic we know that $a_{k} = a_{k-1} + a_{k-2}$ and so that $a_{k+1} = a_{k} + a_{k-1}$. Because of the hypothesis we know that the statement applies for $a_{k}$ and $a_{k-1}$. As $a_{k+1}$ exists of the sum of $a_{k}$ and $a_{k-1}$, we can conclude that the statement also applies for $a_{k+1}$.
Is this proof by induction valid?

We have $a_{n} = a_{n-1} + a_{n-2}$ with $a_{0} = 1$ and $a_{1}=2$.
Let $b_{n} = (\frac{5+3\sqrt{5}}{10})(\frac{1+\sqrt{5}}{2})^{n} + (\frac{5-3\sqrt{5}}{10})(\frac{1-\sqrt{5}}{2})^{n}$.
To prove that $a_n=b_n$, it is enough to prove that $b_{n} = b_{n-1} + b_{n-2}$ with $b_{0} = 1$ and $b_{1}=2$.


*

*$b_{0} = 1$ and $b_{1}=2$ is immediate.

*$b_{n} = b_{n-1} + b_{n-2}$ follows from the fact that $\frac{1\pm\sqrt{5}}{2} $ are roots of $x^2=x+1$.
