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

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?

• I don't know what "should" and "have to" mean in this context. There are no official rules for what constitutes a proof or not. They are written to convince an audience. The question that's relevant is whether requiring your students to do this helps them learn the material better and avoid mistakes. Nov 19 at 6:26
• One way to approach this is to ask what professional mathematicians do. If I open up a math journal and see a proof by induction, will it assume that I will recognize that it is a proof by induction or will it have verbiage such as "by the principle of induction"? Nov 19 at 16:05
• When I learned induction at high school, you needed to use a very precise and long phrase at the end of the proof, something along the lines of "Since P(0) is true, and whenever P(k) is true, P(k+1) is true, then by the principle of mathematical induction, P(n) is true for all n" (and this was over two decades ago, and I've never used it since). If you didn't include this precise phrase, you lost marks, regardless of whether the proof was correct or not. Personally, I'd love to see the death of the phrase "principle of mathematical induction", in favour of plain "induction". Nov 20 at 23:49
• It's important to know that the hardest part about teaching induction is that it cannot be proved from simpler principles, it is literally an axiom of how natural numbers are formally defined. I'm always honest with students and tell them about this fact. I tell them it is indeed subtle, and that the recognition that this is actually such an axiom was only codified near the 19th century, a loooong time after people have been using numbers for all sorts of things. Nov 21 at 0:20
• @DavidRoberts "...the hardest part about teaching induction is that it cannot be proved from simpler principles, it is literally an axiom..." If this is your experience then it's not my place to argue, but my experience is that induction is hard to teach because people simply don't get it--maybe because it seems circular. Once they catch on, I think it's easy for them to accept that there should be such a principle. That the principle doesn't follow from the other axioms of Peano arithmetic and needs to be assumed is an interesting point about formalization, but not a barrier to understanding, Nov 24 at 3:13

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 ;)

• " the whole point...is to demonstrate that you know this stuff" — This is how I explain such requirements to students, too. I appreciate that your answers are centered on (the assessment of) the learning goals at hand. Nov 21 at 14:08
• Out of curiosity, can you give a reference to a research paper that does not mention "by induction" when they apply a proof by induction? Nov 26 at 3:48
• @FerencBeleznay No, I don't have a reference. I'm sure it's vastly more common to mention "by induction" when applying a proof by induction. I would do that myself, and I would appreciate if the author of a paper I'm reading did that -- my only claim is that "by induction" is not something that must be in such a proof, even if it pretty much always is. Nov 26 at 4:07
• Well, unlike high school textbooks, research papers follow the Claim/Proof/Qed format. If a claim says "for all $n$ $P(n)$", and the proof only includes the justification of $P(0)$ and the implication $P(k)\implies P(k+1)$, then in my opinion it is not complete. It must have something extra. Either starting the proof referencing induction, or ending the proof with "hence, $\forall n P(n)$" (with or without the explicit reference to induction). Nov 26 at 5:40
• @FerencBeleznay: Regarding a reference where a proof by induction is given without mentioning the word "induction", see for instance the proof of equality of (11.9) on page 170 in this book or the proof of Lemma 3.3 in this article. Another nice formulation can be found in the proof of Proposition 2.2 "(ii)$\Rightarrow$(i)" of this article: there the authors say "by iteration" to give a brief intuitive description of what is formally an argument by induction. Nov 26 at 22:04

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.

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.

• "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." No students in school are thinking about what mathematicians dealing with formal foundations of mathematics are doing.
– KCd
Nov 20 at 14:39
• Counterpoint: should proofs explicitly label each use of modus ponens Nov 20 at 23:17
• To play devil's advocate, would you accept the phrase "by induction", rather than "by the principle of mathematical induction"? Are your students likely to confuse the induction they are doing in proofs in mathematics with induction as used in the philosophical sense? Nov 20 at 23:44
• @KCd In the IB (international Baccalaureate) all students learn something called "Theory of Knowledge", where they discuss the ways of knowing in different disciplines. When discussing mathematics, they do talk about axiomatic foundations. Some students of course are satisfied with the approach of "give me a formula/method and I use it", but there are plenty who do ask the question "why can we do this?". Probably not in the way I worded it, but there are high school students who are genuinely interested in why things work, even in theoretical mathematics. Nov 21 at 10:25
• When I require special incantations from my students, I contextualize them. "We are writing this for clarity. You might not find it in professional writing, but for this course I will require it, as it helps to demonstrate your understanding." I think in this instance, you are being a bit silly because the cognitive traps you are apparently avoiding seem implausible in a novice, but by the same token, I don't see the harm as long as you do not teach that the statement affects the validity of the proof (it clearly doesn't), but is instead a component of how you ensure that students understand. Nov 21 at 12:06

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!

