Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
3  
Quite related. You can use the eigendecomposition of a matrix to derive the Binet formula. Alternatively, you solve the characteristic equation of your recurrence. –  J. M. Sep 16 '11 at 5:14
3  
There's a straightforward induction proof. The base cases are $n=0$ and $n=1$. For the induction step, you assume that this formula holds for $k-1$ and $k$, and use the recurrence to prove that the formula holds for $k+1$ as well. –  Srivatsan Sep 16 '11 at 5:14
1  
Briefly: associated with your difference equation $u_{n+1}-u_n-u_{n-1}=0$ is the polynomial $x^2-x-1$. Find the roots of that polynomial, and an appropriate linear combination of powers of those two roots gives Binet. –  J. M. Sep 16 '11 at 5:16
    
Yet another method is to a uniqueness theorem. Since the solution must be unique, just show your proposed $u_n$ satisfies the recurrence relation and has the same initial conditions. –  Ragib Zaman Sep 16 '11 at 10:44
    
Did you read en.wikipedia.org/wiki/Fibonacci_number#Closed-form_expression ? –  lhf Sep 16 '11 at 12:10

3 Answers 3

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.

share|improve this answer

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.

share|improve this answer

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

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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