Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
    
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

3 Answers 3

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

share|improve this answer
    
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}$.

share|improve this answer
    
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. –  user123123 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).

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.