# How to teach mathematical induction?

Some students are not convinced that a proof by mathematical induction is a proof. I have given the analogy of dominoes toppling but still some remain unconvinced. Is there very convincing way of introducing mathematical induction? I need something which will have an impact. Are there any real life applications of induction?

-
It's great that they are not convinced! It means you did a good job. What makes you think induction is generally valid beyond the game of moving around letters on a piece of paper, which are associated with this concept? (Please don't use induction in your answer.) –  NikolajK Jun 18 '13 at 12:01
@AndreaMori Huh? Why would you need Peano's axioms to understand induction? –  Jack M Jun 18 '13 at 19:51
Start with the base case of teaching one student (left as an exercise). Now suppose you can teach $n$ students. –  Najib Idrissi Jun 18 '13 at 20:32
@AndreaMori Counting is also one of Peano's Axioms. Kindergartner's can count. PA only formalizes induction after you realize it's obviously true, just like every (traditional) axiomatic system. –  Jack M Jun 18 '13 at 21:51
How do you get everyone in the school to know your secret? Tell one person. –  Blue Jun 18 '13 at 23:03

Use the analogy of dominoes, and then give the real-life example of the sinking of the Titanic: The management of the Titanic realized that the ship was doomed when they realized that the bulkhead that was being flooded would be completely flooded, and that when a given bulkhead was completely flooded, the next bulkhead would undergo the same fate.

-
Good tangible example. –  matqkks Jun 26 '13 at 10:51

I'm surprised everyone seems to be in general agreement that the domino analogy is good. It seems poor to me: what have dominos got to do with proving things? It's a nice metaphor, but it has simply nothing to do with the issue at hand. I don't remember it having been helpful when I came across it before understanding induction, either. Maybe I'm a special case in that regard.

Which brings me to my answer: I would look for theorems that admit a particularly simple inductive proof. I would also relate those proofs to the students in a more conversational language. Ie, rather than:

First, prove it for 0. Then, prove that if it is true for n, it is true for n + 1. So it must be true for all n.

There are two points here that may be confusing:

1. The notion of proving an "if then" statement. I suspect many students initially find it hard to see that an "if then" can even be considered a "statement" at all, people are more used to thinking of them as combinations of statements. The idea of proving "A if B", without even considering whether A is true, seems bizarre. Supposing I proved that if there were a unicorn, it would like tea.
2. The use of a variable $n$ may be an unnecessary distraction for some students with low mathematical ability, many students remain uncomfortable with variables all the way through high school. This is admittedly a less important point.

To beat issue (1), work by example. State a simple theorem and propose to prove that it's true for all numbers (don't say "for all n"! Just point to the number in the statement, written on the board, and say "we'll prove it's true no matter what this is"). Prove it for zero. Then, without proving or stating the inductive step as a separate statement, go right ahead show "well because it's true for 0, it must be true for 1, because...". Then, "but because it's true for 1, we can use the same argument to show it must be true for 2, after all...". Repeat maybe once more. Finish up by pointing out that as the same argument works for any number, you can keep going as far as you need to and the statement is true for all numbers.

Imagine you had never been taught induction, that you were living in an age before abstract mathematics, and remember the principle meaning of the word proof. A proof is what you use to convince your fellow human that something must be true. If you were simply trying to do that, you wouldn't be fussing around with separating out the inductive step as a proposition in its own right, you'd use the much more easily grasped (and much more convincing!) sort of proof by example above. The illustration of why that means it's true for all $n$ is in the language of the proof itself: it's true because we can keep doing the thing we just did two or three times.

-
+1 for showing (at least trying to) how and why the induction step appears, instead of postulating it and then moving on to convince the class that it works. –  Rolazaro Azeveires Jun 18 '13 at 20:24
Yeah, most proofs by induction are awful that way. "Suppose this complicated formula is true for $n$..." What? Why!? –  Jack M Jun 18 '13 at 21:52
I always disliked the dominoes analogy too, it seemed to me to miss the point. +1 for the explanation in the last two paragraphs, that's the way to explain things! –  Josh Chen Jun 18 '13 at 21:59
Do you think the well-ordering principle is intuitive? Why do we take it as an axiom? Why do we accept anything about natural numbers? I consider induction as something that we accept. (Not to object your opinion!) –  user123412 Jun 19 '13 at 2:02
@GilYoungCheong I never claimed all axioms are intuitive or that only intuitive facts should be taken as axioms. I only claimed that induction happens to be an example of an axiom that is intuitive. (Also, I think you meant to reply to my comments under the OP) –  Jack M Jun 19 '13 at 2:18

