How to teach Mathematical Induction mathematically?

Question

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?

Answer 1

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

Answer 2

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.

Answer 3

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.)}

---

Answer 4

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.

Answer 5

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$

Answer 6

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

Induction says what is true for an arbitrary collection, if it KEEPS being true under a certain expansion procedure, then 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 so INDEFINITELY under the same circumstances. (Unfortunately the example with water invisibly change these circumstances, and it is fun to think about too)

Answer 7

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.

Answer 8

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

Answer 9

I suspect the issue (as many are) is more pedagogical than "explanation based". Instead of looking for some "aha" magic explanation, you need to expose the kid to many example and force him to replicate them. Yes, even if he doesn't "get them". Over and over...and force him to solve problems. And NOT the hardest, most aha kind. But more like variations on a theme (same as example but with slightly varied numbers).

Sometimes things only make sense in retrospect. Like learning your kip as a gymnast. https://stickitgirl.com/blogs/stickitgirl/how-to-help-your-gymnast-get-her-kip

And this is not a troll (Dan). I really mean it in terms of a reframing.

And in the end...the kid will probably even come upon an intuitive explanation. But it will not happen top down. Will happen after exposure and bottoms up familiarity. [Somehow this blows the minds of axiom-based math logicians, but makes total sense to sports coaches...and practical...teachers.]

Answer 10

*Actually I have enough experience of seeing students who don't answer a question but when the lesson is explained they say everything ok and understood. In mathematical induction there are different methods and for each of them there are many different types of questions.

1. The most commonly used method using only one assumption,
   you can start by proving the result is true for n = 1 and then assuming that the result is true for n = p ( p is a positive integer) and use assumption to prove that the result is true in the case of n = p+1. In the other hand you can start by proving the result is true for n = 1,2,... ,k and go on with other steps when you require the condition p ≥ k for the proof in n = p+1 .
   
2. Using more than one assumption,
   As an example you can prove the result is true for n = 1 and n = 2 , then assume the result is true for n = p and n = p+1 . Now you can use both assumptions to prove that the result is true for n = p+2 . By this way you can have even 3, 4 ,....assumptions.
   I think depending on the content of the syllabus and level of the students you need to explain few more examples until they are capable of using this as in any other cases in mathematics.
   Actually I have another issue related to this, that is how can we use the term mathematical induction when this method is considered as a deductive proof.*