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$?
On
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$
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}$.