<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] The recurrence is $L_{n+1}=L_{n}+L_{n-1}$.Now I am using the characteristic
equation of this above recurrence to solve the recurrence. So the characteristic 
equation of this above recurrence is as follows $\implies$
Put $L_{n}={r^n}$ and solve the equation $\implies ({r^2}-r-1)=0$
By solving this equation we get $r=\frac{1+_-\sqrt{5}}{2}$(+ and -).
Hence $r=\frac{1+\sqrt{5}}{2}\;\;and\;\;\frac{1-\sqrt{5}}{2}$.Now denote these
two roots by $r_1\;and\;r_2$. It is given that $L_1=1\;and\;L_2=3$.
Hence $L_n=A{r_1^n}+B{r_2^n}$ where A and B are constants.Hence we have shown 
that $L_n=a{(\frac{1+\sqrt5}{2})^n}+b{(\frac{1-\sqrt5}{2})^n}$. Now put $n=1$
and$n=3$, then you get two equations with two unknowns which is solvable.
Two equations are $\implies$ $1=A{r_1}+B{r_2}\;\;and\;\;3=A{r_1^2}+B{r_2^21}$.
Solving this two equations we get $A=1\;\;and\;\;B=1$. Hence $a=1\;and\;b=1$.
Finally we get $L_n={(\frac{1+\sqrt5}{2})^n}+{(\frac{1-\sqrt5}{2})^n}$. 
</s>