Prove by induction Fibonacci equality

Solution 1:

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.

Solution 2:

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

Solution 3:

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