20
$\begingroup$

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.

  • 5
    [Quite related](http://math.stackexchange.com/questions/61997). You can use the eigendecomposition of a matrix to derive the Binet formula. Alternatively, you solve the characteristic equation of your recurrence.2011-09-16
  • 9
    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.2011-09-16
  • 2
    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.2011-09-16
  • 1
    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.2011-09-16
  • 1
    Did you read http://en.wikipedia.org/wiki/Fibonacci_number#Closed-form_expression ?2011-09-16

7 Answers 7