I use the domino analogy myself, and I think it is the most useful I've seen.

As a different approach I also do the following, which is more difficult to understand, but does serve as a way of introducing certain other useful properties of systems of numbers. Consider the set of counterexamples: i.e. the set of positive integers $n$ such that $P(n)$ is false. If this set is non-empty, then it must have a smallest element. Why? At this point I usually find the youngest person in the crowd by running the "anyone younger than $x(\in\mathbb{N})$ years raise your hand"-algorithm once. After that you can pinpoint the exact point, where the induction had to fail but didn't. Then you can conclude that the contrapositive assumption that the set of counterexamples was non-empty is the culprit.

Of course:

• You also need to have explained proof by contradiction.
• You need to explain that no matter how large the crowd of counterexamples (even infinite!), the "raise your hand" -algorithm will terminate after finitely many steps. Nowadays many students have seen computers and algorithms in school, and actually seem to follow this - might not have worked nearly as well 40 years ago.
• You can also immediately start modifying the process, and discuss, why/how "raise your hand" algorithm might fail, if A) the number of participating people is infinite, and B) we count their ages with infinite precision instead of in full years. Alternately (may be better?) you can return to this "memorable" example, when you discuss the finer points of the order relation of real numbers.

Do it in many ways. One explanation may work for some, another for somebody else. Some may not get the point of any of them, but them's the breaks.

-
I use this approach in freshman calculus, because I will get to completeness of the real number system a few weeks after doing induction, and thus need to discuss the non-existence of a smallest element in some sets of numbers. –  Jyrki Lahtonen Jun 18 '13 at 12:46

I quite like the domino analogy.

The problem with teaching induction - this is from a UK point of view but it probably applies everywhere - is that there is a formal way of setting it out which they have to use, but only makes sense if you're familiar with the construction of the natural numbers.

In particular the formal inductive argument is roughly as follows.
1. There is some set $S = \{n\in\mathbb N : P(n) \text{ is true}\}$.
2. $0\in S$.
3. $k+1\in S$ for every $k\in S$.
4. $\mathbb N$ is defined as the smallest set such that 2. and 3. hold. Therefore $S=\mathbb N$.

But because induction is used so often it's enough to do steps two and three and write induction somewhere on the sheet. In the UK students get a little proof template which they have to learn, but you can pass the exam without understanding it.

A more intuitive explanation of induction is as a contradiction.

Suppose that there is some $n\in\mathbb N$ such that $P(n)$ is false then there must be a smallest $k$ such that $P(k)$ is false. We can show that $k\neq 0$ by checking that $P(0)$ is true, therefore we must have $P(k-1)$ is true, but $P(k)$ is false. But we have shown that $P(k-1)\Rightarrow P(k)$ which is a contradiction.

Notice that for this version is similar to Euclid's proof that there are infinitely many primes, you can even turn that one into an induction, with $P(k)$ the statement that there are at least $k$ primes. You might use this as an introduction.

You should try to get across the idea that induction is shorthand for a deeper argument, rather than present it as an argument in itself. I can't remember all the good examples (I'm not a teacher) but there are some examples of a formulae that are quite tricky to work out, but once you've got them the proof by induction is very quick. So induction is good for lazy people.

-
Your second sentence is exactly the point I was trying to make with my comment above. –  Andrea Mori Jun 19 '13 at 9:43

Have you tried just showing how it works in special cases?

For example suppose you have proved the basis and induction steps for $P(n)$. Now we can show that $P(3)$ holds:

• $P(0)$ holds because that's the basis step.
• $P(1)$ holds because $P(0)$ holds and the induction step says that if $P(0)$ holds then $P(1)$ holds.
• $P(2)$ holds because of the induction step and because $P(1)$ holds.
• $P(3)$ holds because of the induction step and because $P(2)$ holds.

