# How to teach Mathematical Induction mathematically?

I am exhausted of teaching Mathematical induction to my little brother. I have given him many examples, Domino effect, aligned shops of hot dogs etc and every time he says that he got it but when I come across the problem mathematically, he starts to gaze at me with Pin-drop silence and it breaks off my attention.

However, it's not my duty to teach him but he is saying that his teacher didn't tell them underlying concept. I am feeling disgraced because I couldn't let him understand it after a enormous trial.

Please tell me how should I explain him?

• Unfortunately, in order to make it possible for others to help, you would have to list everything that you have tried so far, forcing you to relive your painful experience. – k.stm May 9 '15 at 12:27
• The problem is that, I could not make him understand induction mathematically! – Sufyan Naeem May 9 '15 at 12:31
• When I first learned induction i just used logic to explain the situation oh hey if something is true because its one step is true that is $n=1$ , and that if i assume one of it's step is true gives it's next step is true it kind of sets a CHAIN REACTION from n=1 to infinity. – Mann May 9 '15 at 12:32
• Maybe you should start by having him look at some iteratively defined sequences, so he gets the idea of "the next is determined by the previous". For example have him compute the first 10 Fibonacci numbers or something. – Gregory Grant May 9 '15 at 12:47
• No problem done :) – Mann May 9 '15 at 12:49

It seems that some people find it easier to grasp the following "contrapositive" equivalent of the induction principle. (I have no idea whether your brother is one of these people, but it might be worth a try.) If a statement $S(n)$ (about natural numbers $n$) is true for $n=1$ but false for some other value of $n$, say $N$, then there must be some $n$ such that $S(n)$ is true but $S(n+1)$ is false. (Intuitive reason: Imagine counting from $1$ to $N$, and checking, for each number $n$ along the way, whether $S(n)$ is true or false. $S(n)$ starts out true ($S(1)$) but ends up false ($S(N)$), so it must have changed from true to false somewhere along the way.)

• Thank you, it helps a lot! Can you explain where I can use induction and where can't, and write a answer in the question asked by me at math.SE? – tarit goswami Sep 22 '18 at 18:12

You say that your brother says he understands your explanations, but then when it comes to actually proving something mathematical with induction, he can't do it. I know two sources of this sort of non-understanding, because I see them on a regular basis in my Maths Learning Centre when students learn induction for the first time. I'll describe what these sources are and how I deal with them.

Philosophy

The first source is a philosophical issue with it. Some students, no matter how many analogies of dominoes or ladders you describe, will still just feel that it's somehow all a bit too unbelievable. You start by assuming it's true, and prove something with an unknown value of n, and then somehow the thing is proved for all values of n? It seems a bit too much like Baron Munchausen pulling himself up by his own hair. A common phrase the students utter is "it feels like magic". They can't even consider giving it a go with an actual proof assignment question when they feel so philosophically uncomfortable with it.

With such students, I have had success discussing the axioms of the natural numbers. I talk about the axioms of the whole numbers, saying they are based pretty much on the foundation of "There is such a thing as zero", "Every whole number has a unique next number" and "Every whole number (except 0) has a unique previous number". Then I say that mathematicians discovered that in order for a lot of things about numbers to be provably true for all numbers, they had to have induction, and they figured out that just those three rules above weren't enough to be able to prove what they knew to be true. So they had to include induction as one of the rules in the first place. In that sense, I induction is a lot like magic, because it can't be proved to work using simpler rules.

Several students have said they feel better about it after such a revelation because there is no burden on them to understand it by proving it to themselves. It can't be proved analytically, so they don't have to try anymore. This allows them the freedom to rely on the analogy for their understanding, rather than thinking they have to also understand it analytically.

Practical skills

The second source is not having any practical skills for dealing with problems of this kind. Even if a student understands the idea of how induction works, this is a wholly different thing from actually using it in an actual proof. Writing the proof itself is a different skill and often has to be learned separately.

The first key skill is realising what the actual statement is that needs to be proved, and the fact that this statement appears in different forms in four different places in the proof: once with the base case, once with the induction assumption "n=k", once with the induction step "n=k+1", and then once in the final statement which repeats what they were supposed to prove. Without these reference points to hang the proof on, a student can feel very lost, and their proof will not be at all easy to read.

