3

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?

enter image description here

J_SNSD
  • 57
  • You don't need both base cases, the second one is probably unnecessary. I say probably because it might be that $0\not \in \mathbb N$ for you and you only learned the induction principle for $n\ge 1$. – Git Gud Apr 21 '15 at 09:37
  • 4
    @GitGud But you do need both base cases in the proof given in whatever text OP is using. Of course, you do not need both base cases to construct a valid proof that $n<2^n$ for all $n\geq 0$. I think whatever textbook this proof is from should be tossed in the fire. It makes use of an unnecessary base case and then it goes on to implore the reader to determine why it was necessary. Terrible pedagogy. – Daniel W. Farlow Apr 21 '15 at 13:48
  • @MagicMan LOL! That made me laugh – Valentino Apr 21 '15 at 15:58

3 Answers3

4

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

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

wece
  • 2,732
2

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.

sbares
  • 4,063
  • Its funny I did this problem just yesterday and realized this. This answer is the most simplistic and straightforward. – Valentino Apr 21 '15 at 14:08
  • 1
    @Valentino It addresses why two base cases are needed in the textbook's proof, but it does not really say anything about what seems to be bothering OP, namely why two base cases are needed at all to prove the statement under consideration. It's really the lame textbook's fault. – Daniel W. Farlow Apr 21 '15 at 14:15