# 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$?

• Knowing the first two Lucas numbers allows you to find a and b. Then you can use induction. – Steve D Apr 17 '16 at 19:55
• This is an easy case of a "linear recurrence relation". I suggest you look it up, it is frequently useful. The Wikipedia article is not bad en.wikipedia.org/wiki/Recurrence_relation but I would skip the stuff about difference equations. – almagest Apr 17 '16 at 20:06

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

• You can obtain the $\pm$ symbol by typing \pm in math mode. If you want the $\mp$ symbol, type \mp in math mode. – N. F. Taussig Apr 18 '16 at 9:53
• Thank you for telling me this.I didn't know. – sayan kundu Apr 18 '16 at 10:15

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$