Does a proof by induction have to explicitly refer to the principle of mathematical induction?

Question

I teach high school math.

Some of my colleagues insist that a proof by induction should explicitly refer to the principle of mathematical induction, i.e. it must include the words "by the principle of mathematical induction" or words of equivalent meaning.

Others say that (given a proposition $H_n$) it is enough to show that the base case is true and that $H_k\implies H_{k+1}$; it is not necessary to explicitly refer to the principle of mathematical induction.

Solutions in the mark schemes for the exams (IB and A-level) are inconsistent: sometimes they explicitly refer to the principle of mathematical induction, sometimes they do not, and sometimes they refer to it in brackets (indicating that it is optional).

If a proof by induction has to explicitly refer to the principle of mathematical induction, then do proofs using the pigeonhole principle have to explicitly refer to the pigeonhole principle? Do proofs by contradiction have to explicitly refer to the principle of proof by contradiction (if there is such a thing)?

Possibly relevant: Why does induction have to be an axiom?

Answer 1

The appropriate level of granularity for a proof depends on the audience.

• If you're taking an "Intro to Proofs" class and your homework is to do some proofs by induction, then yeah, you will be expected to state when, where, and how you use the principle of mathematical induction. You should explicitly label the base case, the inductive hypothesis, etc. Not because your grader needs that information to follow your proof, but because the whole point of the homework is to demonstrate that you know this stuff. (Likewise, if you're teaching an "Intro to Proofs" class then obviously you need to label all those steps in your example proofs to provide proper scaffolding for students.)

• If you're a full-blown mathematician who is writing a research paper, then your audience already knows this stuff like the back of their hand, so most of it doesn't need to be said explicitly. Sure, it will make the reading a little gentler if you precede the inductive proof with "By induction, ...", and that would probably be a nice thing to do for your audience, but you're not going to lose any other research mathematician in your audience if you omit the explicit reference to induction, and nobody is going to question your understanding of induction because you didn't explicitly label something (you'd have to make a legitimate and egregious error in the basic logic for that to happen).

Your case sounds closer to the first one, so I would say sure, as long as your colleagues tell their students what features of the induction proof they are required to explicitly state/label, it's appropriate for them to expect a student's induction proof to include those features.

... though if they're reading a math research publication and claiming that it should be edited to include the include the words "by the principle of mathematical induction", then that's a different story ;)

Answer 2

A blast from the past comment, for the consolation of your students, of a mathematician being marked down by one of the most influential mathematicians of his day:

John Wallis in his Arithmetica Infinitorum (1656) in Prop. XIX examines the sum of squares up to $n^2$ divided by $n^2(n+1)$. He computes them for $n$ up to $n=6$ and proclaims that by way of induction ("per modum inductionis"), that the sum is given by $${\,0\;+\,1\,+\,4\;+\cdots+n^2 \over n^2+n^2+n^2+\cdots+n^2}={1\over3}+{1\over6n} \,.$$ Wallis is the first written source to use the word "induction" to describe and justify the proof of a proposition. Wallis used his form of induction frequently. Wallis was criticized, but he defended his method. Jacob Bernoulli suggested that one of Wallis's proofs could be improved by showing how the $n+1$ case followed from the case for $n$ — an explicit statement of the induction step. Here is Wallis defending his method in 1685, A Treatise of Algebra, Ch.78, p.298:

Those propositions in my Arithmetick of Infinites, are (some of them) demonstrated by way of Induction: Which is plain, obvious, and easy; and where things proceed in a clear regular Order, (as here they do,) very satisfactory, (to any who hath not a mind to cavil;) and shews the true natural investigation. Which to me, is much more grateful and agreeable, than the Operose Apagogical Demonstrations, (by reducing to Absurdities or Impossibilities,) which some seem to affect;...

Long before the Principle of Mathematical Induction had been formalized, there was controversy over how pedantically formal proofs should be.

Answer 3

