[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.