How to prove that the Binet formula gives the terms of the Fibonacci Sequence?

Question

This formula provides the $n$th term in the Fibonacci Sequence, and is defined using the recurrence formula: $u_n = u_{n − 1} + u_{n − 2}$, for $n > 1$, where $u_0 = 0$ and $u_1 = 1$.

Show that

$$u_n = \frac{(1 + \sqrt{5})^n - (1 - \sqrt{5})^n}{2^n \sqrt{5}}.$$

Please help me with its proof. Thank you.

Answer 1

HINT $\rm\quad\ u_n =\: x^n\ \iff\ 0\ =\ x^{n+2}\:-\:x^{n+1}\:-\:x^n\ =\ (x^2-x-1)\ x^n\ =:\ f(x)\ x^n\:.\:$

Therefore, we infer that $\rm\ \phi^{\ n}\:$ and $\rm\ \bar\phi^{\ n}\:$ are solutions, where $\rm\:\phi,\ \bar\phi\:$ are the roots of $\rm\:f(x)\:.$

Thus by linearity $\rm\ g_n =\: c\ \phi^{\:n} +d\ \bar\phi^{\:n}\ $ is also a solution, for any constants $\rm\: c,\:d\:.$

By induction, solutions are uniquely determined by their initial conditions $\rm\:u_0,\:u_1,\:$ hence

$\begin{array}{rl} \qquad\qquad\rm g_n =\: f_n\!\! &\iff\quad\begin{array}{}\rm 0\: =\: f_0 =\: g_0 =\: c+d \\ \rm 1\: =\: f_1 =\: g_1 =\: c\ \phi + d\ \bar\phi\end{array} \\ &\iff\quad\rm d = {-}c,\quad c\: =\: \dfrac{1}{\phi-\bar\phi} \\ &\iff\quad\rm g_n =\: \dfrac{\phi^{\:n}-\bar\phi^{\:n}}{\phi\ -\ \bar\phi\ \ \ } \end{array}$

This is a prototypical example of the power of uniqueness theorems for proving equalities. Here the uniqueness theorem is that for linear difference equations (i.e. recurrences). While here the uniqueness theorem has a trivial one-line proof by induction, in other contexts such uniqueness theorems may be far less less trivial (e.g. for differential equations). As such, they may provide great power for proving equalities. For example, some of my prior posts.

Answer 2

Let's catalog some those suggestions given in the comments. First, let me rewrite the Binet formula in a more convenient form:

$$F_n=\frac1{\sqrt{5}}(\phi^n-(-\phi)^{-n})$$

where $\phi=\frac12(1+\sqrt5)$ is the golden ratio.

1) Verifying the Binet formula satisfies the recursion relation. First, we verify that the Binet formula gives the correct answer for $n=0,1$. The only thing needed now is to substitute the formula into the difference equation $u_{n+1}-u_n-u_{n-1}=0$. You then obtain

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

We can do some factoring:

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

and since we know that $\phi^2-\phi-1=0$, Binet's formula is verified.

2) Solving the characteristic equation. One can associate with the linear difference equation $u_{n+1}-au_n-bu_{n-1}=0$ the characteristic equation $x^2-ax-b=0$. If the two roots of the characteristic equation are $x_1$ and $x_2$, the solutions of the difference equation take the form $u_n=px_1^n+qx_2^n$.

For the Fibonacci recurrence, $a=b=1$, and the roots of $x^2-x-1=0$ are $\phi$ and $1-\phi=-\phi^{-1}$. Thus, $F_n$ is expressible as

$$F_n=p\phi^n+q(-\phi)^{-n}$$

We can solve for $p$ and $q$ by using the initial conditions $F_0=0,F_1=1$. This gives the two equations

$$\begin{align*}p+q&=0\\p\phi+q(1-\phi)&=1\end{align*}$$

with the solutions $p=-q=\frac1{\sqrt{5}}$. Substituting that into the preliminary expression for $F_n$ yields the Binet formula.

Answer 3

