12
$\begingroup$

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?

$\endgroup$
12
  • 5
    $\begingroup$ I don't mean to derail the discussion, but if the concern is being completely honest with students about why and where induction is needed, then you are immediately led to intricate foundational issues. I don't feel competent to comment on this, so I'll only refer you to Wikipedia's discussion and this math.SE question. The point I'm trying to make is that, while you are correct that there... $\endgroup$ Oct 19, 2022 at 15:01
  • 2
    $\begingroup$ ... are universally quantified statements that follow from the axioms without using induction, how much of the actual arithmetic we care about can be obtained without using induction may be less than you would think. $\endgroup$ Oct 19, 2022 at 15:01
  • 5
    $\begingroup$ Proving infinitely many $P(n)$ is not the same as proving $\forall nP(n)$. In fact, an infinite "proof" is not a proof at all. There are problems which happens to have proofs for every $P(n)$, but which there are no proofs for $\forall nP(n)$ (in Peano arithmetic). So indeed, induction is necessary. $\endgroup$
    – Passer By
    Oct 20, 2022 at 9:44
  • 3
    $\begingroup$ "proving the 'induction step' T(n)⇒T(n+1) also amounts to proving an infinite number of claims" - this seems distinct from the issue you mentioned that you'd run into when not using induction: "we can't go over 'manually proving' all claims". The issue induction addresses is not proving an infinite number of claims, but rather that it's impossible to manually prove infinitely many claims 1 by 1 (whereas induction proves them "in bulk"). $\endgroup$
    – NotThatGuy
    Oct 20, 2022 at 12:22
  • 2
    $\begingroup$ An historical tidbit, which might be interesting: "Although this proposition has an infinity of cases, I will give them a very short proof, assuming 2 lemmas. The 1st,... that this proportion is found in the second base.... The 2nd, that if this proportion is in any base, it will necessarily be found in the following base." — Pascal, Arithmetic Triangle, Twelfth Consequence. So thinking of "For all n, T(n)" as an infinity of claims goes back a ways. There be other ways than induction to prove a "for all" claim, too; otherwise you'd use induction to prove the induction step ad ∞. $\endgroup$
    – user1815
    Oct 21, 2022 at 3:35

7 Answers 7

13
$\begingroup$

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.