The second key skill is realising how you go about proving equalities, inequalities or divisibility statements (the usual fare for induction proofs). None of them can begin with what you are trying to prove! They must start with an expression and perform manipulations on it until it is in the desired form. I find it works quite well to get students to write one part of the thing they're trying to prove with the "k+1" in it, and next to it a column of "=" signs, with the general shape of the goal at the bottom. For example, if they were aiming to show that $7^{k+1} +2$ was a multiple of 3, then it would look like this: \begin{align} 7^{k+1} + 2 &= \\ &= \\ &= \\ &= 3( \text{something} ) \end{align} Once they have this, they can focus on filling in the bits in between, which helps them focus on just a small part at a time which stops them from being overwhelmed.

The final key skill is realising that while proving the induction step, you must use the induction assumption. Otherwise you'd be able to show it was true without induction. Therefore you should always be looking back to the induction assumption to see if you can figure out how to use it. This gives students a clue for how to come up with the most crucial part of the proof.

• Plus 1 for the advice on "filling in the bits in between." – Frank Newman May 21 '15 at 19:11

This is a version of user @Mann's comment. I owe the ladder metaphor to Joe Malkevitch: (From How To Fold It: The Mathematics of Linkages, Origami, and Polyhedra, p.6.)

I have a pet hypothesis which says that it's easier to explain induction using a non-linear order (sometimes this is called well-founded induction), rather than just natural numbers.

Of course, it might be plain wrong, because all the people who benefited from this approach tried to understand induction over naturals first. Still, you may want to give it a try (you didn't say how old your little brother is, the example might be too silly, I don't know).

An escape from mysterious cave