I am (one of the) colleagues David refers to in his post. The reason I am doing this lies in some of the answers/comments posted here already. For example, Humberto sais: "While technically it may be sufficient to show that the base case holds and the inductive step follows (Hk ⟹ Hk+1), ...". My question is why? In my opinion, the answer is "because of the principle of mathematical induction". In my opinion, this is not at all obvious. Nothing else (except the well-ordering principle) implies this. This is why (in my opinion) it needs to be stated. Otherwise students may think that this is obviously some consequence of some theorem(s) that mathematicians who deal with the formal foundation of mathematics proved already. I may be wrong, but I think that it is not. It is an intuitive belief that cannot be proven from the other properties we take for granted (the axioms, if we want to use more formal language). So, back to Humberto's comment, I do not think that technically it is enough to check the base case and the induction step. Intuitively I agree it is enough, but technically we need a concluding statement (with or without the explicit reference to the principle).

Whether we want to insist on students mentioning the point where they use the principle is of course a matter of opinion. An example is posted in Grade on proving |$a_1 +a_2+...+a_n| \le |a_1|+|a_2|+... +|a_n|$ . In this post the student used practically an inductive proof, but instead of formally following the steps (required by most IB and A-level high school markschemes) the student wrote "repeating this ...". He clearly understood the intuition, but not what induction is about. It is not just about formally using a certain method. It is also about why to use the method instead of intuitive arguments.

Answer 4

Typically you want to name things. This makes them visible and something you can discuss. So, while teaching, you do want to say that this thing her is induction, so we have to remember to check the base case, and that from every case we can deduce the next one. If you do not name this thing, then it is likely that many students do not know what they should be paying attention to.

An exam requiring particular magical incantations seems silly, but if succeeding at them is important, then you should teach the magical incantations to the students. You may want to say that in general it is a good idea to say that you using induction, so that the reader is oriented, but whether it is called the principle of induction, or one just writes "By induction...", or explains the idea in the proof itself; not really essential.

So:

• Make the proof as easy to understand as possible.
• Tell students to use any magic words an exam requires in that exam.
• Writing like mathematics articles are written is not always a good idea, as many mathematics articles are poorly written, just like many academic texts in general. There are of course many good ideas there, too, but one has to think communication first, not just copy and paste expressions from other examples of the genre (mathematics research article or textbook).

Answer 5

In a pedagogical context I can see four types of situation where it may reasonably be required for students to explicitly state their use of the principle of mathematical induction:

1. If writing proofs by induction is part of the material being tested, students may be required to state its use explicitly.
2. If the material being tested itself distinguishes in a meaningful way between proofs that use induction and proofs that don't (e.g. a class covering different logical systems and what can/can't be proven in each), students may be required to state where any such proof uses the principle of mathematical induction explicitly.
3. If the students need to write proofs in an extremely standardized format (e.g. so that it can be automatically graded) they may be required to explicitly state whether or not the principle of mathematical induction is used.
4. If the students are generally not expected to already know the principle of mathematical induction and it is not part of the material covered in the class, then any student who does happen to know it and wishes to use it in a proof nonetheless should probably state explicitly that they are using it (although this situation is unlikely to appear in any marking schemes as it is very likely not the kind of answer that the person writing the marking scheme is anticipating).

To summarize, it may be required if it is used to demonstrate the students' understanding of induction as a principle/proof method, if it is relevant to the metamathematical material being tested, if strict formatting guidelines must be followed for some reason, or if students are not expected to know it or learn it in the course at hand but are allowed to use it if they happen to already understand it. Outside of these situations I don't see why students should be required to state its use explicitly.

Answer 6

Peano's axioms without the axiom of induction has some models that do not correspond to the natural numbers that we have in our minds. In order to prove that every natural number $n$ other than $0$ is the successor of some other natural number $k$, i.e., for all $n\ne0$ there exists $k$ such that $S(k)=n$, we must harness the axiom of induction. Think of $k$ as $n-1$.

Consider the model ${\bf N}_\text{strange}$ of Peano's axioms without induction that looks like $$\{0,1,2,3,\ldots, \omega, \omega+1,\omega+2,\omega+3 \ldots \}$$ This system satisfies the Peano axioms without induction, although I am not going to digress and give details (use your intuition). In this system, $\omega$ is not the successor of anything. That this is possible is hardly surprising, because we need the axiom of induction to prove that every number other than $0$ has a predecessor.

