In mathematical induction, how does assuming $P(n)$ differ from assuming $\forall n : P(n)$?

Question

In mathematical induction,* one first proves the base case, $P(0)$, holds true. In the next step, one assumes the $n$^th case** is true, but how is this not assuming what we are trying to prove? Aren't we trying to prove any $n$^th case** is true? So how can we assume this without employing circular reasoning?

I am not asking how to prove mathematical induction is true, but how mathematical induction is in accordance with rules of logic that do not admit circular reasoning as valid.*** Specifically, I am asking how, in the second step of induction, one does not assume what one is trying to prove.

In other words, as @DanielV put it below,

how does assuming $P(n)$ differ from assuming $\forall n : P(n)$?

---

^{*C. S. Peirce preferred to term it "Fermatian inference."
**=$(P(n))$ or $(\forall n : P(n))$ at this step?
***There are some logics that admit circular reasoning, which Aristotle refutes in his Posterior Analytics book 1, 72b-73a20, "by showing that circular demonstration is not acceptable".}

Answer 1

Here is another example. Suppose you were asked to establish "if n is larger than 10, then n is larger than 5". Seems pretty straightforward.

What is the first thing you do? Assume "n > 10". But wait, isn't that assuming every number is greater than 10? No. Same thing with induction: assuming P(n) isn't the same as assuming P holds for every n, it is merely restricting your consideration to those n for which P holds.

The only time you can generalize from $P(n)$ to $\forall n : P(n)$ is when there are no assumptions containing the variable $n$. Which is exactly the opposite of what you do with induction: your first step is to create an assumption containing $n$.

Answer 2

There are two equivalent common formulations of the second step: one is to assume that the claim is true for $n$ and trying to prove it's true for $n+1$. The other is to assume it's true for $n-1$ and try to prove it for $n$. Either way, we are not assuming what we're trying to prove, we're assuming the case before what we're trying to prove.

Perhaps a more intuitive way to explain the induction technique is that we're demonstrating that there cannot be any counterexamples. We do this by showing that no case can be the lowest counterexample; neither the base case, nor any case after that. The axiom of induction that others have referenced says that this absence of a lowest counterexample is enough to conclude that the statement is true in all cases.

Answer 3

I think there are two related but, as we will see, distinct worries expressed by the OP:

A. The inductive hypothesis that you use in the proof by (weak) induction seems to say exactly what you are trying to prove with induction.

B. As such, proofs by induction seem to be circular.

Let me address both of these worries:

Worry A

No, the inductive hypothesis is not the same as what induction is trying to prove.

To see this, note that for the inductive step we are trying to prove that $\forall n (P(n) \rightarrow P(n+1))$.

We do this by letting $n$ be some arbitrary number, and then we assume $P(n)$ as our inductive hypothesis (for weak induction, that is). Once we then show that $P(n+1)$, we conclude (by conditional proof) that $P(n) \rightarrow P(n+1)$. And finally, we use universal proof to say that since $n$ was arbitrary, $\forall n (P(n) \rightarrow P(n+1))$. Here is what it looks like formally:

Notice that the inductive hypothesis $P(a)$ (sorry, the software requires me to use $a$ instead of $n$) that we assume on line 4 is really quite different from the claim that $\forall x P(x)$ (again, sorry, the software requires me to use $\forall x P(x)$ instead of $\forall n P(n)$) that you end up with at the end of your inductive proof on line 10.

Indeed, if the inductive hypothesis was that $\forall n P(n)$, then we could immediately conclude that $P(n+1)$! But that doesn't happen of course. All we assume is that $P(n)$, so it will take some work to go from there to $P(n+1)$.

Worry B

Again, you don't have to worry. Please note the following important distinction between two kinds of assumptions:

1. Assuming something as an original premise at the start of the proof

2. Making additional assumption during your proof (as part of, say, a conditional proof or proof by contradiction).

If we were to assume $\forall n P(n)$ as an original premise, then yes, we would be doing circular reasoning by using that to prove $\forall n P(n)$.

But if we assume $\forall n P(n)$ as an additional assumption to set up, say, a conditional proof, then all we are going to get from that is a conditional of the form $\forall n P(n) \rightarrow \phi$ with $\phi$ being whatever you would be able to infer with the use of this additional assumption $\forall n P(n)$. You would not get $\forall n P(n)$ by itself out of that, and so no, doing that is not circular reasoning ...

As the skeleton above shows, the inductive step follows the latter pattern, as it assumes $P(n)$ as an additional assumption, not as an original assumption.

In fact, as a special case, we could of course conclude $\forall n P(n)$ on the basis of $\forall n P(n)$ within a conditional proof... but all it would give us is in the end is $\forall n P(n) \rightarrow \forall n P(n)$, which is an information-less tautology, and not at all the same as $\forall n P(n)$. Likewise, in the proof skeleton above I could of course infer $P(a)$ (instead of $P(a+1)$) on the basis of the assumption $P(a)$, but all that would give me in the end is $\forall x (P(x) \rightarrow P(x))$, which is yet again a meaningless tautology.

In sum, then, the inductive assumption is not the same claim as the claim that we are trying to prove, and even if it were, it would still not be circular reasoning. So both worries are nothing to worry about!

Finally, while nothing to worry about, I can certainly understand your worries about weak induction, because it feels like we're proving that "any arbitrary $n$ has property $P$ by at some point assuming that some arbitrary $n$ has property $P$"! Is there maybe a way to get rid of, or at least alleviate, this feeling of circularity?