Do this for a few cases and you one should see that if you take any $n$ you can always "climb the ladder" from $0$ to $n$ this way.

-

Maybe try a tiling proof by induction to demonstrate that the assumption of the inductive hypothesis is not "cheating".

My favourite is using induction to prove the tiling of a $2n\times 2n$ L-shape is possible by using $2\times 2$ L-shapes. You can motivate it by saying "look, the shape can be split into $4$ L-shapes of the next size down, if we knew we could tile those then we could tile the whole thing!".

-
+1 for the observation that induction is often more intuitive if done backwards. –  Jack M Jun 18 '13 at 19:49

Here's what I've said in student handouts (for non-mathematicians, so hopefully this is accessible to doubting mathematicians too). It echoes some other answers, but the very slightly different presentation might be helpful for some readers.

Suppose we want to show that all natural numbers have some property $P.$ We obviously can't give separate proofs, one for each $n$, that $n$ has $P$, because that would be a never-ending task. So how can we proceed?

One route forward is to appeal to the principle of arithmetical induction. Suppose we can show that (i) $0$ has some property $P$, and also that (ii) if any given number has the property $P$ then so does the next: then we can infer that all numbers have property $P$.

Let's borrow some logical notation, use $\varphi$ for an expression attributing some property to numbers, and put the principle like this:

Given

(i) $\varphi(0)$ and
(ii) $\forall n(\varphi(n) \to \varphi(n + 1))$,

we can infer $\forall n\varphi(n)$.

Why are arguments which appeal to this principle good arguments? Well, suppose we establish both the base case (i) and the induction step (ii). By (i) we have $\varphi(0)$. By (ii), $\varphi(0) \to \varphi(1)$. Hence we can infer $\varphi(1)$. By (ii) again, $\varphi(1) \to \varphi(2)$. Hence we can now infer $\varphi(2)$. Likewise, we can use another instance of (ii) to infer $\varphi(3)$. And so on and so forth, running as far as we like through the successors of $0$ (i.e. through the numbers that can be reached by starting from zero and repeatedly adding one). But the successors of $0$ are the only natural numbers. So for every natural number $n$, $\varphi(n)$.

The arithmetical induction principle is underwritten, then, by the basic structure of the number sequence, and in particular [this is the crucial point!] by the absence of stray' numbers that you can't get to step-by-step from zero by applying and reapplying the successor function.

-

There is no better analogy; but some of your students may not actually have played with dominoes in this way, so it doesn't come home to them. I suggest bringing some (real) dominoes into the classroom. With a bit of hand-waving, you can explain that the line can be extended as far as you like. Only the ultrafinitists in your audience will doubt you.

-

I remember that I felt more convinced with mathematical induction more after seeing it being derived from the "well ordering principle" of the natural numbers. At that time, the "well ordering principle" was more intuitive for me than mathematical induction.

Perhaps your students will find the well ordering principle more natural than mathematical induction, and will get more convinced if they see it being derived from a possibly more "intuitive" concept.

-

My experience has been that students who grasp how induction is supposed to work generally have little trouble accepting that it does work; the real problem is getting them to understand the idea in the first place. First playing around a bit with simple recursively defined functions can be helpful.

I generally mention the domino analogy, but I tie it very closely to the actual workings of simple induction. That is, proving that $P(k)\to P(k+1)$ is analogous to making sure that the $k$-th domino is close enough to the $(k+1)$-st domino to knock it over. Then proving $P(0)$ knocks over domino $0$, which by virtue of $P(0)\to P(1)$ knocks over domino $1$, and so on. If we’ve done a little with logic, as we often have in a discrete math course, I might actually talk through the fact we’re repeatedly using modus ponens and actually derive $P(0)\to P(4)$, say. Without some such detailed explanation, it really isn’t (and shouldn’t be) at all convincing.

Time permitting, I also like to prove a few concrete cases of the induction step, starting with the first two or three after the base case. Then I’ll point out that the argument was pretty much the same each time and show that I can do exactly the same thing to get from $100$ to $101$, say. At that point most students are reasonably comfortable with the idea that I could fill in the gap to conclude that the $P(n)$ holds through $n=101$. Then we can usually go to the general case without losing too many students: we’re just ‘automating’ the process of getting from $0$ to $n$ for arbitrary $n$.