So why do we want high school students learning about induction to chat "by mathematical induction blah blah blah? This is a tricky question. But under the hood, given a proposition $H(n)$ and showing (i) that the base case is true and (ii) $H_k\implies H_{k+1}$ is not sufficient to deduce $H(k)$ for all $k$ in ${\bf N}_\text{strange}$. The truthiness of $H$ would not extend to $\omega$. One justification for the required chat invoking induction is "mathematical honesty," although I don't think this will be appreciated at scale!

Answer 7

Let's not overlook an obvious application of induction is to turn it around and go from general to specific.

Let's say we have established $H(1)$ and that $H(k+1)$ follows from $H(k)$ and we are perfectly content with whatever algebra and logic was involved to establish this. But we simply refuse to recognize or accept induction as method of proof. We just refuse to chant "by induction, $H(n)$ is true for all $n\in{\bf N}$."

Now then, how would we actually write down a proof of $H(10,000)$? Well, we would start our proof by establishing $H(2)$, then we would continue writing by establishing $H(3)$, etc. Eventually we would have written down a very long, boring and stupid proof that establishes $H(10,000)$. If only we not so stubborn, and were willing to invoke induction to first conclude $H(n)$ is true for all $n\in{\bf N}$, and then go from general to specific: apply the validity of $H(n)$ for all $n\in{\bf N}$ to the specific case $n=10,000$.

In a similar vein, how can we establish $$\sum_{n=1}^{10,000} n^2 = 333383335000$$ if we refuse to accept induction as a method of proof?

No problem. We just have a symbolic computational system like Wolfram perform the sum. Perhaps for the first $N=10,000$ terms the system is actually doing the addition by brute force. But at higher values of $N$, the system is smart enough to "cheat" and skip the onerous addition, and instead substitute $N$ into the formula $\frac{N(N + 1)(2N + 1)}{6}$. So again, induction is being used to go from general to specific. The general result is the statement $$H(N):\ \sum_{n=1}^N n^2=\frac{N(N+1)(2N+1)}{6}$$ which is established by induction, and we go to the specific case by substituting a numerical value into the formula.

Answer 8

To be a proof, an argument needs to be explicit about the logical structure. An induction proof won't be any different. Take a very standard task like: such as showing that, for all $n\in \mathbb{N}$ $$ \frac{1 - x^{n+1}}{1-x} = 1 + x + x^2 + \cdots + x^n $$ (i.e., that the rational function on the left is the polynomial on the right).

Answer 1: Let $n\in \mathbb{N}$ be given. We compute $$ (1 - x)(1 + x + x^2 + \cdots + x^n) = (1 - x) + (x - x^2) + \cdots + (x^n - x^{n+1}) $$ Rebracketing the rhs we get $$ 1 + (-x + x) + (-x^2 + x^2) + \cdots + (-x^n + x^n) - x^{n+1} = 1 - x^{n+1} $$ and so $$ (1 - x)(1 + x + x^2 + \cdots + x^n) = 1 - x^{n+1} $$ Dividing both sides by $1-x$ gives the identity we wanted for this $n$. As $n\in \mathbb{N}$ was arbitrary, the identity holds for all $n$.

Comments: I picked this example because it is a standard school induction exercise, but this isn't a proof by induction. The logical structure is different. (Though it is the same structure you see in $\varepsilon$-$\delta$ proofs from calculus class. A weird thing to university level instructors is that some students think that "proofs" are "proof by induction" when they arrive, and then struggle with simpler direct proofs like this one.)

Answer 2: The proof is by induction on $n\in \mathbb{N}$. The base case is $n=0$. We verify it directly: $$ \frac{1 - x^{0 + 1}}{1 - x} = \frac{1 - x}{1 - x} = 1 $$ Now we suppose that, for some $n\ge 0$, $$ \frac{1 - x^{n+1}}{1-x} = 1 + x + x^2 + \cdots + x^n $$ Consider now the sum $$ 1 + x + \cdots + x^n + x^{n+1} $$ By the induction hypothesis, this is equal to $$ \frac{1 - x^{n+1}}{1-x} + x^{n+1} = \frac{1 - x^{n+1} + (1 - x)x^{n+1}}{1-x} = \frac{1 - x^{n+1} + x^{n+1} - x^{n+2}}{1-x} = \frac{1- x^{(n+1) + 1}}{1-x} $$ Hence the induction hypothesis implies that the identity holds for $n+1$. This closes the induction, and so we conclude that the identity holds for all $n\in \mathbb{N}$.