In think there is, and in order to do so, let me first point out that strong induction does not have this same feeling of circularity, as its inductive assumption is 'suppose $P(m)$ is true for all $m$ smaller than $n$'. That is, by making reference to the numbers other than $n$, one does not get the feeling that we are somehow proving that $n$ has property $P$ assuming $n$ has property P.

But notice that the inductive step in weak induction can be understood this way as well: we show that a number $n$ has property $P$ on the basis of its previous number having property $P$. Therefore, I think it may help to alleviate feelings of circularity by characterizing the weak induction step as going from $n-1$ to $n$ (for $n>0$ of course), rather than as going from $n$ to $n+1$. Same idea of course, but maybe a little easier to accept conceptually.

Answer 4

In the inductive step, you don't prove $P(n)$ is true for all $n$ supposing it's true, you prove only $$\forall n,\;P(n)\implies P(n+1)$$ which is not the same thing.

Actually to prove the implication is true, you do as for any implication $\;A\implies B$ proof: you add (temporarily) $A$ to the axioms of mathematics, and you deduce $B$ from this completed set of axioms. From the rules of mathematical logic, $A \implies B$ is proved.

Answer 5

The non-circularity may become clearer if you look in more detail at what gets proved, namely, first "$P(1)$", and second "for all $n$, if $P(n)$ then $P(n+1)$". Let me write out carefully some of what's included in the second part:

If $P(1)$ then $P(2)$. (That's the special case where $n$ is 1.)

If $P(2)$ then $P(3)$. (That's the special case where $n$ is 2.)

If $P(3)$ then $P(4)$. (That's the special case where $n$ is 3.)

Of course, the general statement that was proved, "for all $n$, if $P(n)$ then $P(n+1)$" includes infinitely many more implications like the three that I just wrote out, but let me, for a while, work with just those three implications.

The basis step, proved as part of the induction proof, ensures that $P(1)$ is true. Once we know that, the first implication that I wrote out ensures that, as a consequence, $P(2)$ is also true. Once we know $P(2)$, the second implication that I wrote out ensures that $P(3)$ is also true. Once we know $P(3)$, the third implication ensures that $P(4)$ is also true.

So the basis of the induction and the three special cases of the induction step that I wrote out ensure that all four of $P(1),P(2),P(3),P(4)$ are true, since they can be deduced one after the other.

If I had been more patient and had written out ten implications instead of just 3, using the induction step for $n$ going from 1 up to 10, then the same idea, using the implications one after another, would show that $P(n)$ is true not only for $n$ up to 4 (as I showed above) but for $n$ up to 11.

Using more and more special cases of the induction step, you'll get enough implications to prove $P(n)$ for any natural number $n$ that you want. For example, if you want $P(1,000,000)$ then you'll need to use 999,999 such implications, one after the other.

This would get terribly boring, but, once you see the general pattern (which I hope my three implications have made clear enough), you can understand that $P(n)$ must be true for all natural numbers $n$.

The induction principle says that, instead of using the implications one at a time to get $P(n)$ for larger and larger $n$ (and needing infinitely many steps to take care of all values of $n$), you can infer from the general pattern of these implications that you could get to any $n$ that you want. In other words, you can conclude that $P(n)$ is true for all natural numbers $n$.

Answer 6

Imagine the game you can play with domino tiles called domino show, where you place the domino tile in a row and then, by pushing over the first tile, triggering a chain reaction which will push over the next tile and so on until all tiles have fallen.

Now, for the sake of argument, imagine you have infinitely many domino tiles. More precisely, imagine that the row of dominos has still a first tile, but then goes on forever.

Now, let's pick any of the domino tiles. You would most likely agree when I say

If this tile fell, then the next one would also fall.

However, would you agree with saying the following?

All tiles will fall.

The point here is: the first statement is conditional. It doesn't say something is actually happening. It just says, if something were to happen, then something else would happen.

On the other hand, the second statement is not conditional. It just says something will happen. However, you lack some information to actually conclude this. Here, the missing fact is the following: Whether or not somebody actually pushes over the very first tile.

This is also how induction works and how the universal statement in the premise and the universal statement in the conclusion differ. The first one is conditional, the second one isn't. And, you need one additional bit in the premise to actually arrive at the conclusion. Actually, I sometimes prefer the following (logically equivalent) version of the induction axiom: $$ \left(\forall n. A(n) \rightarrow A(n+1) \right) \rightarrow \left( A(0) \rightarrow \forall n A(n)\right) $$

Some final note: As others have mentioned, induction typically is one of Peano's axiom for natural numbers, so it doesn't require proof, but can rather be considered one of the properties of natural numbers. If you are working in different frameworks, e.g., set theory, you may see induction on an even larger class of structures, namely well-orders, where it more or less follows directly from the definition.

Answer 7

I see that there are lots of great answers here but allow me to add something here.

The OP asked

how does assuming $P(n)$ differ from assuming $\forall n. P(n)$.

Here is a straight answer.

When you assume $P(n)$ you are saying something like let consider an object, let's call it $n$, and suppose that for this specific $n$ the property $P(n)$ is true.

On the other hand when you assume $\forall n. P(n)$ you are saying let's suppose that $P(n)$ is true for all possible $n$'s.

So assuming $P(n)$ you are assuming the property $P$ holds for a $n$ (a generic $n$ not well specified), assuming $\forall n. P(n)$ you are assuming that the property $P$ holds for all possible $n$'s.

Hope this addresses your doubts.