• In ${\bf N}_\text{strange}$, what number is immediately before $\omega$?
– Dan
Nov 19 at 22:37
• @Dan There is not one, and I state this explicitly. This is the whole point. This is possible if we do not have induction. Nov 19 at 22:38
• Is ${\bf N}_\text{strange}$ really "the model of Peano's axioms without induction" or just "a model that satisfies Peano's axioms without induction"?
– Stef
Nov 20 at 12:28
• @Stef It might be more clear if I had written "Consider the following model..." There are many other models of PA without the axiom of induction besides this one that I am referring to as ${\bf N}_\text{strange}$. Nov 20 at 12:43
• BTW, I use ${\bf N} \cup \{n+i \mathrel{|} n \in {\bf N}\}$ ($i$ = complex imaginary unit) for ${\bf N}_{\text{strange}}$ in class. I've tried it with $n+{1\over2}$, but sometimes the students get confused, thinking that now the successor of $2$ is $2.5$. I also use directed graphs to illustrate a system that fails one or another of the axioms, which is a nice way to help the students see the structure abstractly. Nov 22 at 16:52

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.

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).
• The last one is more of a general note. Nov 18 at 14:18

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.

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.

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.

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 ..."

• The two proofs are very similar, the main difference being that in the second proof the telescoping happens only with one pair of terms whereas with the first it happens with a whole series of pairs at once, something that, strictly speaking, can only be justified by an appeal to induction. (This essentially reproduces the second proof.) "Logical structure" can be hard to pin down. Certain manipulations permitted to students may have a lot of logical structure hidden inside. What are the rules that determine when such structure has to be made explicit? Nov 28 at 18:12
• @WillOrrick: In the first proof, once $n$ is fixed, the coefficients of a polynomial multiplication are determined by a formula, which is what I used and also would expect high school students to know. You don’t need induction there. I think your other question is sort of losing the big picture. A proof needs to state a hypothesis, state a conclusion, have a sequence of steps going from the hypothesis to the conclusion, and then justify the steps. The question is asking whether students can just skip everything except for the steps. They can’t. It’s more basic than detail in calculation. Nov 29 at 8:59
• Your answer is very nice, and it has education value. The contrast between Answer 1 and Answer 2 is valuable. But Will Orrick has a valid point. Answer 1 is using induction in subtle ways. For example, how do with know that $x\cdot x^n=x^{n+1}$ without induction. In fact to even define $x^n$ for a generic $n$ requires induction. Yes, we can define $x^{100}$ without induction, but without induction we can speak of $x^n$ only when $n$ is a specific integer. Nov 30 at 0:28
• I think there may be a 'context' problem with the specific chosen example: while the rational function and the polynomial are equal as elements of $k(X)$, they are not equal as functions from (subsets of) $k$ to $k$, so one should be careful. Also, the closing remark about proofs by contradiction seems to not distinguish those from proofs of negation. Lastly, @user52817 comment may be related to the fact that some theories lack enough induction to prove exponentiation is total, for example Robinson arithmetic
– ac15
Nov 30 at 15:41
• @ac15 Yes, your comment about Robinson Arithmetic is precisely what I have in mind. It is essentially Peano without induction. RA has simple models where exponentiation is not total. In other words, we need induction to define $x^n$. It gets to be unnerving when we start to realize how often we are using induction in "every day math" without being aware of it! Nov 30 at 17:11

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

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.

• Didn't downvote, but just FYI that in the USA, it's not uncommon to see induction covered in a honors precalculus class. See, for example, the popular textbook by Larson. Nov 18 at 7:01
• -1 That's the prototype of a straw man argument. You take a rather natural concept, write it down in the very abstract language of formal logic, and then claim that high schoolers weren't able to understand the concept itself (rather than the language in which you wrote it down). This is like writing a cook book with all the recipes formulated as algorithms in pseudo code, to then claim that most people weren't able to cook. Nov 18 at 8:53
• @Jochen Glueck: write it down in the very abstract language of formal logic --- And not correctly either. $0 \in N$ should be $0 \in P.$ Nov 18 at 12:25
• I don't feel this answers the question. Nov 19 at 6:19
• @DawoodibnKareem The question was. "Does a proof by induction have to explicitly refer to the principle of mathematical induction?" I have argued to contrary. PBI is difficult enough for students without having to also introduce axiomatic number theory. Nov 19 at 20:35