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?
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.
Talk about impact…
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:
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.
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:
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 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.
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:
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!”.
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.
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.
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.
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.
In my experience, there are two main problems students have with induction:
They cannot clearly write down the inductive hypothesis.
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?
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:
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!
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
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.
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.
A mathematical axiom should be self-evident. It should be unnecessary to explain why something is self-evident.
One should prove mathematical induction based on the self-evident proposition that every set of natural numbers has a least element.
I have found that students immediately understand the truth of that proposition whereas they do not immediately understand the principle of mathematical induction.
Mathematical induction is better approached as a theorem rather than an axiom.