In proof by induction, what happens if P(n) is false for a specific case or the base cases are false? Can we still deduce meaningful conclusions?

The principle of mathematical induction works basically because of the following:

If we have a predicate $P(n)$, then if we have:

P(0) is true, and

P(n) $\implies$ P(n+1) for all nonnegative integers n,

then:

P(m) is true for all nonnegative integers, m.

However, I was concerned what if $P(n)$ is false or what if the base cases were false, what that would mean about $P(n+1)$.

I think I know the answer to my question but I wanted to check the answer with the community.

Say that we know $P(n_0)$ is false. Thus, the implication $P(n_0) \implies P(n_0+1)$ is true vacuously (from the definition of implies). However, our goal in induction is to establish the truth about some implication $P(n)$ for as many n as we can. However, since $P(n_0)$ is false, then from the truth table of an implication $P(n_0) \implies P(n_0 + 1)$ remains true regardless of the truth value of $P(n_0 + 1)$. Thus, even though the implication is true, we are unable to conclude anything about $P(n_0+1)$ (or any other value of n > n_0) because $P(n_0 + 1)$ might be either true or false. The goal was to establish the truth about $P(n_0+1)$, but since we can’t establish which fact is true it (about $P(n_0+1)$), then we cannot continue reasoning about values of $n \geq n_0 + 1$.

Is this correct? Is this why if we have a false statement we cannot have a proof by induction that proceeds correctly? Related to this question, if we find a case were $P(n_0) = False$ but then $P(n_1) = True$ for $n_1 > n_0$, can we still hope to show $P(n_0)$ for $n > n_0$? What about the other way round, if $P(n_0) = True$ but then $P(n_1) = False$, $n_1 > n_0$? Can we still hope induction to help us deduce anything meaningful?

Solutions Collecting From Web of "In proof by induction, what happens if P(n) is false for a specific case or the base cases are false? Can we still deduce meaningful conclusions?"

If $P(n_0)$ is false then the implication $P(n_0) \implies P(n_0+1)$ is true (vacuously, as you’ve pointed out), however, we cannot deduce the truth or otherwise of $P(n_0+1)$ in this case.

The hardest part in a proof by induction is proving $P(n) \implies P(n+1).$ If you’ve proved this, then all you have to do is find a suitable $n_0$ such that $P(n_0)$ is true. If $P(n_0)$ is false, but $P(n) \implies P(n+1)$, then pick a different value for $n_0$ (assuming that one exists). If you can find just one such $n_0$ (and if you’ve proved that $ \forall n, P(n) \implies P(n+1)$, then $P(n)$ is true for all $n \geqslant n_0$, by the principle of mathematical induction.

In this case, pick a different value of $n_0$ until $P(n_0)$ is true.

Regarding your last sentence, if $P(n_0)$ is true and $P(n) \implies P(n+1)$, then, by the property of implication, $P(n_0+1)$ is true, as is $P(n_0+2), P(n_0+3), …$, so you’d never have $P(n_1)$ being false (for any $n_1 \geqslant n_0$)!

What you’ve said is correct, but it’s not the usual way that we deal with “false cases”.

Consider the statement $P(n)$ that says
$$
3\ln(1 + n) < n.
$$
You might try proving this is true for every $n$, but you’d fail: it’s false for $n = 0$ and $n = 1$. This is fairly common: namely, it’s often the case that for finitely many values of $n$, $P(n)$ is false. Clearly you therefore can’t prove $P(n)$ true for all $n$. You can, however, often find some $n_0$ with the property that all the “bad” $n$s are less than $n_0$. In the example, $n_0 = 6$ works.

So you typically prove instead that the statement is true for all $n > n_0$.

Alas, the principle of induction doesn’t apply directly.

The usual subterfuge is to consider a new $S(n) = P(n + n_0)$. (So $S(0)$ says that $P(n_0)$ is true, and $S(1)$ says that $P(n_0 + 1)$ is true, and so on.)

The principle of induction then applies to the statments $S(n)$, for $n = 0, 1, …$ and from their truth, you can deduce the truth of $P(n)$ for $n = n_0, n_0 + 1, n_0 + 2, \ldots$.

If the base case is false, then you can’t prove anything. The basic idea of induction is that the two steps mean that $P(0)$ is true, and $P(0)\implies P(1)$, so $P(1)$ is true, and $P(1)\implies P(2)$, so $P(2)$ is true, etc. So “induction” encodes our intuition that this is enough to prove it for every natural number.

If you’ve proved $P(0)$ and $\forall n(P(n)\implies P(n+1))$ then you can’t get any natural number $n$ for which $P(n)$ is false. That is the nature of induction.

Essentially, induction can be seen as a computer program which can take a number $n$ and product a finite proof of $P(n)$.

But without the initial step, then entire thing falls apart. For example, “Every natural number is even and odd”, written as:$$P(n):=\exists k(n=2k)\land \exists \ell(n=2\ell+1)$$ is clearly false, but we can prove $P(n)\implies P(n+1)$. Since $P(0)$ is not true, we can’t prove it.

Note that you aren’t really “assuming $P(n)$ is true,” except as part of proving that $\forall n: P(n)\implies P(n+1)$. You are just saying “if $P(n)$ is true, then $P(n+1)$.” The natural of implications is that you want to deduce $P(n+1)$ from the assumption that $P(n)$ is true. So it doesn’t matter if $P(n)$ is true here, as my example above shows.