Using generating functions à la Wilf's "generatingfunctionology". Define the ordinary generating function: $$ F(z) = \sum_{n \ge 0} F_n z^n $$ The Fibonacci recurrence is: $$ F_{n + 2} = F_{n + 1} + F_n \qquad F_0 = 0, F_1 = 1 $$ Applying properties of the ordinary generating function: $$ \frac{F(z) - F_0 - F_1 z}{z^2} = \frac{F(z) - F_0}{z} + F(z) $$ The solution to this equation as partial fractions is: $$ F(z) = \frac{z}{1 - z - z^2} = \frac{1}{\sqrt{5}}\cdot \left( \frac{1}{1 - \phi z} - \frac{1}{1 - \bar{\phi} z} \right) $$ Here $\phi = \frac{1}{2} (1 + \sqrt{5})$ and $\bar{\phi} = \frac{1}{2}(1 - \sqrt{5})$ are the roots of $r^2 - r - 1$. This is just two geometric series: $$ F_n = \frac{1}{\sqrt{5}}(\phi^n - \bar{\phi}^n) $$

Answer 4

Fibonacci sequence is

$$0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89.........$$

We can observe that a recurrence relation exist

$$y(n+2) = y(n)+y(n+1)$$ or

$$y(n) = y(n-1)+y(n-2)$$

with initial conditions $$y(0) = 0; y(1)=1$$

Now we take the help of Z transform

Taking Z transform on both side of 1st equation

$$z^2Y(z)-z^2y(0)-zy(1) = Y(z) +zY(z) -zy(0)$$

$$Y(z) = \frac{z}{z^2-z-1}$$

Now we have to perform inverse Z transform

$$z^2-z-1=0$$

$$\alpha=z_1= \frac{1+\sqrt5}{2}$$

$$\beta=z_2= \frac{1-\sqrt5}{2}$$

$$Y(z) = \frac{z}{(z-\alpha)(z-\beta)}=\frac{A}{z-\alpha} + \frac{B}{z-\beta}$$

$$A = \frac{\alpha}{\alpha-\beta}$$

$$B= \frac{\alpha}{\beta-\alpha}$$

$$a^{n}u(n) \rightleftharpoons \frac{z}{z-a}$$

$$a^{n-1}u(n-1) \rightleftharpoons \frac{1}{z-a}$$

$$y(n) = \frac{\alpha^n - \beta^n}{\alpha - \beta} u(n-1)$$

Golden Ratio $$\phi = \frac{1+\sqrt5}{2}$$

$$\alpha=\phi$$

$$\alpha+\beta = 1$$

$$\beta= 1- \phi$$

$$y(n) = \frac{\phi^n - (1-\phi)^n}{2\phi} u(n-1)$$

$$y(n) = \frac{(\frac{1+\sqrt5}{2})^n - (\frac{1-\sqrt5}{2})^n}{1+\sqrt5} u(n-1)$$

Answer 5

Let $$A=\begin{pmatrix} 1 & 1 \\ 1 & 0 \end{pmatrix}$$ $$M_n = \begin{pmatrix} F_{n+1} & F_n \\ F_n & F_{n-1} \end{pmatrix}$$ By induction, you can show that $M_n=A^n$. Now, the eigenvalues of $A$ satisfy $\lambda^2-\lambda-1=0$. Let them be $\lambda_1$ and $\lambda_2$.

$A$ can be diagonalized and written as $A=SBS^{-1}$, where $B=\begin{pmatrix} \lambda_1 & 0\\ 0 & \lambda_2 \end{pmatrix}$, $S=\begin{pmatrix} \lambda_1 & \lambda_2 \\ 1 & 1 \end{pmatrix}$ Thus, $$A^n = SBS^{-1}SBS^{-1}SBS^{-1}SBS^{-1}.... = SB^nS^{-1}$$ $$=\begin{pmatrix} \lambda_1 & \lambda_2 \\ 1 & 1 \end{pmatrix}\begin{pmatrix} \lambda_1^n & 0\\ 0 & \lambda_2^n \end{pmatrix}(\frac{1}{\lambda_1-\lambda_2}\begin{pmatrix} 1 & -\lambda_2 \\ -1 & \lambda_1 \end{pmatrix})$$ $$=\frac{1}{\lambda_1-\lambda_2}\begin{pmatrix} \lambda_1 & \lambda_2 \\ 1 & 1 \end{pmatrix}\begin{pmatrix} \lambda_1^n & -\lambda_1^n\lambda_2\\ -\lambda_2^n & \lambda_2^n\lambda_1 \end{pmatrix}$$ $$=\frac{1}{\lambda_1-\lambda_2}\begin{pmatrix} \lambda_1^{n+1}-\lambda_2^{n+1} & -\lambda_1\lambda_2(\lambda_1^n-\lambda_2^n)\\ \lambda_1^n-\lambda_2^n &-\lambda_1\lambda_2(\lambda_1^{n-1}-\lambda_2^{n-1}) \end{pmatrix}$$ Using $\lambda_1\lambda_2=-1$, $A^n = \begin{pmatrix} F_{n+1} & F_n \\ F_n & F_{n-1} \end{pmatrix}$, $\lambda_1=\frac{1+\sqrt{5}}{2}$ and $\lambda_2=\frac{1-\sqrt{5}}{2}$, we get

