Exercise 14

Find the flaw in the following “proof” of the “fact” that $n \lt 100$ for every $n \in \N$.

Let $P(n)$ be the statement $n \lt 100$. We will prove $P(n)$ is true for all $n \in \N$. First we establish the base case: when $n = 0$, $P(n)$ is true, because $0 \lt 100$. Now for the inductive step, assume $P(k)$ is true. That is, $k \lt 100$. Now if $k \lt 100$, then $k$ is some number, like 80. Of course $80+1 = 81$ which is still less than 100. So $k +1 \lt 100$ as well. But this is what $P(k+1)$ claims, so we have shown that $P(k) \imp P(k+1)$. Thus by the principle of mathematical induction, $P(n)$ is true for all $n \in \N$.