Prove by induction Fibonacci equality [question:]    
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.
[end]
I've had multiple attempts at this, the most fruitful being what follows, though it is incorrect, and I cannot figure out where I am going wrong:
[my answer:]
What follows is an incorrect approach, after which comes the approach that I should have done
Inductive Hypothesis: $$F_i=\frac{\phi^i-\hat{\phi^i}}{\sqrt5}, i\in\mathbb{N}  $$   (I include 0)
Base case: $$F_0=\frac{\phi^0-\hat{\phi^0}}{\sqrt5}=0$$
Proof:
$$\begin{eqnarray*}
F_{i+1}&=&\frac{\phi^{i+1}-\hat{\phi^{i+1}}}{\sqrt5}\\
&=&\frac{\phi*\phi^i-\hat{\phi}*\hat{\phi^i}}{\sqrt5}\\
&=&\frac{\frac{1+\sqrt5}{2}*\phi^i-\frac{1-\sqrt5}{2}*\hat{\phi^i}}{\sqrt5}\\
&=&\frac{\frac{\phi^i+\sqrt5\phi^i}{2}-\frac{\hat{\phi^i}-\sqrt5\hat{\phi^i}}{2}}{\sqrt5}\\
&=&\frac{\frac{\phi^i+\sqrt5\phi^i-\hat{\phi^i}+\sqrt5\hat{\phi^i}}{2}}{\sqrt5}\\
&=&\frac{\phi^i+\sqrt5\phi^i-\hat{\phi^i}+\sqrt5\hat{\phi^i}}{2*\sqrt5}\\
&=&\frac{1}{2}\left(\frac{\phi^i+\sqrt5\phi^i-\hat{\phi^i}+\sqrt5\hat{\phi^i}}{\sqrt5}\right)\\
&=&\frac{1}{2}\left(\frac{\sqrt5\phi^i}{\sqrt5} + \frac{\sqrt5\hat{\phi^i}}{\sqrt5}
+\frac{\phi^i-\hat{\phi^i}}{\sqrt5}\right)\\
&=&\frac{1}{2}\left(\phi^i+\hat{\phi^i}+F_{i}\right)\text{   by inductive hypothesis}\\
&=&\frac{1}{2}\left(\sqrt5*...\right)\\
\end{eqnarray*}$$
Actually I just saw my error in that line (I eventually multiplied by $\frac{\sqrt5}{\sqrt5}$ and 
substituted for $F_i$, but I see that the conjugates are added there, not subtracted).
Correct approach:
$$\begin{eqnarray*}
F_{i+1}&=&F_{i} + F_{i-1}\\
&=&\frac{\phi^i-\hat{\phi^i}}{\sqrt5}+\frac{\phi^{i-1}-\hat{\phi^{i-1}}}{\sqrt5}\\
&=&\frac{\left(\phi+\hat{\phi}\right)\left(\phi^i-\hat{\phi^i}\right)-\phi\hat{\phi}\left(\phi^{i-1}-\hat{\phi^{i-1}}\right)}{\sqrt5}\text{ (see answer for why this works)}\\
&=&\frac{\phi^{i+1}-\phi\hat{\phi^i}+\hat{\phi}\phi^i-\hat{\phi^{i+1}}-\phi^i\hat{\phi}+\phi\hat{\phi^i}}{\sqrt5}\\
&=&\frac{\phi^{i+1}-\hat{\phi^{i+1}}-\phi\hat{\phi^i}+\phi\hat{\phi^i}-\hat{\phi}\phi^i+\hat{\phi}\phi^i}{\sqrt5}\\
&=&\frac{\phi^{i+1}-\hat{\phi^{i+1}}}{\sqrt5}\\
\text{Q.E.D., punk problem.}
\end{eqnarray*}$$
From what I searched on the web, there is no available source proving this of the Fibonacci sequence - all
inductive hypothesis proofs prove the actual sequence with induction. 
Bill, it's always easy to forget about the inherent properties of special numbers... I didn't even realize $\phi$ + $\hat{\phi}$ = 1 in your first hint, as well as the multiplication, until you pointed it out.
Alex, I'm sure that going through the problem that way will produce the result, also, but with Bill's, it's much faster.  
Thanks for the help.
 A: You can't start from $F_{i+1}=\frac{\phi^{i+1}-\smash{\hat{\phi}}^{i+1}}{\sqrt5}$ as that's what you're trying to prove. Rather, the proof should start from what you have (the inductive hypothesis) and work from there. Since the Fibonacci numbers are defined as $F_n=F_{n-1}+F_{n-2}$, you need two base cases, both $F_0$ and $F_1$, which I will let you work out. The induction step should then start like this:
