F(n) is a Fibonacci number. Why do we need two base cases: $n = 3$ and $n = 4$ for the induction to prove $F(n) \geq 2^{(n-1)/2}$ for all $n \geq3?$

Question

F(n) = F(n-1) + F(n-2) is a Fibonacci number(F(1) = 1, F(2) = 1, F(3) = 2 so on...) I wonder why we need two base cases: $n = 3$ and $n = 4$ for the induction to show $F(n) \ge 2^{(n-1)/2} \;\forall n \ge 3.$ I keep thinking, but I need one base case, $n=3$. I might miss something.

I could see F(3) = 2 is true as (3)≥2 then I could assume that F(k) is true for ≥3 then I could prove $F(n) \ge 2^{(n-1)/2}$ is true for n = +1 as an inductive step. As a result, I could not find out why we need 3 and 4 instead of just 3

Answer 1

HINT: $F(2)=1$ is NOT greater than $2^{(2-1)/2}$, so you need two initial numbers $F(3)$ and $F(4)$ for the induction step.

Answer 2

Let us denote by $P(n)$ the property $F(n) \ge 2^{(n-1)/2}$. To prove $P(n)\;\forall n \ge 3$ you need "two base cases" $P(3)$ and $P(4)$ because the induction step derives $P(n+1)$ not only from $P(n)$: it also needs $P(n-1)$. This is an "induction of order 2". You can view it as a simple induction (of order 1) on $Q(n):=P(n)\land P(n+1)$. The base case is then $Q(3)=P(3)\land P(4)$, and the induction step is $Q(n)\implies Q(n+1)\;\forall n \ge 3$, or equivalently: $Q(n-1)\implies Q(n)\;\forall n \ge4$, i.e. actually $\left(P(n-1)\land P(n)\right)\implies P(n+1)\;\forall n \ge4$

Answer 3

Okay, I didn't put it into words as clearly as I thought I had.

In the induction step to prove $P(n+1)$ we have to calculate $F(n+1) = F(n) + F(n-1)$ and we need to assume not only that $P(n)$ is true, but also that that $P(n-1)$ is true. Because we have two assumptions we have to have two base cases for these assumptions.

The thing is: If you have a single base case $n= n_1$ then the "first" time you apply your induction step all you are assuming is that $n \ge n_1$. You do that step and to prove $P(n+1)$ you need to assume $P(n)$ and you need to assume $P(n-1)$. Assuming $P(n)$ is fine because $n \ge n_1$ but assume $P(n-1)$ is NOT okay because $n-1 \not \ge n_1$ for all we know. (In fact, the "first" time we do the induction step we are assuming $n = n_1$ so $n-1 < n_1$.) To handle this we need to introduce a case $n-1 = n_0$ and have the two base cases $P(n_0)$ is true and $P(n_1)$ is true. THen:

... when we do or induction step it goes like this: Assume that $P(n)$ is true and $P(n-1)$ is true (we've covered the base cases of $n=n_1$ and $n-1 = n_0$) the show that $P(n+1)$ is true.

==== edit ====

If you base case is for $n=n_1$ and you want to do an induction step you must assume $P(n)$ is true for $n\ge n_1$ and assume that implies $P(n+1)$ is true.

So if $P(n)$ is true and $n\ge n_1$, that is that $F(n) \ge 2^{\frac {n-1}2}$.

We must prove $F(n+1) \ge 2^{\frac {n}2}$. Se we try it.

$F(n+1) = F(n) + F(n-1)$. By our induction hypothesis we know $F(n) \ge 2^{\frac {n-1}2}$. And we want to know by the induction hypothesis that $F(n-1) \ge 2^{\frac {n-2}2}$ but .... we don't know that. We would know that if we knew $n \ge n_1$ but we don't know that. We are flummoxed and utterly stuck unless there is a case we can make for $P(n-1)$. But we just don't have such a case.

We need a case were $P(n_0)$ is true. ANd where $n_1 = n_0+1$ and $P(n_1)$ is true. Then we can use our induction step.

Assume we know $P(n)$ is true and $n\ge n_1$ AND assume we know $P(n-1)$ is true and $n-1 \ge n_0$.... Now our inductions step is:

$F(n+1) = F(n) + F(n-1)$ and because by one induction hypothesis, $P(n)$ is true, we know $F(n) \ge 2^{\frac {n-1}2}$ is true. An by our OTHER induction step for $P(n-1)$ we know $F(n-1) \ge 2^{\frac {n-2}2}$ so

$F(n+1)=F(n)+F(n-1) \ge 2^{\frac {n-1}2}+2^{\frac {n-2}2}> ....$ and we can finish.