Exercise 16

What is wrong with the following “proof” of the “fact” that for all $n \in \N$, the number $n^2 + n$ is odd?

Let $P(n)$ be the statement “$n^2 + n$ is odd.” We will prove that $P(n)$ is true for all $n \in \N$. Suppose for induction that $P(k)$ is true, that is, that $k^2 + k$ is odd. Now consider the statement $P(k+1)$. Now $(k+1)^2 + (k+1) = k^2 + 2k + 1 + k + 1 = k^2 + k + 2k + 2$. By the inductive hypothesis, $k^2 + k$ is odd, and of course $2k + 2$ is even. An odd plus an even is always odd, so therefore $(k+1)^2 + (k+1)$ is odd. Therefore by the principle of mathematical induction, $P(n)$ is true for all $n \in \N$.