$$\begin{eqnarray*}
F_{i+1}&=&F_i + F_{i-1}\\
&=&\frac{\phi^i-\smash{\hat{\phi}}^i}{\sqrt5}+\frac{\phi^{i-1}-\hat{\phi}{}^{i-1}}{\sqrt5}\\
\end{eqnarray*}$$
which is hopefully enough of a hint to get you started.
Edit: Here is a more worked-out version. I made a typo in my comments.
$$\begin{eqnarray*}
F_{i+1}&=&F_i + F_{i-1}\\
&=&\frac{\phi^i-\smash{\hat{\phi}}^i+\phi^{i-1}-\hat{\phi}{}^{i-1}}{\sqrt5}\\
&=&\frac{(\smash{\hat{\phi}}^2-\hat{\phi})\phi^{i+1}-(\phi^2-\phi)\smash{\hat{\phi}}^{i+1}}{\sqrt5}\\
\end{eqnarray*}$$
A: HINT $\rm\quad \phi^{\:n+1}\!-\:\bar\phi^{\:n+1}\ =\ (\phi+\bar\phi)\ (\phi^n\!-\:\bar\phi^n)\ -\ \phi\:\bar\phi\ (\phi^{\:n-1}\!-\:\bar\phi^{\:n-1})$
Therefore, upon substituting $\rm\ \phi+\bar\phi\ =\ 1\ =\ -\phi\bar\phi\ $ and dividing by $\:\phi-\bar\phi = \sqrt 5\:$ we deduce $\rm\ \ldots$
REMARK $\ $ To understand the essence of the matter it's worth emphasizing that such an inductive proof amounts precisely to  showing that $\rm\:f_n\:$ and  $\rm\: \bar{f}_n = (\phi^n-\bar\phi^n)/(\phi-\bar\phi)\:$ are both solutions of the difference equation (recurrence) $\rm\ f_{n+2} = f_{n+1} + f_n\:,\:$ with initial conditions $\rm\ f_0 = 0,\ f_1 = 1\:.\:$ The (trivial) induction simply proves the uniqueness of such solutions. It will prove quite instructive to structure the proof from this standpoint. It will also mean that you can later reuse this uniqueness theorem for recurrences.
Generally, just as above, uniqueness theorems provide very powerful tools for proving equalities - a point which I emphasize in many prior posts. For example, see my prior posts on telescopy and the fundamental theorem of difference calculus, esp. this one.
A: F0 = 0 holds. F1 = 1 holds. Assume that Fk = φk−ˆ φk √5 holds ∀k < n. Fn = Fn−1 + Fn−2 by deﬁnition of Fn. Fn = φn
−
1
− ˆ φn
−
1 √5 + φn
−
2
− ˆ φn
−
2 √5 by induction. Let’s verify an identity:
φi−1 − ˆ φi−1 + φi−2 − ˆ φi−2 = (1 + 1+√5 2 )φi−2 −(1 + 1−√5 2 )ˆ φi−2 = 4+2+2√5 4 φi−2 − 4+2−2√5 4 ˆ φi−2 = 1+2√5+5 4 φi−2 − 1−2√5+5 4 ˆ φi−2 = (1+√5 2 )2φi−2 −(1−√5 2 )2 ˆ φi−2 = φi − ˆ φ2 We conclude that Fn = φn−ˆ φn √5 , which is, the induction hypothesis holds for n too. By induction the equality holds for all n ≤ 0
