# 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:

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.

-
You have to use the fact that $\phi$ and $\hat\phi$ are the roots of the equation $$x^2=x+1.$$ Given that the sequence is defined with a recurrence relation involving two preceding numbers, your induction must use that too. Check both $F_0$ and $F_1$ to get started. –  Jyrki Lahtonen Dec 29 '11 at 18:08
Letting $G_i=\frac{\phi^i-\smash{\hat{\phi}}^i}{\sqrt5}$ prove that $G_0=0$, $G_1=1$ and for $n>0$ that $G_{n+1}=G_{n}+G_{n-1}$. Then use induction to prove that $G_n=F_n$ –  Thomas Andrews Dec 29 '11 at 18:32

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.

-

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*}$$

-
I actually tried that method and worked through a page before it got ridiculous. I'll go ahead and start modifying my question to show my approach from that direction. As a side note, shoot, I remember making that same mistake last year (approaching it with what I'm trying to prove) - So it's wrong, I know, but shouldn't I still be able to break this down into F sub i somehow (reverse-prove it?) –  twmb Dec 29 '11 at 18:14
I'm sure your approach would work, however, in looking at Bill's hint, the numbers magically come together out of the properties of $\phi$, which is easier (and cool). –  twmb Dec 29 '11 at 19:01
@twmb Well the answer pops out of the last line since $\smash{\hat{\phi}}^2-\hat{\phi} = \phi^2-\phi = 1$. –  Alex Becker Dec 29 '11 at 19:03
I wish I could award two correct answers. I like Bill's method more just because using cool ways to get 1 always impress me, however your method (yet again, I forgot about the $\phi^2-\phi=1$ property when I wrote that last comment) is also very clear to see. –  twmb Dec 29 '11 at 19:07

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

-
When you display mathematics on the site, you should use $\LaTeX$ to make it more readable. A simple explanation is here: meta.math.stackexchange.com/questions/107/…, and you can find many guides elsewhere online. –  Stahl Mar 27 '13 at 19:12