Whether they convince or not, these two approaches are useful in trying to get across the idea that a proof by induction is often just a legitimate way to say and so on, and they do convince quite a few students.

However, my main serious argument is that any proof by induction is just a proof that there is no minimal counterexample to the theorem and hence no counterexample at all (provided, of course, that we’re doing induction over a well-founded relation): I’ve found that almost all students readily accept that a non-empty set of integers that is bounded below has a least element. I make a point of presenting some induction arguments in those terms, too, though I also present some in more traditional format.

This point of view has the virtue of covering all kinds of induction: weak induction, strong induction, structural induction, and transfinite induction. It even covers some arguments that aren’t usually taught as proofs by induction, like the usual proof of irrationality of $\sqrt2$. Those who get it at all generally seem to find it quite convincing.

-

From a layman's perspective, the two essential constituents of induction are a starting point and neighbourhood. With natural numbers, the starting point is proving P(1) is true, and the neighbourhood step is proving P(n) is true implies P(n+1) is true. Here is a simple application of induction:

If you have a line of coloured balls, how do you prove that they are all the same colour? You note the colour of the first ball and it is the same colour as itself, so P(1) is true. To check the rest of the balls, you simply make sure that any ball is the same colour as the previous ball. If all balls up to the previous were the same colour, then all balls up to the current are the same colour. If you can check that, you have shown that P(n) is true implies P(n+1) is true. All balls are now shown to be the same colour.

-

I like to emphasize that the induction principle (or, more precisely, its contrapositive) is just expressing the idea that we can (in principle) get from 0 to any natural number by counting (in steps of 1, as usual). So if some statement is true about 0 but false about some other number $n$, then, by watching what happens to the statement as we count up to $n$, we will see the statement change from true to false at least once (maybe more often, if it changes back to true). So we get some $k$ such that the statement is true for $k$ but not for $k+1$.

Separately from this, I also follow the procedure in nonpop's answer, showing that, if a statement is true for 0 and preserved to successors then we can deduce it first for 1 and then for 2 and then for 3, etc.

-

As another possible approach for these young skeptics, you might pose the question, what are the essential properties of the natural numbers? Steer the discussion to these fundamental points (or just present them):

(1) 1 (or 0, depending on preference) is a number.

(2) For every number, there is a unique next number, with "next" being a function. $next(1)=2, next(2)=3$, etc.

(3) If a number has a predecessor, it is unique.

(4) 1 has no predecessor.

Draw a diagram something like:

$1\rightarrow 2 \rightarrow 3 \rightarrow 4 \rightarrow ...$

Does this diagram fit all these of 4 essential features? Yes.

Then add 1 or more other points off to the side that are linked in a circular graph not connected to the first diagram, using letters as the nodes.

$a \rightarrow b$

$\uparrow \space \space \space \space \downarrow$

$d\leftarrow c$

Taken together with the previous diagram, the 4 essential features still fit. Somehow, we must introduce another property to eliminate the possibility of such side loops or chains. And this is precisely what the principle of induction does.

Suppose you have a subset $P$ of natural numbers. Suppose $1\in P$. Suppose that if $x\in P$, then $next(x)\in P$. Then argue that $P$ must contain every element of the chain $1 \rightarrow 2\rightarrow...$, but not any of the side loop. You can't get there from here (starting at 1). So, the last requirement is that we must have $P=N$.

-

How about giving an analogy related to genetics .Say if we can prove that if the parents are tall, so will be their children. Then if a person is tall, so will be his children, his grandsons and so on.

-

I've taught a discrete math for computer science course for about two years now and use the analogy of "the wave" at sporting events:

• Some person starts off the wave.
• If the person to your left does the wave, you do the wave as well.

I usually have my students actually do the wave to get a sense for why induction works - something starts everything off (the base case), and as long as there is "energy" propagating forward, it will keep propagating forward (the inductive step). People love it.

I've tended to follow this up by showing the Miller Human Dominoes commercial, which is dominoes made out of people. It's great and I reiterate the idea that there's some initial impulse, and the energy keeps propagating forward. This is your standard dominoes analogy, but it's way more fun. :-)

