10
$\begingroup$

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

  • 1
    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$2011-12-29

3 Answers 3

1

F0 = 0 holds. F1 = 1 holds. Assume that Fk = φk−ˆ φk √5 holds ∀k < n. Fn = Fn−1 + Fn−2 by definition 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

  • 0
    When you display mathematics on the site, you should use $\LaTeX$ to make it more readable. A simple explanation is here: http://meta.math.stackexchange.com/questions/107/faq-for-math-stackexchange/117#117, and you can find many guides elsewhere online.2013-03-27
5

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

  • 0
    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.2011-12-29
5

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.