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.

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.
