How to prove that the Binet formula gives the terms of the Fibonacci Sequence? 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.

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!