Since this is a discrete math for computer science course, I often continue onward by talking about induction as a "machine." You start off with a proof that the result holds for 0. Then, you build a magic machine that takes as input a proof that the result holds for some number n, and it produces a proof that the result holds for some number n + 1. CS students are pretty good at getting the idea that you could just sit in a loop and feed in the proof for 0 to get a proof for 1, then a proof for 1 to get a proof for 2, etc.

Hope this helps!

-
Good point about "the wave" - and it reminds me of the phenomenon of the sudden freezing over of a super-cooled lake when a pebble is thrown into it. –  Mike Jones Jul 13 '13 at 14:17

I like the "Stairway to Heaven" example:

Given an (semi-)infinite staircase from the ground up forever. It is promised that if any stair is white, then the stair above it is also white. Once you find the first (or any) white stair, then all the rest above it forever will also be white.

-

I was never "convinced" that mathematical induction was an absolute truth of universe, and it bothered me so much until I thought of it as an axiom of natural numbers. Just as some people were not comfortable accepting axiom of choice (and many magical proofs based on it), I don't think it is a good idea to find a way to "convince" students about it.

For students who want to understand "why" every single statement in mathematics is "true", I think it is important to understand that mathematics is not always about "truth" but it is rather about logical conclusions of certain axioms.

I feel comfortable writing proofs with induction, but I am still amazed about elementary proofs that use induction. Not only induction, but the existence of maximal element of finite linearly ordered set or arguments based on counting finite sets also fascinate me, but I do not try to make it "rigorous" by going deeper on those principles. These are beautiful principles, but that does not mean that we can "prove" why they work.

-

I think the problem here is that mathematical induction may come across to some people as a bit abstract. The domino effect seems quite a decent example, except that there is a lot more explaining to do than just to say that one tile falls and others will follow.

The best way to make your students accept mathematical induction is to make them "suffer" through the pains of calculations. For example,

"Show that for each $n$, $\sum_{i=1}^{n}i=\frac{n(n+1)}{2}$."

and ask them to calculate by hand. It will be very tedious and not satisfactory, because you may have verified for n=10, but you still have a lot more verification to do. Yet this statement is true for all $n$!

You can then show them that one does not have to suffer by using a trick: splitting up the sums $\sum_{i=1}^{n-1}i+n$ and ask them to use the previous results that they have established, and show them that this trick works in general for all n.

Using this as an example, you can then show them the proof in general and how it leads to mathematical induction. A mathematical induction in short is a way of telling people how the machinery of calculation works (that is it is based on the result of the previous calculation)

-

Tell your students that $\omega$ is the smallest inductive set

-

In my experience, there are two main problems students have with induction:

1. They cannot clearly write down the inductive hypothesis.

2. They think that mathematical induction is a technique used (only) to prove summation formulas for series of numbers.

I have been teaching an algorithms class recently. I have seen many students who have in fact had a discrete mathematics course in which mathematical induction was covered, but who are completely baffled by inductive arguments applied to finite graphs. I spend a lot of time talking about the inductive hypothesis, and insisting that they write down explicitly what it is in their proofs. We work out lots of problems in elementary graph theory in class. Eventually, most of them do get the idea, but it seems to be a very subtle and sophisticated notion for students.

I'm particularly interested in this because these are all Computer Science students, and every one of them knows how to write a recursive function. And even though (from my point of view, at least) the understanding needed to write a recursive function is pretty much the same as that needed to write an inductive proof, it evidently doesn't seem that way to most of my students. I too would really like to understand better exactly what the difficulty is as seen by the students. I have some ideas, as I've indicated above, but I do have the feeling that I'm missing something big.

And by the way, I think that toy examples aren't useful. I can't imagine dominoes helping anyone understand how to write an inductive proof. But maybe I've misunderstood how that explanation is used?

-

You could modify the domino analogy by pointing out that, if some of the dominos are not properly set up, and wouldn't be knocked over by the previous one, it becomes no longer true that $\phi(k)\implies\phi(k+1)$, and hence the induction step will not be provable. You could also attack Zeno's paradox, first proving that if there's space between one $\sum_{k=0}^k\frac{1}{2^i}$ and $2$, there's space between $\sum_{k=0}^{k+1}\frac{1}{2^i}$ and $2$. A realworld application isn't as effective or to the point as a scenario they can vividly imagine, and Zeno situations are something many people have thought about and sought to logically establish.

