When do you need to prove more than 1 base case in the Fibonacci problem?

Question

I was trying to prove that if $F_n = F_{n-1} + F_{n-2}$ and $F_1 = 1$ and $F_2 = 1$, then the following proposition $P(n)$ was true $\forall n : \sum^n_{i=1}F_i=F_{n+2} - 1$

The issue I have with the proof is that I was told I need to prove two base cases $P(1)$ and $P(2)$. However, I didn't understand why it was necessary in this case. I do understand strong induction conceptually; where you can use any $P(k), k \leq n$ to aid you to conclude that $P(n+1)$. However, I just don't see how strong induction relates to my Fibonacci problem or why we need two base cases.

This is what I had so far: Show true for base case $P(1) : \sum^1_{i=1} F_i = 1 = F_3 -1 = 2-1 =1$

I.H (Induction Hypothesis) P(n) : $\sum^n_{i=1}F_i=F_{n+2} - 1$

Now, lets show $P(n) \implies P(n+1)$: $$P(n+1)$$ $$\sum^{n+1}_{i=1} F_i = \sum^n_{i=1} F_i + F_{n+1}$$ using I.H. (Induction Hypothesis) is true (i.e. P(n) is true): $$=F_{n+2} + F_{n+1} - 1$$ Using the definition of a Fibonacci number $F_i = F_{i-1} + F_{i-2}$ $$F_{n+3} - 1$$

Which concludes proof.

In the argument I provided above I do not see at which step I ever require to conjure up two base cases. I only used $P(n)$ was true to conclude $P(n+1)$, so I don't see why It's strictly necessary to justify $P(1)$ AND $P(2)$.

Do I need two base cases or not? (regardless of which two they might be, P(0) or P(1) etc...do I need 1 or 2 base cases for my proposition?)

Answer 1

Your proof is correct. What you should worry about here is using the recursion relation $F_m = F_{m-1} + F_{m-2}$ for too small values of $m$; it is valid only for $m\geq3$ (I'm renaming to avoid future confusion). Now you are doing the induction step for all $n\geq1$ (since you check only $P(1)$ explicitly). This means you can apply the recurrence relation safely only for $m\geq n+2$, which is ensured to be at least $3$. It turns out you are actually using it for $m=n+3$, so that's safe.

It is interesting that you have a unit to spare. That suggests you could go even further and take $P(0)$ as starting case instead of $P(1)$. Indeed $P(0)$ reads $$ \sum_{i=1}^0F_i=F_2-1, $$ which is perfectly meaningful (since the sum is empty, and in particular never uses $F_0$) and true (since $F_2=1$). Now your induction step can be applied to deduce $P(1)$ from $P(0)$. $$ \sum_{i=1}^1F_i=\sum_{i=1}^0F_i+F_1 \overset{I.H}=F_2-1+F_1=F_3-1 $$ where the last step uses the valid recursion $F_1+F_2=F_3$. No sweat!

You may also remark that this never uses the given starting value $F_1$. So the statement remains true for every Fibonacci-like sequence, obeying the same recurrence relation, but replacing $F_1$ by any fixed value; for instance you could take the Lucas numbers with shifted index, starting $l_1=2,l_2=1$. And finally the value $F_2=1$ only serves to make $F_2-1=0$ in the starting case of the recurrence. If we replaced the constant $1$ by the constant $F_2$ even that would be automatic, giving (with the same proof):

Whenever a sequence of numbers $(a_i)_{i\geq 1}$ satisfies the recurrence relation $a_{i+2}=a_i+a_{i+1}$ for all $i\geq1$, one has $\sum_{i=0}^na_i=a_{n+2}-a_2$ for all $n\geq0$.

Answer 2

Your proof seems correct.

I think the reason why someone told you that you need two base cases is that since $F_n$ depends on $F_{n-1}$ and $F_{n-2}$, if you want to prove something about $F_n$ you often want to use the induction hypothesis on $F_{n-1}$ and $F_{n-2}$, which requires two base cases (for example, if you want to prove that the explicit formula for $F_n$ is correct).

In your prove above, you really only need $P(n)$ to prove $P(n+1)$ (you can easily check this by trying whether your prove works for $n = 1$; if so, then you automatically prove the "second base case").

Answer 3

Who told you two base cases are necessary? If it was the professor, he may have some other concept he's trying to teach you. For example, if practicing strong induction is the real goal this proof misses the point.

If another student said two base cases are necessary, it may be based on a superficial examination of the problem. At first glance, the fact $F_{n}$ relies on both $F_{n-1}$ and $F_{n-2}$ may suggest two base cases. With a clear distinction in one's mind separating P(n) from $F_n$ as you have demonstrated eliminates the wish for the 2nd base case. Certainly some proofs for the same problem could require two base cases, but with the above proviso, I believe your proof is valid as written.

Considering the instructions, I would pay lip service to $P(1)$ and $P(2)$. Adding the lines-

P(1) is proven.
P(n) implies P(n+1)
So P(2) is true. are sufficient.