Induction on the Fibonacci sequence? 
Prove by induction that the $i$th Fibonacci number satisfies the equality:
  $$F_i = \frac {\phi^i - \hat\phi{}^i}{\sqrt5}$$
  where $\phi$ is the golden ratio and $\hat\phi$ is its conjugate.

Thanks for the help. This is the first time I have dealt with the Fibonacci sequence and the first time I have used induction, so please be really explicit in your answers.

Since the $F_n$ are (uniquely) defined by
$$F_0=0,\qquad F_1=1,\qquad F_n=F_{n-1}+F_{n-2}\text{ if }n\ge2,$$
you have to show that $f(n):=\frac{\phi^n-\hat\phi^n}{\sqrt 5}$ also fulfills
$$f(0)=0,\qquad f(1)=1,\qquad f(n)=f(n-1)+f(n-2)\text{ if }n\ge2.$$
Thus you verify $F_0=f(0)$ and $F_1=f(1)$ directly and for $n\ge 2$ you conclude (from the assumption that $F_k=f(k)$ for $0\le k<n$) that also $f(n)=f(n-1)+f(n-2)=F_{n-1}+F_{n-2}=F_n$.
