<s>[INST] Lucas numbers proof I'm running through some example problems and encountered this one:
Define a sequence of integers $L_n$ by $L_1=1, L_2=3, L_{n+1}=L_n+L_{n-1}.$ Show that $L_n = a\cdot \left(\frac{1+\sqrt{5}}{2}\right)^n + b\cdot \left(\frac{1-\sqrt{5}}{2}\right)^n$ and find the values of $a$ and $b$. 
I wasn't able to prove the formula using induction first since the LHS has $a$ and $b$ in it so I cannot show the base case. How can I show the equation holds, and then find $a$ and $b$?
 [/INST] We, as usual, assume that there is a solution $L_n=\alpha^n$ so we have $\alpha^{n+1}=\alpha^n+\alpha^{n-1}$ hence that $$\alpha^2=\alpha+1$$ It follows
$$\begin{cases} \alpha_1=\frac{1+\sqrt 5}{2}\\ \alpha_2=\frac{1-\sqrt 5}{2}\end{cases}$$
Hence $L_n=(\frac{1+\sqrt 5}{2})^n$ and $L_n=(\frac{1-\sqrt 5}{2})^n$ are solutions.
A general solutions is $$L_n=a(\frac{1+\sqrt 5}{2})^n+b(\frac{1-\sqrt 5}{2})^n$$ what is straightforward to verify. Two initial conditions determine the values $a$ and $b$ in each case. For the given values we have to solve 
$$\begin{cases}a(\frac{1+\sqrt 5}{2})+b(\frac{1-\sqrt 5}{2})=1\\a(\frac{1+\sqrt 5}{2})^2+b(\frac{1-\sqrt 5}{2})^2=3\end{cases}$$ which is an easy linear system in $a$ and $b$
</s>