Comments: Whether a version of this argument uses the specific template I have (or some other one), it would need to say that induction is being used, what the parameter is, what the IH is and so on. By itself, the final computation is pretty meaningless. Even a very terse version like: we have $\frac{1 - x^{n+1}}{1-x} + x^{n+1} = \frac{1 - x^{n+2}}{1-x}$ so the identity holds for all $n$ by induction is clear about the logical structure.

You also ask:

If a proof by induction has to explicitly refer to the principle of mathematical induction, then do proofs using the pigeonhole principle have to explicitly refer to the pigeonhole principle? Do proofs by contradiction have to explicitly refer to the principle of proof by contradiction (if there is such a thing)?

The answer is (obviously?) "yes" to both of these questions. Much like with induction, there is even a standard template for proofs by contradiction, which begins: "Suppose, for a contradiction, that ..."

Answer 9

From a traditional standpoint in teaching high school math, clarity and pedagogy are paramount. A proof by induction traditionally includes an explicit reference to the principle of mathematical induction to ensure that students understand not just the mechanics of the proof but also the underlying logical framework that validates the approach. While technically it may be sufficient to show that the base case holds and the inductive step follows (Hk ⟹ Hk+1), explicitly stating that one is using the principle of mathematical induction reinforces the method and its formal structure, which is crucial for educational purposes.

Regarding other principles like the pigeonhole principle or proof by contradiction, traditionally, it is also considered good practice to name the principle being used. This practice helps students to distinguish between various proof techniques and understand their applications. However, as with the principle of mathematical induction, it may not always be necessary to name the principle as long as the logical structure of the proof is clear and correct.

In educational settings, it is often beneficial to be explicit about these principles to aid learning, even if, in professional mathematics, such explicit references may sometimes be omitted.

Answer 10

Does a proof by induction have to explicitly refer to the principle of mathematical induction?

There's no obligation of course, but it seems to be good pedagogy, especially at ealy(er) stages, to ask for and foster explicitness on argumentation. On the matter of induction specifically, one could do wonders by discussing the different forms of induction:

• 'Sucessor induction', the best known, that holds in the natural numbers;
• 'Well-ordered induction', that also holds in, say, $\omega+\omega$, $\omega + \omega + \omega$,..., with these lacking 'sucessor induction' as a previous answer noted, but otherwise being models for sucessor-addition-multiplication arithmetic;
• 'Well-founded induction', (sometimes called either 'weak' or 'strong' [!] induction in the context of the naturals) that holds for binary strings $2^{<\omega}$ ordered by the substring relation, or for well-formed formulas ordered by the subformula relation, each of these not being well-orders

Of course each case implies the next, and the examples show the implications are not reversible. The last one's likely to be more interesting/useful to students with interests in computing sciences, but really, just talk to them about these things

Do proofs by contradiction have to explicitly refer to the principle of proof by contradiction (if there is such a thing)?

Yes, please, let's try to teach people that proofs of negations are not the same thing as proofs by contradiction

Answer 11

The Principle of Mathematical Induction states:

$\forall P\subset N:[0 \in P \land \forall x\in P: [S(x) \in P] \implies P=N]$

Where $S$ is the successor function on $N$.

IMHO high-school students in North America will not be able to grasp the meaning of this statement, never mind apply it in proofs. I'm guessing most high-school teachers there won't understand it either.

EDIT

This is not to say that proof by induction should not be taught in high schools. Just don't dwell on the above axiom as seems to be suggested here. A formalized approach, even if translated into words, will only create confusion at that level. If students cannot recall the exact wording of the axiom, they may think the cannot do proof by induction.