Why are two base cases needed to prove that $n<2^n$ for all $n\geq 0\,$?

Question

So I understand more than one base case is needed when there is a recurrence relation like the Fibonacci sequence. But I don't understand why two base cases are needed in the below example. Is there somehow a recurrence in the statement or does it possibly relate back to strong induction somehow?

Answer 1

This is an interesting, and rather unfortunate, problem in a way because the answer really depends on how you interpret the question (and, of course, ambiguity is not exactly something desired in mathematics). The two possible interpretations:

1. In the proof just given (i.e., the one in your picture), why do you need the two base cases $n=0$ and $n=1$? Or:
2. Why do you need the two base cases $n=0$ and $n=1$ in order to prove that $n<2^n$ for all $n\geq 0$?

The two current answers address point (1) above, and the comment by Git Gud addresses (2). I'll try to give reasonable responses to both interpretations.

(1): You are trying to prove that $n<2^n$ holds for all $n\geq 0$, right? As SBareS notes, your induction assumption is only for values $n\geq 1$. This means that whatever you prove will only be valid for $n\geq 1$. Thus, in the proof you pictured, you need the base case $n=0$ in order for the statement you proved to be valid for all $n\geq 0$ and not just $n\geq 1$. Of course, you need the base case $n=1$ in order for your induction proof to actually be a valid induction proof. Hence, you need both base cases $n=0$ and $n=1$ in the proof you pictured.

(2): You do not need both base cases to prove that $n<2^n$ for all $n\geq 0$. In fact, the proof you have pictured is pretty bad because it is not very well-written and it also makes use of an unnecessary base case to confuse matters more. I'll outline a proof below that shows how you can prove $n<2^n$ for all $n\geq 0$ using only the base case $n=0$.

---

Proof using only one base case: For $n\geq 0$, let $S(n)$ denote the statement $$ S(n) : n<2^n. $$ Base case ($n=0$): $S(0)$ says that $0<1=2^0$, and this is true.

Induction step: Fix some $k\geq 0$ and assume that $S(k)$ is true where $$ S(k) : \color{blue}{k<2^k}. $$ To be shown is that $S(k+1)$ follows where $$ S(k+1) : k+1<2^{k+1}. $$ Beginning with the left-hand side of $S(k+1)$, \begin{align} \color{blue}{k}+1 &< \color{blue}{2^k}+1\tag{by $S(k)$, the ind. hyp.}\\[0.5em] &\leq 2^k+2^k\tag{since $k\geq 0$}\\[0.5em] &=2\cdot 2^k\tag{group like terms}\\[0.5em] &=2^{k+1},\tag{by definition} \end{align} we end up at the right-hand side of $S(k+1)$, completing the inductive step.

By mathematical induction, the statement $S(n)$ is true for all $n\geq 0$. $\blacksquare$

---

The above proof is perfectly valid, and it makes use of only the base case $n=0$.

But I don't understand why two base cases are needed in the below example.

Maybe now you can see why the two base cases are needed in the specific example/proof you showed in the picture (addressed in point (1)) but that two base cases are not needed to prove that $n<2^n$ for all $n\geq 0$ (addressed in point (2) and in the proof above).

Answer 2

You need 2 base case because in your induction step you assume that $2n=n+n\geq n+1$ thus you assume that $n\geq 1$. Hence you have to prove the cases $n=0$ and $n=1$.

Answer 3

The key is in "For $n\ge1$, also $2n=n+n \ge n + 1$". So really the induction only proves the theorem for $n\ge1$. The case $n=0$ is merely a special case (since $0<1$), not a base case.