Does induction really avoid proving an infinite number of claims?

Question

I am teaching calculus $1$ this semester, and I saw the following motivation for using induction by another teacher:

Since we can't go over "manually proving" all claims $1,2,\ldots$ and actually get to the finish line in a finite time, we use induction to prove "all the claims at once".

But this motivation feels a bit inaccurate and dishonest to me, since proving the "induction step" $T(n) \Rightarrow T(n+1)$ also amounts to proving an infinite number of claims, one for each $n$.

So, we don't really avoid the need to prove some claim $P(n)$ for all $n$ at once, by some argument.

Thus I guess that a more refined presentation would be like this: We have a sequence of claims we want to prove $T(n)$. It may be hard to this directly for an arbitrary $n$, so we instead "replace" $T(n)$ with another sequence of claims $T(n) \Rightarrow T(n+1)$ which we can prove "once and for all" (and $T(1)$ of course).

I think most students won't notice the subtle "sweeping under the rug" here, if not explicitly stated, but I think it can be beneficial to remark honestly on what we are actually doing here. On the other hand this might confuse them unnecessarily.

What do you think?

Answer 1

The "avoidance of proving an infinite number of claims" explanation for the need for induction has not yet resonated with me because there are obviously many universally quantified statements over infinite domains that are proven without induction (e.g., for all $n \in \mathbb{N}$, if $n$ is divisible by 4, then $n$ is even).

Instead, they might think of it as an approach to enabling repeated application of some step in a way that makes it clear what inference rules are being used. Here's an example starting with a student's flawed proof from a previous question.

In an Advanced Calculus course, students were asked to prove $|a_1+a_2+...+a_n|≤|a_1|+|a_2|+...+|a_n|$ for $n$ real numbers $a_1,a_2,...a_n$.

I am teaching assistant for this course, and one of my students replied like this: $|a_1 + a_2|≤|a_1|+|a_2|$ by triangular inequality. Then, $|a_1+(a_2+...+a_n)|≤|a_1|+|a_2+...+a_n|$ $|a_1|+|a_2+(a_3+...+a_n)|≤|a_1|+|a_2|+|a_3+...+a_n|$

Repeating this, $|a_1+a_2+...+a_n|≤|a_1|+|a_2|+...+|a_n|$

The student recognizes that the base case is just the triangle inequality for two real numbers (assuming this has been proven in the course and can just be cited if the hypotheses are true and that the $n=1$ case is trivial). Even though it is intuitively clear in this case that "repeated application of the triangle inequality" is the crux of the idea, what formally valid inference rules are being applied in the "repeating this" step?

We can get around this by assuming $P(n)$, introducing one extra real number labeled $b$: $$ \begin{align} |a_1+a_2+ \cdots +a_{n+1}| &= |b + a_{n+1}| &(\text{Sum of real numbers is real}) \\ |a_1+a_2+ \cdots +a_{n+1}| &\leq |b| + |a_{n+1}| &(\text{Triangle Inequality for Two Real Numbers}) \\ |b| &\leq |a_1| + \cdots + |a_n| &(\text{Assumption: P(n)}) \\ |b| + |a_{n+1}| &\leq |a_1| + \cdots + |a_n| + |a_{n+1}| &(\text{Add a real number to both sides}) \\ |a_1+a_2+ \cdots + a_{n+1}| &\leq |a_1| + \cdots + |a_n| + |a_{n+1}| &(\text{Transitivity of Order Relation}) \\ \end{align} $$

Then, it bears repeating to the students that we have two facts:

1. The base case, $P(1)$ (trivial) or $P(2)$ (triangle inequality for two real numbers).
2. $\forall n (P(n) \implies P(n+1))$