$\endgroup$
6
  • 10
    $\begingroup$ Even though it is intuitively clear ..., what formally valid inference rules are being applied in the "repeating this" step? You are absolutely right that the student should know how to completely formalize the argument, if required, but I would humbly disagree that the proof should be called "flawed" in this case. IMHO, understanding that the induction is just a "finite repetition of the same step" and being able to see that quickly is at least as important as the ability to write "Base ..., Step ...". I've seen students who can do the latter but are totally clueless about the former. :-) $\endgroup$
    – fedja
    Oct 19, 2022 at 12:52
  • 1
    $\begingroup$ @fedja Agreed that there is no actual logical flaw in the student’s reasoning, but I think the “repeating…” step is doing a lot of work, likely too much work for the student to illustrate understanding of induction. So it’s only flawed in the sense that it is unlikely to receive full marks. $\endgroup$
    – Steve
    Oct 19, 2022 at 13:26
  • 6
    $\begingroup$ "it is unlikely to receive full marks" If that happens when the students are just learning the induction, I 100% agree, but when I teach students who are supposed to have had the induction in their toolbox for a few years, not only do I let such style of inductive argument pass, but also often use it myself. It is funny that we have to require our students to use formal language to ensure and to check understanding (and I see no other way), but it is very seldom that we resort to it in our everyday mathematical communication ourselves :-) $\endgroup$
    – fedja
    Oct 19, 2022 at 13:50
  • 5
    $\begingroup$ @Thierry The student certainly understands the idea and one of statements in my comment is equivalent to your remark in parentheses. However, when students are just learning a tool, I often also request them to present an argument in some particular commonly used format and the ability to do that is graded as well. Once they master it, I drop that requirement, of course (recall all those horrible "two column proofs" in American school geometry. That is certainly not how one thinks, but learning to convert one's natural thought flow into a formal presentation is still necessary, IMHO :-) ) $\endgroup$
    – fedja
    Oct 19, 2022 at 14:07
  • 1
    $\begingroup$ @Thierry Whether the student should receive full marks for that answer was really the subject of the linked question, where these same issues of whether the answer was sufficient or not and in what contexts came up. $\endgroup$
    – Steve
    Oct 19, 2022 at 16:54
11
$\begingroup$

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.

$\endgroup$
8
  • 1
    $\begingroup$ Interestingly, the answer in the question I linked actually contends induction is logically necessary because it is the means by which we can move from an inference “for any fixed” n to one “for all” n. Where does “for each” n fit into this hierarchy of quantifiers? $\endgroup$
    – Steve
    Oct 20, 2022 at 0:06
  • 1
    $\begingroup$ For whatever is worth, I downvoted both said question and answer. The TA was unfair to the student, and the answer delves into wording that might be appropriate if one is discussing foundations, but not otherwise. I don't see how "for each $n$" is different from "for all $n$". But saying "for each" emphasizes the fact that the proof can be done for each $n$ at a time (which is almost always the case). $\endgroup$ Oct 20, 2022 at 0:31
  • 2
    $\begingroup$ I took the three dots to be a notational convenience--a human reader can easily fill in the missing 97 terms. Induction is not needed to justify that. More generally, if you only need to prove $P(n)$ for a finite set of values of $n$, you don't need induction since you can write out the finitely many chains of implications that are required. It's only to prove $\forall n P(n)$ that induction is needed. $\endgroup$ Oct 20, 2022 at 20:58
  • 2
    $\begingroup$ This answer doesn't seem to talk about statements like $\forall n.P(n)$, and, consequentially, it does not rely on induction. Since the question title explicitly included the words "induction" and "infinite", I don't understand how this answer is actually related to what's being asked. In the comments to the question, it has already been pointed out that one can construct $P$ such that all $P(1)$, $P(2)$, ... are true and provable, but $\forall n.P(n)$ is not provable. $\endgroup$ Oct 21, 2022 at 12:35
  • 2
    $\begingroup$ @Thierry It is enough to prove it for all $n$; it's just that your proofs get longer and longer as $n$ gets bigger. If you want to assert the statement for an $n$ you haven't been able to reach, or worse, for all $n$, you need to call upon the principle of induction. The main claim in the answer I was objecting to is that the focus on infinity was misplaced. You can prove the statement for finitely many $n$ without appealing to induction, but to assert it for all $n$ you need induction. For that reason, infinity is the central issue. $\endgroup$ Oct 21, 2022 at 22:24
9
$\begingroup$

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.

$\endgroup$
6
  • $\begingroup$ This is somewhat helpful... can you set me straight on the below? Let's say we are typical undergraduates working in FOL. We would protest being told to prove $P(n)$ because it's not a sentence in FOL. If so, then students in a non-logic course are never in the first situation of trying to prove a formula in the formal language that is quantified in the metalanguage. The whole situation is further complicated by the fact that students are "working in" FOL but writing the proofs in natural language. So there is no apparent difference to them between "for all n, P(n)" and $\forall n P(n)$. $\endgroup$
    – Steve
    Oct 20, 2022 at 19:09
  • 1
    $\begingroup$ @Steve "$P(n)$ [...] is not a sentence in FOL", wait, why not? For a fixed predicate $P$ and a constant natural number $n$, it's a sentence in FOL. Please note that both $P$ and $\kappa$ (formerly n) are metavariables, you have to take a concrete predicate $P$ and fix a number $\kappa$, only then does $P(\kappa)$ become a proper sentence in FOL. I've updated the answer to differentiate more clearly between variables in the object language and the metavariables. $\endgroup$ Oct 20, 2022 at 20:13
  • 1
    $\begingroup$ @Steve "So there is no apparent difference to them between "for all n, P(n)" and ∀𝑛𝑃(𝑛)." - No, wait. Forget "FOL" or "SOL" or "HOL" or whatever. Even little kids should understand, that there is a huge difference between calling an Uber ($\forall destination . CanGoTo(destination)$), and buying twenty suitcases full of tickets for every bus and every train for the next ten years ($CanGoTo(dest1)$, $CanGoTo(dest2)$, $CanGoTo(dest3)$, ...). $\endgroup$ Oct 21, 2022 at 13:48
  • $\begingroup$ @Steve Similar situation for this answer here: it is as if you asked something about private jet maintenance, but the answer instead says something like "Private jets ($\forall destination.CanFlyTo(destination)$) are overrated, you can just buy all the tickets to all flights instead ($CanFlyTo(City1)$, $CanFlyTo(City2)$, $CanFlyTo(City3)$)." (to be continued...) $\endgroup$ Oct 21, 2022 at 13:55
  • 1
    $\begingroup$ @Steve (...cont) But that's obviously not the same thing. Ordinary everyday common sense should tell you that buying a private jet might sometimes make sense, whereas buying all tickets for all destinations for all times is clearly insane (especially if there are infinitely many possible destinations that you might want to reach). There is a clear and intuitive distinction between solving one problem at a time in ad-hoc manner ($P(1)$, $P(2)$, ...), and having a machine that can solve all the problems at once ($\forall n.P(n)$). You don't need any FOL / HOL distinctions for that. $\endgroup$ Oct 21, 2022 at 13:58
6
$\begingroup$

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.

$\endgroup$
16
  • $\begingroup$ I think this is well said in terms of what students really intend when they ask “why do we /need/ induction?”. $\endgroup$
    – Steve
    Oct 21, 2022 at 20:00
  • $\begingroup$ Given any n greater than 1, there will exist some largest natural number k such that 2k <= n, and some natural number b such that n=2k+b. If b=0 then 2|n. If b=1, then n=2k+1, and thus n+1 will be 2k+1+1=2(k+1), implying 2|(n+1). If b were 2 or greater, that would imply that 2(k+1)<=n, meaning k was not the largest integer such that 2k<=n. $\endgroup$
    – supercat
    Oct 21, 2022 at 22:19
  • 1
    $\begingroup$ I'm pretty sure that the last sentence of your comment I objected to implicitly says (via pragmatics) that if you don't need a first-order proof, then you can get away without using induction. This is wrong because if you have PA− plus suitable set-construction axioms, using second-order well-ordering is no different from (and in fact inferior to) using second-order induction. And if the set-construction axioms are not too strong, then second-order or first-order actually makes no difference to the induction/well-ordering. $\endgroup$
    – user21820
    Dec 2, 2022 at 13:41
  • 1
    $\begingroup$ Furthermore, supercat did not use the term "set" at all in his/her initial comment, which is why I said that supercat invoked a first-order schema, not a second-order axiom as you think. Don't mix up the ability to introduce new function/predicate-symbols (i.e. definitorial expansion) to an FOL system with true second-order axioms. Whenever we use induction in (first-order) PA, we can first define a new predicate-symbol Q over PA and then prove Q(0) ∧ ∀k∈ℕ ( Q(k) ⇒ Q(k+1) ) and then deduce ∀k∈ℕ ( Q(k) ). Using such a symbol "Q" does not make it second-order; it remains squarely first-order! $\endgroup$
    – user21820
    Dec 2, 2022 at 13:45
  • 1
    $\begingroup$ Stating induction as a second-order axiom is a very popular pedagogical error, for similar erroneous reasons. Many textbooks/teachers state that induction is about subsets of ℕ. I hope my explanation has made it clear that this is wrong. Induction, properly understood, is first-order over the base system. If you state induction as a second-order axiom, you will force the use of induction to rely on set-theoretic axioms, but induction itself has absolutely nothing to do with set theory! $\endgroup$
    – user21820
    Dec 2, 2022 at 13:53
4
$\begingroup$

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.

$\endgroup$
2
$\begingroup$

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.

$\endgroup$
1
  • 2
    $\begingroup$ "...we should view proofs by induction as showing us something...", "What a proof by induction gives us is...", "... the inductive step shows...". I notice that in every one of the phrases quoted you are careful to say that it is the "proof" or the "induction step" that gives us information about the successor function. These parts of the argument all take place prior to invoking induction to conclude that the property holds for all $n$, and would make a fine standalone proof that the successor function preserves the specified property. They don't seem to have any bearing on induction itself. $\endgroup$ Oct 22, 2022 at 18:31
2
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ Understood on claim #3, but I’d say that when someone says a proof is “by” some method, it is a local description about the proof being presented and not a global description about whether any prior result depends on a certain method (nor a much stronger claim about the non-existence of alternative proofs of results cited). Unsaid is that results depend broadly on definitions (the facts of the particular mathematical domain) but also the choice of logical system. $\endgroup$
    – Steve
    Oct 21, 2022 at 21:30
  • $\begingroup$ I agree. Point 3 was addressed to the original poster, who seemed incredulous (to the point of calling the other instructor's description "dishonest") that an axiom whose reason for inclusion in our system is the need to prove universally quantified statements should require the proof of a universally quantified statement before you can use it. What I was trying to articulate is that, yes, this probably does lead to a regress, but not an infinite one. $\endgroup$ Oct 21, 2022 at 22:08

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.