-

Bearing in mind that mathematical induction is an axiom, it can be interpreted as "If there are no appearing obstacles/boundaries to stop us, then we can walk as we wish". (not a translation/modification of any kind of quote, just threw off my head).

-

you could use programming for induction proof:

see,

#simple func which returns sum of the arguments
>>> def func(x, y):
...     return x + y
#range from 0 to 9
>>> r1 = range(10)
>>> r1
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
#range from -10 to -1
>>> r2 = range(-10, 0 , 1)
>>> r2
[-10, -9, -8, -7, -6, -5, -4, -3, -2, -1]
#range from 20 to 29
>>> r3 = range(20,30,1)
>>> r3
[20, 21, 22, 23, 24, 25, 26, 27, 28, 29]
>>>


we know that:

if a>0 and b>0 than a+b>0
if a<0 and b<0 than a+b<0
if a>0 and b<0 than a+b>0 (if -b < a) ... etc


now we could see it:

#map parameters from list1(x) and list2(y) and call func with func(x,y)
>>> map(lambda x, y: func(x,y), r1, r2)
[-10, -8, -6, -4, -2, 0, 2, 4, 6, 8]
>>> map(lambda x, y: func(x,y), r3, r2)
[10, 12, 14, 16, 18, 20, 22, 24, 26, 28]
>>> map(lambda x, y: func(x,y), r3, r1)
[20, 22, 24, 26, 28, 30, 32, 34, 36, 38]
>>>
`

i hope it helps.

-

Since we are discussing how to prove non-provable statements, I think you should first make sure that the students understand that, even though you are trying your best to not use a proof in this case, proofs are absotively, posolutely desirable in almost every single other case.

Next, I think the important thing to stress is that, for those few statements that you can't prove (axioms), the acceptance/nonacceptance of those statements depends on their usefulness. I consider an axiom to be useful if it can prove many interesting statements without making any contradictions. For instance, many mathematicians accept the axiom of choice for precisely this reason: although it is unintuitive, it is still profoundly useful without being contradictory.

In other words, you should challenge your students to live their (mathematical) lives without ever applying the induction axiom. Show them how much math they would be missing out on - how many useful and elegant theorems they would be unable to prove without inducting. Also stress that induction is not contradictory (so far as we know); if your students really hate the induction axiom, they should try to derive a contradiction from it.

-
Wait a minute... How is the axiom of choice more useful than the axiom of determinacy? Isn't this still completely subject to one's personal opinion? Furthermore, as you know, we don't even know that ZF is consistent, so we can't say that ZF is useful by your criterion, because it may turn out to be contradictory. The reason why people accept ZF is generally because they can do what they want with it. –  user21820 Dec 26 '13 at 10:56

You are in line at Taco Bell. The first person in line orders a cheesy gordita crunch.

Also, if the person in front of you orders a cheesy gordita crunch, you order it too, because it sounds so good.

How many people in line order cheesy gordita crunches?

-

I think that what your students really don't understand is the Axiom of Induction, one of the Peano Axioms, which defines the term Natural Numbers.

A proof that using mathematical induction contains two part:

Part 1: Prove that the desired proposition satisfies the requirement of Axiom of Induction, which is usually showed in a fashion like "base case ... case n ... case n+1".

Part 2: Once Part 1 is finished, the QED is just a sentence away: By Axiom of Induction, the desired proposition holds for all natural numbers.

The correctness of such a proof is no more mysterious than any other proofs: In Part 1, you made sure that the desired proposition satisfies an already-true proposition (in this case, Axiom of Induction), thus you can apply the already-true proposition to the desired proposition to get a true proposition, which is Part 2.

I don't think you can help your students understand the Axiom of Induction, it's called an axiom for a reason. It's a formal statement of the intuition we have on natural numbers, and it takes a lot to understand an intuition.

-

## protected by Alexander Gruber♦Jun 19 '13 at 23:32

Thank you for your interest in this question. Because it has attracted low-quality answers, posting an answer now requires 10 reputation on this site.