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.

Let $P(i)$ be the proposition $$\text{The $i$th Fibonacci number is: } F_i = \frac{\phi^i - \hat{\phi}^i}{\sqrt{5}}.$$ To use induction, we must check that it is true for $i=1$. Then, assume that $P(i)$ is true. One must show that $P(i+1)$ is true by using this assumption.
The $i$th Fibonacci number has a definition via a recurrence relation:
$$ F_{i+1} = F_i + F_{i-1},$$
with $F_0 = F_1 = 1$. This definition is the key to solving the last step in the above induction proof. Note that $\phi = (\sqrt{5}+1)/2$ and $\hat{\phi} = (\sqrt{5}-1)/2 = \phi-1$.
These clues hopefully put you on the right track.
