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.
 A: 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$.
A: 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.