You are an adventurer in a mysterious cave which looks like this (here draw a graph). Unfortunately, your flashlight died (it's pitch dark) and you got lost.

However, there is a gentle breeze which indicates, for each passage, in which direction the exit is (here direct each edge so that it becomes a strict poset where the exit(s) is(are) the bottom element(s)) - we have to go against the wind.

Prove that you can get away from the cave.

You start with "proofs" that you can escape from halls near the exit, namely producing explicit paths of length 1, 2, 3, whatever necessary.

Then explain that you would like to produce such a path for each hall in the cave, but that would be a tedious task (the cave may have huge number of halls; in math it could even be infinite). Instead, we will show how to produce such a path if we know a path from at least one hall closer to exit.

Induction can be understood as an agreement that such a way of producing paths is just as good as explicit paths.

Now explain why you need base: you can travel inside the cave all you want, you cannot escape it if there is no exit (draw an example).

Explain also why you need all the steps: if some corridor collapses, then possibly some parts of the cave might be cut off (draw an example).

Heap property

We say that a rooted tree (it can be binary, but it's not necessary) has heap property if for any vertex its value is bigger or equal the values of its children.

Prove that the root is at least as big as other values in the whole tree.

Start with drawing an example where values aren't uniformly bigger from one level to the next. Of course, we could take the value of the root and compare it with any other node and that would be enough to prove that in this particular instance it is true.

Next draw an example with symbols like $a, b, c, \ldots$ or $a_1, a_2, a_3, \ldots$. Now we can't compare the root value with any other (we know the inequalities between the parent and its children), but we could write down sequences like $a_{12} < a_5 < a_1$ for each node and it also would be a proof for this instance. However, if the tree is big, that would be tedious. Similarly to the cave problem, instead of providing exact paths you say how to generate them from smaller paths. (Also draw an example where a single node that violates the heap property is enough for the lemma to be untrue.)

And if all is going well, you can then explain how we can do here even better, that is, instead of saying how to generate chains of inequalities for this particular instance, you can describe a way to do it for any tree that satisfies the heap property.

Don't forget to stress why both the base and the step are important. If your brother is eager for more, you can show him how the sum of the first $n$ even numbers is odd, you can describe why all horses are the same color.

If your brother wants even more and you are not afraid to confuse him a bit, you can demonstrate why relation has to be well-founded, e.g. you could prove that zero is strictly bigger than itself.

Consider the set $A = \{1, \frac{1}{2}, \frac{1}{3}, \frac{1}{4}, \ldots, 0\}$. We prove that for all $x \in A$ we have $x > 0$. The base is true, because $1 > 0$. We have that for any $x \in A$ the next element after $x$ is strictly bigger than zero, so the step also works. Hence $0 > 0$.

I hope this helps $\ddot\smile$

This problem may be partly because the core idea of induction is essentially meta-logical. There is a first-order induction schema that we can use to have something like induction in a first-order theory like PA, but the original intuition is not first-order at all. Instead it goes something like this: $\def\nn{\mathbb{N}}$ $\def\imp{\rightarrow}$

Given a property $P$, such that you can prove $P(0)$ and $\forall n\in\nn\ ( P(n) \imp P(n+1) )$, then you would like to be able to draw the conclusion $\forall n\in\nn\ ( P(n) )$.

Why should we accept this? The meta-reasoning goes as follows:

To get $P(1)$, you instantiate $\forall n\in\nn\ ( P(n) \imp P(n+1) )$ with $n = 0$ to get $P(0) \imp P(1)$ and then use modus ponens with $P(0)$ to get $P(1)$. Similarly, to get $P(2)$, you instantiate $\forall n\in\nn\ ( P(n) \imp P(n+1) )$ with $n = 1$ to get $P(1) \imp P(2)$ and then use modus ponens with $P(1)$ to get $P(2)$. And so on. This clearly shows that we can prove $P(n)$ for any specific natural number $n$, just by repeating these deductive steps $n$ times, because we define natural numbers to be exactly the numbers we can get by incrementing $0$ by $1$ finitely many times. In the meta-logic we are already done because we can see that every natural number satisfies $P$, but we need the axiom of induction to derive the universally quantified statement in the formal system itself.

To understand this better, you could actually perform the deductive steps in the meta-reasoning and notice that proving $P(n)$ for large $n$ requires a proof of length proportional to $n$. The induction axiom essentially says that if you are able to prove $P(n)$ for arbitrary natural $n$, you are allowed to conclude $\forall n\in\nn\ ( P(n) )$. The part in bold is a statement in the meta-logic, which you would like to transfer to a statement in the logic.

i am not sure your analogies are good. to my taste the underlying concept of the induction does not map to a process or an action at all.

imho, induction says us, what is true for an arbitrary collection, and KEEPS being true under a certain expansion procedure, then it is true for any collection produced by this procedure infinitely applied to the collection.

it is not an explanation, but it might give you a clue for constructing an explanation.

i would begin with trivial inductive definitions of known things. for example: take a bunch of toothpicks. it is a bunch of toothpicks. add one. is it still a bunch of toothpicks? could you destroy this property by ADDING one toothpick? therefore, this property will hold under infinite addition of one toothpick. we conclude that a bunch of toothpicks will remain defined as such.

induction is the same but applied to a particular property of an initial object...

you can take opposite approach (more illustrative, but less true). take a cup of water and divide it. water remains water under division. -- this is what makes deduction a legitimate way of reasoning -- some property holds, if it holds once it will do INDEFINITELY under the same circumstances. (unfortunately the example with water invisibly change these circumstances, and it is fun to think about too)

• Except the procedure is not applied infinitely, just arbitrarily many times (there is a difference). – Tobias Kildetoft May 9 '15 at 13:16
• yes. and this fact is reflected in typical induction as we prove our "next step" proposition relative to a random "step" in the "future" and NOT just a next step to the currently proven state. P.S. Man! i am ashamed i couldn't do that reasoning when i was in school! – Silly Sad May 9 '15 at 13:22

I do it by presenting and discussing this "Theorem"

Let $X \subseteq \mathbb W$ where $\mathbb W = \{0, 1, 2, \dots\}$ and suppose $X$ has the following two properties

1. $0 \in X$
2. If $n \in X$ then $n+1 \in X$

Then $X = \mathbb W$

We don't really prove it, but we try to convince ourselves that it is true. Then we consider similar theorems for sets other than $\mathbb W$. Once I am pretty sure that they understand the paradigm, then I introduce mathematical induction.

For some reason, I always found it easier to understand if I started with the inductive step, then did the base case. I think it's because I had trouble with the idea of "if it's true for a given step, then it's true for the next step." This may be because of the use of the word "assume" in mathematics. I interpreted the usual base case --> inductive step as "Show it's true for the first case. Now just assume it's (miraculously) true for some case further down the line." By reversing it, it becomes "if it happens to be true for some case, it also happens to be true for the next case. Oh, but it's true for the first case, therefore..."