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.

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.
