# How do I find the nth term of the Fibonacci sequence?

Sep 13, 2015

If ${F}_{0} = 0$ and ${F}_{1} = 1$, then ${F}_{n} = \frac{{\phi}^{n} - {\left(- \phi\right)}^{- n}}{\sqrt{5}}$, where $\phi = \frac{1 + \sqrt{5}}{2}$

#### Explanation:

I will assume that you are familiar with the definition of the Fibonacci sequence:

${F}_{0} = 0$, ${F}_{1} = 1$, ${F}_{n} = {F}_{n - 2} + {F}_{n - 1}$

yielding:

$0 , 1 , 1 , 2 , 3 , 5 , 8 , 13 , 21 , \ldots$
$\textcolor{w h i t e}{}$

Let's prove this formula by induction:

Let $f \left(n\right) = \frac{{\phi}^{n} - {\left(- \phi\right)}^{- n}}{\sqrt{5}}$

First note:

$\frac{1}{\phi} = \frac{2}{1 + \sqrt{5}} = \frac{2 \left(\sqrt{5} - 1\right)}{\left(\sqrt{5} - 1\right) \left(\sqrt{5} + 1\right)}$

$= \frac{2 \left(\sqrt{5} - 1\right)}{5 - 1} = \frac{\sqrt{5} - 1}{2}$

and

${\phi}^{2} = \frac{\left(1 + \sqrt{5}\right) \left(1 + \sqrt{5}\right)}{4} = \frac{1 + 2 \sqrt{5} + 5}{4}$

$= \frac{3 + \sqrt{5}}{2} = \frac{1 + \sqrt{5}}{2} + 1 = \phi + 1$

so ${\phi}^{2} - \phi - 1 = 0$

Base case

$f \left(0\right) = \frac{{\phi}^{0} - {\left(- \phi\right)}^{- 0}}{\sqrt{5}} = \frac{1 - 1}{\sqrt{5}} = 0 = {F}_{0}$

$f \left(1\right) = \frac{{\phi}^{1} - {\left(- \phi\right)}^{- 1}}{\sqrt{5}} = \frac{\frac{1 + \sqrt{5}}{2} - \left(- \frac{\sqrt{5} - 1}{2}\right)}{\sqrt{5}} = 1 = {F}_{1}$

Induction step

Suppose ${F}_{n - 2} = f \left(n - 2\right)$ and ${F}_{n - 1} = f \left(n - 1\right)$

Then:

$\sqrt{5} \left(f \left(n\right) - f \left(n - 1\right) - f \left(n - 2\right)\right)$

$= \left({\phi}^{n} - {\left(- \phi\right)}^{- n}\right) - \left({\phi}^{n - 1} - {\left(- \phi\right)}^{- \left(n - 1\right)}\right) - \left({\phi}^{n - 2} - {\left(- \phi\right)}^{- \left(n - 2\right)}\right)$

$= \left({\phi}^{n} - {\phi}^{n - 1} - {\phi}^{n - 2}\right) - {\left(- 1\right)}^{n} \left({\phi}^{-} n + {\phi}^{- \left(n - 1\right)} - {\phi}^{- \left(n - 2\right)}\right)$

$= {\phi}^{n - 2} \left({\phi}^{2} - \phi - 1\right) + {\left(- 1\right)}^{n} {\phi}^{- n} \left({\phi}^{2} - \phi - 1\right) = 0$

So $f \left(n\right) = f \left(n - 2\right) + f \left(n - 1\right) = {F}_{n - 2} + {F}_{n - 1} = {F}_{n}$