# Why is $F_n = r^n$ a solution of the difference equation if $r$ satisfies $r^2-r-1=0$?

The following is from p.4 of https://www.math.ucdavis.edu/~hunter/intro_analysis_pdf/ch3.pdf

The terms in the Fibonacci sequence are uniquely determined by the linear difference equation

$$F_n − F_{n−1} − F_{n−2} = 0, n ≥ 3$$

with the initial conditions $$F_1 = 1, F_2 = 1$$.

We see that $$F_n = r^n$$ is a solution of the difference equation if $$r$$ satisfies $$r^2 − r − 1 = 0$$ which gives $$r = \phi$$ or −$$\dfrac{1}{\phi}$$ where $$\phi = \dfrac{1 + \sqrt{5}}{2}\approx 1.61803$$.

I'm unable to see why $$F_n = r^n$$ is a solution of the difference equation if $$r$$ satisfies $$r^2-r-1=0$$.

• Do you mean $F_n$ not $F^n$? If so, plugging in $F_n=r^n$, we get $r^n-r^{n-1}-r^{n-2}=r^{n-2}(r^2-r-1)=0$ and clearly $r\ne0$. – TheSimpliFire Dec 28 '18 at 19:12
• See the answer at this duplicate. – Dietrich Burde Dec 28 '18 at 19:15
• @TheSimpliFire: Yes, I meant $F_n$. – K.M Dec 28 '18 at 19:28

Hint: Multiply $$r^2 − r − 1 = 0$$ by $$r^{n-2}$$.
• Multiplying $r^2 -r-1=0$ by $r^{n-2}$, I get that $r^{n}-r^{n-1}-r^{n-2}=0$, but I'm not sure how I would get that $F_{n}=r^{n}$ without first assuming that $F_n=r^{n}$ and then plugging this into $r^{n}-r^{n-1}-r^{n-2}=0$ – K.M Dec 29 '18 at 21:14
Usually, the complete solution to a difference equation with two distinct roots in the characteristic equation is in the form $$A{r_1}^n + B{r_2}^n$$.
In your case, the distinct roots for $$r_1$$ and $$r_2$$ are $$\phi = \dfrac {1+\sqrt{5}}{2}$$ and $$-\dfrac {1}{\phi} = \dfrac {1-\sqrt{5}}{2}$$. Thus the complete solution is $$F_n = \dfrac {1}{\sqrt {5}} \left (\phi^n - \dfrac {1}{\phi}^n \right)$$