$$\begin{pmatrix} F_{n+1} & F_n \\ F_n & F_{n-1} \end{pmatrix} = \frac{1}{\sqrt{5}}\begin{pmatrix} \lambda_1^{n+1}-\lambda_2^{n+1} &\lambda_1^n-\lambda_2^n\\ \lambda_1^n-\lambda_2^n &\lambda_1^{n-1}-\lambda_2^{n-1} \end{pmatrix}$$

Which gives us $F_n=\frac{\lambda_1^n-\lambda_2^n}{\sqrt{5}}$, as required.

Answer 6

Alternatively, you can use the linear recursion difference formula. This works for any linear recursion (i.e. a recursion in the form $a_n=qa_{n-1}+ra_{n-2}$.

Step 1 for closed form of linear recursion: Find the roots of the equation $x^2=qx+r$. For Fibonnaci, this formula is $x^2=x+1$. The roots are $\frac{1\pm\sqrt5}2$.

Step 2: The closed form is in the form $a(n)=g\cdot\text{root}_1^n+h\cdot\text{root}_2^n$. For Fibonacci, this yields $a_n=g(\frac{1+\sqrt5}2)^n+h(\frac{1-\sqrt5}2)^n$.

Step 3: Solve for $g$ and $h$. All you have to do know is plug in two known values of the sequence into this equation. For fibonacci, you get $g=h=1/\sqrt5$. You are done!

Answer 7

See here -- the solutions of $a_n=Aa_{n-1}+Ba_{n-2}$ are given by $a_n=C\lambda_1^n+D\lambda_2^n$ if $\lambda_1\neq \lambda_2$, where $C,D$ are constants created by $a_0,a_1$, and $\lambda_1, \lambda_2$ are the solutions of $\lambda^2-A\lambda-B=0$ (the characteristic polynomial), and $a_n=C\lambda^n+Dn\lambda^n$ if $\lambda_1=\lambda_2=\lambda$.

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

In this case, you want $\lambda_1=\frac{1 + \sqrt{5}}{2}$, $\lambda_2=\frac{1 - \sqrt{5}}{2}$, $C,D$ created by $u_0=0$, $u_1=1$.

Apply Vieta's formulas.

$\lambda_1+\lambda_2=1=A$, $\lambda_1\lambda_2=-1=-B$.

The characteristic polynomial is $\lambda^2-\lambda-1=0$.

The recurrence relation is $u_n=u_{n-1}+u_{n-2}$ for $n>1$ with $u_0=0$, $u_1=1$.

$u_n$ is an integer because $u_0$, $u_1$ are integers and the recurrence relation shows that $u_2=u_1+u_0\in\mathbb Z$, etc. You could use induction here.

(I.e., if $u_k$, $u_{k+1}$ are integers for some $k\in\mathbb Z$, $k\ge 0$, then $u_{k+2}=u_{k+1}+u_k$ is also an integer).

Furthermore, $u_n$ is the integer closest to $\frac{1}{\sqrt{5}}\left( \frac{1 + \sqrt{5}}{2} \right)^n$ (see this question).

To prove this, it's enough to prove that

$\left|\frac{1}{\sqrt{5}}\left( \frac{1 - \sqrt{5}}{2} \right)^n\right|<\frac{1}{2}$

and two proofs of that are seen in the linked question (one of them is in the comments there).

Similar facts are applicable for Pell's equations. See, e.g., this answer.

It's not easily applicable for Fibonacci numbers because $\frac{1}{2}$ isn't an integer, unlike in this sequence.