Paradox of proof by induction

Question

I'm having trouble understanding the following situation: Given an identity P(n) that is wrong (but I don't know whether it's right or wrong), I am trying to check whether this identity can be proven using induction. I find that the base case of n=k is to be true for P(k). Now I attempt to show that P(n) -> P(n+1) and since P(n) was a false statement, it turns out that implication comes out to be true (since if P is false P->Q can still be true). Now I have shown that base case for n=k is true and P(n)->P(n+1) is true. So by induction, I conclude that P(n) is true (which is actually wrong). Why is this paradox occurring?

Answer 1

I was initially really confused by your claim that '$P(n)$ is wrong' in conjunction with your claim that 'the base case $P(n)$ is true for $n=k$'. That is: how can you say that $P(n)$ is wrong ... and yet it is also (at least for the case $n=k$ also true?

But I am guessing that when you say that '$P(n)$ is wrong', you have something in mind like:

$P(n):$ $n = n^2$

which is indeed wrong in general, but still is true for the base case $n=k=0$

So: when you say that '$P(n)$ is wrong', you really mean to say that $\forall n \ P(n)$ is wrong!

But that is a totally different claim from saying that the $P(n)$ as part of the claim $P(n) \to P(n+1)$ is wrong.

That is, when we do an inductive proof, and make the inductive hypothesis/assumption that $P(n)$ is true, what we are really claiming that $P(n)$ is true for some arbitrarily chosen number $n$. And note: in a case like this, whether $P(n)$ is actually true depends on what this arbitrarily chosen $n$ is: if $n=0$, then $P(n)$ is true, but for $n \neq 0$, it is not true.

Therefore, when you say that we can set $P(n) \to P(n+1)$ to true 'because $P(n)$ is wrong', you are making a mistake: For $n=0$, we have that $P(n)$ is true. And, since in that case $P(n+1)$ is false, we in fact have that $P(n) \to P(n+1)$ is false, breaking the inductive proof ... and thus resolving the paradox that you perceive.

But yes, the basic mistake you are making is that you are confusing $P(n)$ with $\forall n \ P(n)$

And this is in fact a really common confusion I see when it comes to induction. That is, I frequently see people claim that induction is circular by claiming that the inductive assumption is exactly the same as the ultimate claim that we are trying to prove. But again, the former is the claim that $P(n)$ is true for some arbitrarily picked $n$, whereas the latter is the claim $\forall n \ P(n)$, which are two different things.

Answer 2

After having proved that $P(k)$ holds, the next step is to prove that, for every $n\geqslant k$, $P(n)\implies P(n+1)$. Simply proving that for one specific $n$ you have $P(n)\implies P(n+1)$ (which is what you did) is not enough.

Answer 3

I think you are confused about what the "base case" means.

Suppose (for example) that $P(n)$ is the statement $$ n = n+1 . $$

The assertion $$ P(n) \text{ implies } P(n+1) $$ is true for two good reasons. The first, as you you note, is that the antecedent is false, so the implication is true. But that does not imply the truth of $P(n+1)$, just the truth of the implication.

The second reason is simple algebra. Add $1$ to both sides to arrive at $$ n = n+1 \implies n+ 1 = (n+1) + 1. $$

So the inductive step is fine. But there is no true "base case" to get things started: $P(1)$ is false, so chain of correct implications $$ P(1) \implies P(2) \implies P(3) \implies \cdots $$ is useless.