and from these facts we can now conclude $\forall n P(n)$ (writing it like this highlights the difference between #2 and what we were looking to prove). We were able to do this without any "repeating this..." or "by a similar argument..." , which are not really valid inference rules, in the middle of it all.

Answer 2

My personal take on this, is that all the talk about "infinite this, and infinite that" is only mudding the waters. The emphasis should not be on wanting to prove $P(n)$ for all all $n$, but rather that you want to prove it for each $n$.

The way I see induction is that the following happens. You know that $P(1)$ is true, and that whenever $P(n)$ is true, $P(n+1)$ is true. Then we we need $P(100)$, say, we have a chain of true implications $$P(1)\implies P(2)\implies\cdots\implies P(100),$$ where $P(1)$ is true and hence all are true. No infinity of any kind.

The emphasis on infinitely many things only confuses. When you show that $n(n+1)$ is even, say, you just write a proof and it works for every $n$; nobody ever emphasizes that one has just proven infinitely many statements.

Answer 3

The statement

Since we can't go over "manually proving" all claims 1,2,… and actually get to the finish line in a finite time, we use induction to prove "all the claims at once".

is essentially accurate, but it's actually making two separate points:

1. It's trying to motivate why it is necessary to go from countably many separate statements $P(0)$, $P(1)$, $P(2)$, $P(3)$, ... to a single universally quantified statement $\forall n\in\mathbb{N}. P(n)$.
2. It introduces the induction principle that allows you to prove $\forall n\in\mathbb{N}.P(n)$ by proving the simpler statements $P(0)$ and $\forall n\in\mathbb{N}.P(n) \Rightarrow P(n + 1)$.

The first part of the quote

we can't go over "manually proving" all claims 1,2,… and actually get to the finish line in a finite time

motivates the point (1.), whereas the second part

we use induction to prove "all the claims at once"

hints at one specific method how to accomplish (2.).

Motivating (1.) and explaining (2.) are actually two separate pedagogical tasks, both challenging in their own way.

Motivating the induction principle

The (2.) might be the easier one, because it does not include any subtleties about "infinitely many statements", and because it's just one of Peano's axioms. Intuitively, it simplifies the problem, because it replaces a "complicated" statement $\forall n.P(n)$ about $P(n)$ by a "much simpler" statement $\forall n. P(n) \Rightarrow P(n + 1)$ about tiny steps $P(n) \Rightarrow P(n + 1)$.

While proving $P(0)$ and $\forall n.P(n) \Rightarrow P(n+1)$ is sufficient, it's not necessary for proving $\forall n.P(n)$: if, for example, one is able to assume $n:\mathbb{N}$ and prove $P(n)$ directly, then this probably should be preferred in most of the cases. The quote by itself therefore does not motivate why you "need" the induction: it just introduces one additional tool specific to $\mathbb{N}$.

Motivating the necessity to go from infinitely many statements $P(1)$, $P(2)$, ... to a single statement $\forall n.P(n)$.

The (1.)st point might be quite a bit more difficult to motivate. Below, I'm suggesting to take some inspiration from intuitionism, and emphasize the difference between "giving a man a fish" ($P(1)$, $P(2)$, ...) vs. "giving a man a fishing rod" ($\forall n.P(n)$).

Explain it like I'm five

Let's start with a "physical" metaphor, in which intuitionistic proof terms are replaced by physical artifacts.

Consider the following problem: suppose that you want to reach a certain altitude of n meters above the ground. How would you explain the fundamental difference between

• the ability to build arbitrarily tall skyscrapers and
• interstellar spaceflight?

In the first case, being able to build arbitrarily tall skyscrapers means that

• For each given height of n meters
• one is able to design and to build a tower of height n.

In the second case, "spaceflight" means that

• One is able to design and build a rocket that
• for each given distance of n meters
• can reach the distance of n meters from the surface of Earth.

Note how the order of building and choosing the n have switched:

• for towers, you first have to pick and fix an n, and only then can you build the tower.
• for rockets, you first build a rocket, which then allows you to pick an arbitrary n

Both methods would, in a highly idealized world, allow you to reach arbitrary distance from the surface of the Earth. But in the first case, you would have to re-design and re-build the tower for each given n, whereas in the second case, you would be able to build one single vehicle once, which could then travel arbitrarily far.

You can see how the induction principle works for a rocket:

• P(0): You can place the rocket on the surface of the Earth (without it falling over etc.)
• P(n) => P(n + 1): If it went P(n) meters, and it can fly one more meter, then it can also reach the distance of P(n + 1) meters.

Thus, for a rocket, you can conclude that, in principle, it can go arbitrarily far.

The induction doesn't work for towers / skyscrapers, though: it could well be that having a wooden tower that's 100 meters tall doesn't allow you to go to 101 meter, because the entire construction is on the brink of collapse. You would have to switch to brick / steel / titanium / graphene / unobtanium ... in order to build taller buildings. This is the difference between the ability to build arbitrarily tall towers and the ability to build rockets.

Explain it like I can program

If one understands the distinction between the compile time / runtime, and is working in a language where types can depend on integers, then it should be quite obvious that:

• Being able to write down a term of type P(n) at compile time will only give you a single value of runtime type P(n), but not necessarily P(n + 1), P(n + 2) , ... etc.
• Being able to write down a term of the dependent function type Π(n: Nat).P(n)/forall(n: Nat).P(n) gives you a function which, given an arbitrary n: Nat at runtime, would produce you a value of type P(n).

Here is a very similar construction, written out in an actual programming language: the question showed that one could prove P(n) for each n by rerunning the compiler, whereas the answer showed how to prove Forall n. P(n) once and for all, without having to re-run the compilation for each new n.

Explain it like I understood something about formal systems

In the statement

• "For all κ, we can prove P(κ)." (where κ is a metavariable that can take values of natural numbers, e.g. κ = 1 for P(1), κ = 2 for P(2) etc.)

the universal quantification takes place in the metalanguage (in this case, in plain English, without the gray background). It's a meta-linguistic statement about infinitely many propositions P(1), P(2), P(3) ... etc.

In the statement

• "We can prove ∀n.P(n)"

the universal quantification takes place in the object language, the quantifier is part of the proposition that we are proving, and we are talking about one single proposition ∀n.P(n).

These are clearly very different statements, because in the first case, one doesn't need universal quantifiers, whereas the second couldn't even be formulated in a system that doesn't have universal quantification.

This should also clarify Steve's question under this answer: it's universal quantification in both cases, but in one case, it's in the metalanguage, whereas in the other case, it's actually in the object language.

---

So, in all three cases, one can see that it's always

• building infinitely many static structures vs.
• building one single rocket with unlimited range

or

• rerunning the compiler unbounded number of times to generate separate terms of type P(n) vs.
• running the compiler just once to generate a function of type forall n. P(n)

or

• making a metalanguage-claim about infinitely many separate propositions P(1), P(2), ...
• making a claim about a single proposition ∀n.P(n).

To conclude,

Since we can't go over "manually proving" all claims 1,2,… and actually get to the finish line in a finite time, we use induction to prove "all the claims at once"

is essentially accurate.

Answer 4

The most basic way to prove a claim of the form $$\forall x \in X: P(x)$$ is universal generalization.

Such a proof looks like this: Let $x \in X$ be chosen arbitrarily. Argue $P(x)$.

This is a way of proving an arbitrary number (including infinite numbers) of statements all at once.

When we are dealing with a statement quantified over the natural numbers, then we have an additional tool to use which is mathematical induction. We take it as an axiom that for any proposition $P$ about natural numbers,

$$[P(0) \wedge (\forall k \in \mathbb{N}: P(k) \implies P(k+1))] \implies \forall n \in \mathbb{N}: P(n)$$

So to prove $\forall n \in \mathbb{N}: P(n)$ we can instead argue $P(0) \wedge (\forall k: P(k) \implies P(k+1))$.

The way to argue this is to use conjunction introduction: Argue $P(0)$, then argue $\forall k: P(k) \implies P(k+1)$. The way we usually argue the second claim is using universal generalization: take an arbitrary $k \in \mathbb{N}$ and try to argue $P(k) \implies P(k+1)$. Finally the way we argue this is using implication introduction: Assume $P(k)$ and attempt to deduce $P(k+1)$ under this hypothesis.

So we have (at least) two different proof strategies for proving universal statements about natural numbers: "regular" universal generalization, and mathematical induction.

Some examples: we can easily prove that $6|(12n)$ for all natural numbers $n$ without appealing to induction. However, I think you will find it difficult to prove that either $2|n$ or $2|(n+1)$ for all $n$ except by using mathematical induction.

Answer 5

I guess what I dislike about the characterization of induction quoted in the OP is that it takes a statement $\forall n.T(n)$ about natural numbers, separates it into a sequence of statements $T(1)$, $T(2)$ etc., and then seems to imply that when faced with such a sequence, the method of proof to use is induction. Rather, I would stress in my characterization that induction is a tool we allow ourselves to use when convenient. There are other methods to prove a statement of the form $\forall n.T(n)$. You can use whatever method works. Sometimes induction might be the easiest way, and sometimes it might be the only way.

For instance one can prove $n+n$ is even. Since the context is a calculus class and the goals are, I presume, to teach the students to construct and understand induction arguments, I will take the rules of arithmetic for granted, even though they are established by means of induction or its equivalent when not taken for granted. A typical proof that $n+n$ is even starts with "Let $n\in{\Bbb N}$ be arbitrary." The rest is just algebra in whatever detail you wish to use or impose: $n+n=(1\cdot n)+(1\cdot n) = (1+1)\cdot n = 2n$, which is even by definition (with the appropriate definition). A student in calculus should not construct an induction proof of this statement. (One could prove it by induction, and one could make the student do so; but I don't see why it's a good idea.)

To motivate the usefulness of induction, one should look for an example in which $T(n+1)$ naturally builds on $T(n)$. A nice example for this is Maurolycus's propostion that the sum of the first $n$ odd integers is $n^2$. The standard "proof-without-words" figure of a square on grid paper shows how the firgure for $T(n+1)$ is literally constructed from the figure for $T(n)$. Generally summation formulas are a common starting point for induction proofs because it is clear how the sum of the first $n+1$ terms is built on the sum of the first $n$ terms.

As regards the "sweeping under the rug," the induction step is of the form $\forall n. P(n)$, and one needs to apply some tool for proving universal statements to it. You shouldn't introduce induction before you've introduced at least one way other than induction to prove such a statement, such as the one that starts, "Let $n$ be arbitrary...." Possibly your students know this already. In the US, where I teach, I find it helpful in calculus to remind them, as it were, what "Let $X$ be arbitrary" means and how it is used.

Answer 6

As with the other answers, talk of proving an infinite number of claims is unnecessary.

Rather, we should view proofs by induction as showing us something fundamental about the successor function. Now, every natural is either zero, or some number of applications of the successor function to zero. What a proof by induction gives us is a proof that, say, zero is green, and that given a green object, the successor function gives us back a green object. Hence, since all numbers are either zero or formed by the successor function, all numbers are green.

In particular, the inductive step shows that the successor function preserves "greenness". Now, this approach generalizes to any inductively/recursively defined objects.

As for what distinguishes when we need induction and when we don't I refer to this helpful answer: https://math.stackexchange.com/questions/1295010/what-are-statements-about-the-natural-numbers-where-induction-is-impossible-or-u. In particular, induction seems to be unnecessary in the many divisibility cases, where the proof strategy will ultimately be to obtain some algebraic rewrites. Also, induction is not very helpful with properties such as primality- even if we can show that the successor function respects certain properties, it is not very helpful for us to have this information.

Answer 7

I endorse Andrey Tyukin's answer but I want to add a few remarks.

1. Induction certainly is all about proving statements for infinitely many $n$ all at once. If you are proving a statement for only finitely many $n$ then you don't need induction.

2. I think it possible that you are interpreting the other instructor's words more rigidly then they were intended: "Since we can't go over "manually proving" all claims $1, 2, \ldots$ and actually get to the finish line in a finite time, we use induction to prove 'all the claims at once'." If the instructor meant that statements of the form $\forall n. P(n)$ can only be proved by induction, then you are right to object, since that is untrue. For example, the statement $\forall n. Sn\ne 0$ holds without induction, being an axiom of Peano arithmetic. But if the instructor merely meant that some proofs of statements of the form $\forall n. P(n)$ require induction, then that is correct, and for precisely the reason given: the inputs to an inductive proof already give a proof for any particular $n$ simply by stringing implications together, but induction is the extra ingredient needed to turn this into a "for all $n$" statement.

3. You are right to be concerned that the proposition $\forall n. P(n)\Rightarrow P(Sn)$ is itself a "for all $n$" statement, which either undermines the other instructor's claim (if that claim is taken to hold for all universally quantified statements), or else itself requires induction to prove, leading to an apparent infinite regress. The answer to this is twofold: (1) as mentioned in the previous remark, there do exist "for all $n$" statements that can be proved without induction; (2) although the proof of $\forall n. P(n)\Rightarrow P(Sn)$ may appear not to use induction, it probably relies on many common arithmetic truths that are treated as black boxes. How do you know that these black boxes don't have proofs by induction inside? Many things we mostly take for granted do require induction to prove in Peano arithmetic. The Wikipedia article on Robinson arithmetic is interesting in this regard. Robinson arithmetic is essentially the fragment of Peano arithmetic without induction. The article mentions that in Robinson arithmetic there is a proof of the commutativity of the addends of any particular sum, but there is no proof of the statement $\forall x,y. x+y=y+x$. So in any particular inductive proof, it is quite likely that there's an induction buried inside of the proof of $\forall n. P(n)\Rightarrow P(Sn)$.

4. This is an aside, but I want to call attention to the very interesting comment of Passer By, pointing out that even in Peano arithmetic with induction there are statements $P(n)$ for which proofs can be given for any particular $n$, but for which no proof of the statement $\forall n. P(n)$ is possible.