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

  • 3
    $\begingroup$ Knowing the first two Lucas numbers allows you to find a and b. Then you can use induction. $\endgroup$ – Steve D Apr 17 '16 at 19:55
  • $\begingroup$ 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. $\endgroup$ – 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}$.

  • $\begingroup$ You can obtain the $\pm$ symbol by typing \pm in math mode. If you want the $\mp$ symbol, type \mp in math mode. $\endgroup$ – N. F. Taussig Apr 18 '16 at 9:53
  • $\begingroup$ Thank you for telling me this.I didn't know. $\endgroup$ – 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$


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.