Students find mathematical induction hard, and there is a complex interplay of reasons why. Some years ago I wrote an answer on the Maths Education Stack Exchange describing these and it’s still something I come back to regularly. I’ve decided to post it here too.

Some reasons why students find mathematical induction difficult.

These come from a combination of reading various research articles and my own experience helping students in the Maths Learning Centre.

1. Many students don’t know what proof is.
2. Many students don’t realise it’s actually about statements.
3. Many students don’t have experience in manipulating inequalities and divisibilities.
4. Many students are philosophically uncomfortable with it.
5. Many students find analogies unhelpful.
6. Many students don’t know what to focus on to come up with something to prove.

Below I give further explanation of each point.

1. Many students don’t know what proof is

For many students, the problem with induction proofs is wrapped up in their general problem with proofs: they just don’t know what a proof is or why you need one.

Most students starting out in formal maths understand that a proof convinces someone that something is true, but they use the same reasoning that convinces them that everyday things are true: empirical reasoning. That is, in everyday life they can use several pertinent examples to convince themselves something is true, so they do the same with maths. If you ask them to prove that, say, all prime numbers beyond 3 are one more or one less than a multiple of 6, they’ll say “7 = 6+1, 11 = 12-1, 13 = 12+1, 17 = 18-1, so yes it’s true”. They transfer this approach to mathematical induction too [2].

After some experience with maths teachers, students become aware that this is unacceptable. For many it is literally unacceptable in the sense that “my maths teacher doesn’t accept this sort of thing”. So, they learn to apply other methodologies, such as manipulating symbols [2], and think that now this constitutes proof, because it is what is convincing to their teachers. They will attempt to apply symbol manipulations to an induction problem, which often won’t work, because the logical structure of induction is different to their previous experience.

It’s probably a good idea to get the students to discuss what constitutes a proof, and bring out ideas of why it’s necessary to use certain ways of arguing in maths.

2. Many students don’t realise it’s actually about statements.

You can define mathematical induction as being sure the statement “true for n=1” is the truth, and being able to transform the statement of “true for n=k” into the statement “true for n=k+1”. As such, it’s actually something you do to statements, rather than objects or numbers per se. That means it’s much closer to propositional calculus than, say, a geometry or algebra proof. If your students have learned any propositional calculus, this has a chance of help them [1], (though in my experience, sometimes it gets in the way).

In any case, knowing it’s about statements helps them to structure their proof appropriately because they know it hangs upon certain statements in certain places. This is something many students don’t realise about proofs in general, and I find it really helps them to focus their attention when they prove almost anything.

3. Many students don’t have experience in manipulating inequalities and divisibilities

Whether students are attacking induction proofs operationally or with an understanding of how the idea actually works, they often don’t have the operational skill with the types of algebraic manipulations required [3]. Standard fare for induction proofs are inequalities and divisibilities, and most students I meet simply don’t know how to reason with these, even if they’ve done the highest level of maths at school.

For example, consider a sequence of working like this:
(n+1)²
=n²+2n+1
>2n+2n+1
≥2n+6+1, since n≥3
>2n+2
=2(n+1)
Most students don’t understand that each equality/inequality symbol only refers to the step immediately before it, so that the final statement is actually (n+1)²>2(n+1). They also don’t realise you can replace the “6+1” with “2” because you want to make a statement that one number is bigger than another. Moreover, they don’t have well-developed instincts for what they should choose to do next to advance towards the goal.

Divisibility proofs generally involve rewriting things so that they have the divisor out the front, both for the k and the k+1 case. Many students don’t realise this is what divisibility means, and also have trouble seeing how to split up the expression to sub in the induction hypothesis.

If you show any examples of doing a proof by induction in these situations, you’re going to have to be extremely explicit about your ordinary algebraic reasoning at every step, and how you made the decision of what to do on every line, so that you can help them develop these skills.

4. Many students are philosophically uncomfortable 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.

Partly this is due to them not understanding that you actually aren’t assuming it’s true for any specific value of n at all. You’re doing a thought experiment of what would happen if it was true for n=k [3]. I use the phrase “suppose true when n=k” rather than “assume true when n=k” to emphasise this.

Even if they do realise this, some students still want to somehow prove to themselves that it’s ok to just say “therefore it’s true for all n”. A mathematically mature student will often understand things by proving to themselves that they work (such as deriving the quadratic formula). However, you can’t derive mathematical induction. It’s an axiom. Telling them this removes the burden of proof and they can feel slightly better about using it. Alternatively, you could prove it from the well-ordering of the natural numbers, and that might make them feel better if they think the well-ordering is a more obvious sort of axiom to use.

5. Many students find analogies unhelpful

Everyone always advocates using the domino analogy for teaching induction, but there are problems with this. One is that some students simply will have never seen dominoes set up in a line to knock down! If you’re going to use this analogy, bring actual dominoes!

A second problem is that if you are not very specific about exactly what in the domino analogy corresponds to what in the induction proof, students will develop unhelpful ideas about induction. This of course goes for any analogy you might use, such as climbing a ladder or a game of whispers [4].

Worse than this is the problem that no amount of very salient analogies will actually help them to attack an actual problem when faced with it [5]. Analogies are really only good for helping them understand how induction works in a general way. You’re going to have to give them examples and experiences of the act of coming up with a proof because that is a separate skill from describing how induction works in a general way.

6. Many students don’t know what to focus on to come up with something to prove

Students can actually become quite successful in solving your standard identity, inequality and divisibility induction proofs. But anything other than this leaves them completely stumped. Mostly this is because they have learned some standard classes of problems and how to deal with them. (Many students actually think this is what mathematics is — a list of problems and how to solve each one!)

When faced with something entirely different (eg the Tower of Hanoi, or a visual pattern), they don’t know what to focus on. First, you need to help them find where the natural number is that describes the possible situations [3]. Induction only works on natural numbers, and is the gold standard of proving things for all natural numbers, so you really need to look for a natural number! But it has to describe the situation well.

After this, some authors suggest getting them to focus on a process pattern generalisation [2,3]. That is, figure out how you would move from size 1 to size 2, from size 2 to size 3 etc, and see if you can figure out if the process of moving from one size to the next follows a pattern. This pattern is the shape of your proof of “true for n=k implies true for n=k+1”.

An unhelpful thing to focus on is verifying that the formula works for each number in turn. This is just reinforcing their empirical reasoning, which won’t help them figure out how to prove! [2]

References:

[1] Dubinsky, E. (1986) Teaching Mathematical Induction I, Journal of Mathematical Behavior, 5, 305-317

[2] Harel, G. (2002) The Development of Mathematical Induction as a Proof Scheme: A DNR-Based Instruction, in Campbell, S. & Zazkis, R. (Eds.) Learning and Teaching Number Theory: Research in Cognition and Instruction, Greenwood Publishing Group

[3] Palla, M., Potari, D. & Spyrou, P. (2012) Secondary school students’ understanding of mathematical induction: structural characteristics and the process of proof construction, International Journal of Science and Mathematics Education, 10, 1023-1045

[4] Ron, G. & Dreyfus, T. (2004) The use of models in teaching proof by mathematical induction, in Proceedings of the 28th Conference of the International Group for the Psychology of Mathematics Education, 113-120

[5] Segal, J. (1998) Learners’ difficulties with induction proofs, Journal of Mathematical Education in Science and technology, 29, 159-177