# Why doesn't this induction “proof ”show $f_n = (\phi)^n + (1-\phi)^n$?

Here, $\phi$ is the golden ratio and $f_n$ is the $n^{th}$ Fibonacci number. The formula I'm using is actually the closed form of the Lucas numbers.

Let $n = 1$. Then $f_n = 1$ and $\phi + 1 - \phi = 1$. Thus, the case holds where $n = 1$, establishing our base case.

Assume the case holds for all natural numbers less than or equal to $k$. Then $f_{n+1} = f_n + f_{n-1} = \phi^k + (1-\phi)^k + \phi^{k-1} + (1-\phi)^{k-1} = \phi^{k-1}(1 + \phi) + (1-\phi)^{k-1}(2-\phi) = \phi^{k-1}\phi^2 + (1 - \phi)^{k-1}(1-\phi)^2 = \phi^{k+1} + (1-\phi)^{k+1}$. Thus the case holds where $n = k+1$. By mathematical induction, the claim holds for all $n \in N$.

However, $f_3 =2$ and $\phi^3 + (1-\phi)^3 = 4$. Why is this?

-
Those are Lucas numbers, not Fibonacci. They have initial terms $2,1$ vs. $0,1$ for fib's. –  Bill Dubuque Nov 30 '12 at 2:34

Your inductive step is just a verification that $\rm\:g_n = \phi^n + (1-\phi)^n\:$ also satsifies the fibonacci recurrence $\rm\:f_{n+2} = f_{n+1}\! + f_{n}.\,$ The solutions of such linear second-order homogeneous difference equations are uniquely determined by the initial values $\rm\,f_0, f_1,\:$ as a trivial inductive proof shows. However, your "base case" only verifies that they agree for $\rm\:n = 1.\:$ But they disagree for $\rm\:n = 0\:$ since $\rm\:f_0 = 0\:$ but $\rm\:g_0 = \phi^0 + (1-\phi)^0 = 2.\:$ These initial conditions define the Lucas numbers.

So why does your proof fail? If you examine the proof of the inductive step for $\rm\:n = 1\:$ you'll note that, to deduce the truth of the identity for $\rm\:n = 2,\:$ it employs the truth at $\rm\;n = 1\:$ and $\rm\:n = 0.\:$ However, you never proved that it is true for $\rm\:n = 0;\:$ in fact, as we saw, it is not: $\rm\:f_0\ne g_0.$

-
So for all induction proofs for the Fibonacci sequence, do we have to show two base cases? –  Max Lipton Nov 30 '12 at 3:25

Note that you've defined $f_{n+1}=f_{n}+f_{n-1}$, so to use the induction, you need to know that it holds for the previous two cases, rather than just the previous. That means that $n=0$ is also part of the base case, but $\phi^{0}+(1-\phi)^{0}=2$, which isn't the same as $f_{0}$.

-
Would it be sufficient to show the claim is true where $n = 2$, or do I need to show two base cases? –  Max Lipton Nov 30 '12 at 2:33
You need to have two established cases to work from, because in order to define $f_{n+1}$, you have to refer back to the two previous cases. If you've only established one, you've shown a worthless implication. –  Peter Nov 30 '12 at 2:41
So does this mean all induction proofs involving the Fibonacci sequence should have two base cases? –  Max Lipton Nov 30 '12 at 2:55

I'm going to try and explain the subtlety you've noticed from a different angle. For reference, I'm reprinting your argument here, naming the proposition $P(n) : F_n = \phi^n+(1-\phi)^n$.

Let $n = 1$. Then $F_n = 1$ and $\phi + 1 - \phi = 1$. Thus, the proposition $P(1)$ holds, establishing our base case.

So far, so good.

Assume that $P(k)$ holds for all natural numbers $k\leq n$. Then $F_{n+1} = F_n + F_{n-1} = \phi^n + (1-\phi)^n + \phi^{n-1} + (1-\phi)^{n-1} = \phi^{n-1}(1 + \phi) + (1-\phi)^{n-1}(2-\phi) = \phi^{n-1}\phi^2 + (1 - \phi)^{n-1}(1-\phi)^2 = \phi^{n+1} + (1-\phi)^{n+1}$. Thus $P(n+1)$ holds. By mathematical induction, we have $P(n)$ for all $n \in N$.

This uses $P(n)$ and $P(n-1)$, which on the surface looks good - but note that this requires both $P(n)$ and $P(n-1)$ explicitly. The false statement that you're relying on is the statement '$(\forall k\leq n P(k)) \implies (P(n) \wedge P(n-1))$', because this statement is ill-defined when $n=1$ (assuming that the 'base case' is $n=1$, of course, and thus $P(0)$ is technically undefined.) This means that you haven't actually shown $\forall n \bigl(\left(\forall k\leq n P(k)\right)\implies P(n+1)\bigr)$, which is what you need for your induction to work.

This should explain why virtually all Fibonacci proofs need two 'base cases' : because generally they use the induction principle $P(n-1)\wedge P(n)\implies P(n+1)$, they need both $n=1$ and $n=2$ 'base cases' to get around the issue with the definition of $P(0)$ (or alternately, $n=0$ and $n=1$ base cases).

-