User:IssaRice/Faulty mathematical induction proof example

Problem statement

Consider the following "proof":

Proposition. Let $b,c$ be positive integers. Then $bc>b$.

Proof. We fix $b>0$ and induct on $c$. For the base case when $c=0$, the result is vacuously true. Now suppose inductively that we have the result for $c$. Then for $c+1$ we need $b(c+1)>b$. But $b(c+1)=bc+b>bc$ since $b>0$. Also, $bc>b$ by induction hypothesis. Therefore, $bc+b>bc>b$. This closes the induction.

This proposition is obviously false, since for $c=1>0$ we have $bc=b$, not $bc>b$. The problem is to figure out where the induction "proof" above goes wrong.

Diagnosis

The problem with the proof above is that we are inconsistently bringing in the hypothesis $c>0$. This means that we are "doing induction" but without a fixed predicate $P(c)$, which makes the proof invalid.

When proving the vacuous case, we say that it is vacuously true. This makes it sound like the predicate is $P(c)$ = "if $c>0$, then $bc>b$". With this P in hand, we indeed have that P(0) is true.

But now when we get to the induction case, the induction hypothesis isn't that $bc>b$. Instead, the IH is that if $c>0$, then $bc>b$. So we can't use $bc>b$ without first checking that $c>0$.

Now we need to show that if $c+1>0$ then $b(c+1)>b$. Actually, when showing an implication, it's ok to just show the consequent. And in any case, $c+1>0$ is true for any natural number $c$, so we aren't gaining any new information. So we need to show $b(c+1)>b$. Now, if $c>0$, then we can go through the same steps as in the faulty proof to conclude that $b(c+1)>b$. What if $c=0$? In this case, we can't use the induction hypothesis, and what we are trying to show is that $b1>1$, which is nonsense.

On the other hand, if we had used the predicate $P(c)$ = "$bc>b$" then the base case wouldn't have gone through.

See also

• User:IssaRice/An induction proof that does not use the induction hypothesis