Why are induction proofs so challenging for students?

Question

This forum already has many good, simple examples of induction proofs, a great resource. As I am soon to teach induction for the $n^\textrm{th}$ time—this time to some perhaps under-prepared college students (in the US)—I would like to understand why induction proofs are often challenging for students to grasp. Perhaps I have been at it so long that I am losing sight of what makes it difficult.

I would also be interested to hear if you think in fact induction proofs are not challenging to your students.

Answer 1

The following list comes from a combination of reading various research articles and my own experience helping students in my Maths Learning Centre for the last seven years.

Some reasons why students find induction difficult:

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.

And here's some further explanation of each:

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, 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 may help them. [1]

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: $$ \begin{align*} (n+1)^2 &= n^2 + 2n+1\\ &> 2n + 2n + 1\\ &\geq 2n + 6 + 1 \quad \text{Since } n \geq 3\\ &> 2n + 2\\ &= 2(n+1) \end{align*} $$ 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 > 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

Answer 2

In my experience, the biggest issue is that students don't have a clear grasp of quantifiers, so they don't see the distinction between "for all n P(n)" and "consider an n such that P(n)". This leads to common errors like using P(n) to prove P(n), or to thinking the method is circular because we assume P(n) to prove P(n).

Answer 3

There is a fair amount of research on students' understanding of (and difficulties with) proof by induction. Some good places to start:

Palla, M., Potari, D., and Spyrou, Panagiotis. (2012) Secondary school students' understanding of mathematical induction: Structural characteristics and the process of proof construction. International Journal of Science and Mathematics Education 10(5), 1023-1045.

The abstract of this paper reads:

In this study, we investigate the meaning students attribute to the structure of mathematical induction (MI) and the process of proof construction using mathematical induction in the context of a geometric recursion problem. Two hundred and thirteen 17-year-old students of an upper secondary school in Greece participated in the study. Students’ responses in 3 written tasks and the interviews with 18 of them are analyzed. Though MI is treated operationally in school, the students, when challenged, started to recognize the structural characteristics of MI. In the case of proof construction, we identified 2 types of transition from argumentation to proof, interwoven in the structure of the geometrical pattern. In the first type, MI was applied to the algebraic statement that derived from the direct translation of the geometrical situation. In the second type, MI was embedded functionally in the geometrical structure of the pattern.

A second good paper is:

Stylianides, G., Stylianides, A. and Philippou, G. (2007) Preservice teachers’ knowledge of proof by mathematical induction. Journal of Mathematics Teacher Education 10(3), 145-166.

The abstract reads:

There is a growing effort to make proof central to all students’ mathematical experiences across all grades. Success in this goal depends highly on teachers’ knowledge of proof, but limited research has examined this knowledge. This paper contributes to this domain of research by investigating preservice elementary and secondary school mathematics teachers’ knowledge of proof by mathematical induction. This research can inform the knowledge about preservice teachers that mathematics teacher educators need in order to effectively teach proof to preservice teachers. Our analysis is based on written responses of 95 participants to specially developed tasks and on semi-structured interviews with 11 of them. The findings show that preservice teachers from both groups have difficulties that center around: (1) the essence of the base step of the induction method; (2) the meaning associated with the inductive step in proving the implication P(k) ⇒ P(k + 1) for an arbitrary k in the domain of discourse of P(n); and (3) the possibility of the truth set of a sentence in a statement proved by mathematical induction to include values outside its domain of discourse. The difficulties about the base and inductive steps are more salient among preservice elementary than secondary school teachers, but the difficulties about whether proofs by induction should be as encompassing as they could be are equally important for both groups. Implications for mathematics teacher education and future research are discussed in light of these findings.

You may also want to look at this link to a PME-NA paper by Tommy Dreyfus and Gila Ron which describes "explanations, models and examples that distort the underlying mathematical ideas and show teachers’ conceptual difficulties" with mathematical induction.

Answer 4

For CS students specifically, there is another approach that would work better than the usual way induction is taught, namely by teaching structural induction, which goes like this:

If you want to prove that a collection $S$ of finite structures (such as binary trees) satisfy a property $P$, then all you have to do is to show that for any arbitrary structure $x \in S$ that I give you, you can do either of the following:

1. Show me that $x$ satisfies $P$ without any assumptions.

2. Break $x$ down into strictly smaller structures such that, if I show you that all of them satisfy $P$, then you can show me that $x$ also does.

Now this may seem silly, as it is even stronger than induction, and involves the same essential steps. But it is very different, because students always (wrongly) take a structure of size $n$ satisfying $P$ and build a structure of size $n+1$ from it and shows that it satisfies $P$, and then claim that by induction all the structures satisfy $P$! Using this formulation of strong induction, that mistake is prevented from happening, because they have to start from an arbitrary structure and reduce it to smaller structures.

This doesn't solve the problem of not understanding the logical underpinnings of induction, but at least it solves the problem of using induction wrongly. The other important point is that it presents the quantification involved as a game, which some students grasp much faster than quantifier chains.

There is another advantage that this has for CS students over the usual presentation of induction, which is that following the proof it is easy to construct the recursive algorithm corresponding to it. For example the proof that every finite binary tree has a depth translates straightforwardly and cleanly into the recursive algorithm. Also, the recursive structure lends itself immediately to the idea of storing the relevant data in each substructure, in this case the depth of each subtree.

Answer 5

Lots of good answers here (I've upvoted many). I'm won't try to add to the discussion about why induction is hard, but I can suggest some approaches that have helped some of my students.

Many have seen induction as an algebra exercise - for example, summing the first $n$ squares. Those examples are tedious and work badly. Students have trouble with the hypothetical "Suppose it's true for $n$ ..." and you find yourself trying to answer their "How do you know it's true for $n$?"

I like to start with well ordering, without even calling it induction. Students have little trouble accepting the fact that a nonempty set of positive integers must have a least element. Then you can prove lots of things by showing that a minimal counterexample leads to a contradiction. (I think that's worth doing in spite of my preference for direct rather than indirect proofs.)

For example you can start the fundamental theorem of arithmetic (FTA)- every integer is a product of primes in at least one way - by looking at the smallest integer for which it fails. (One pedagogical problem here is that they don't think the FTA needs to be proved. Examples of rings in which it fails usually take more class time than one can afford.)

The uniqueness in the FTA follows from the same kind of argument if you grant the lemma that a prime dividing a product must divide one of the factors.

That lemma follows from the extended form of the Euclidean algorithm, asserting that the $\text{gcd}(m,n)$ is an integral combination of $m$ and $n$. You can prove that by induction - a minimal counterexample leads to a contradiction with one application of division with remainder.

The actual computation of the coefficients for the linear combination giving the gcd is a classic recursive program - well worth doing in a course with both math and cs students. Just reading the code in an easy language like python is instructive - no need for them to write it. As has been noted in other answers. learning recursion and learning induction reinforce each other.

With well ordering in hand you can tell the classic joke: every positive number is interesting. If not, then the least boring integer is an interesting number. Be sure to distinguish between least (boring integer) and (least boring) integer.

Well ordering helps students understand the traditional formulation of induction and implies it: consider proposition $P(n)$ about positive integral $n$. If $P(1)$ is true and the truth of $P(n)$ implies that of $P(n+1)$ for all $n$ then $P(n)$ is true for all $n$. Just look for a minimal counterexample. To prove that the traditional formulation implies well ordering, consider a set $S$ with no least element and let $P(n)$ be the proposition "$S$ has no elements less than or equal to $n$". Then $P(1)$ is true, since if $1$ were in $S$ it would be the least element. If $P(n)$ is true then $P(n+1)$ is too, lest $n+1$ be the least element of $S$. The truth of all the statements $P(n)$ clearly implies $S$ is empty.

If you have time, teach Fermat's method of descent by going through Euler's proof that $x^4 + y^4 = z^2$ has only trivial solutions.

Well ordering also helps focus on the "inductive step" rather than the base case (as another answer recommends). That inductive step is central in lots of combinatorial arguments. You can show that the cardinality of an $n+1$ element set is twice that of an $n$ element set without knowing a formula for the latter. The recursion for counting combinations works the same way. Then you have a nice inductive proof of the formula by showing it satisfies the same recursion.

The pattern I'm recommending might be called "induction in disguise." The formal structure is there, but appears as simple common sense rather than formidable logic with quantifiers and hypotheses and algebra.

Hope this helps.

Answer 6

I think the main problem students have with induction proofs is that the ordinary direct proof works by reducing a statement with unknown truth value to one that is known as true.

The bulk of an induction proof however is reducing a statement with unknown truth value to a statement with unknown truth value. And not just that, it's even the same statement, just with a trivial variable substitution.

So essentially the bulk of the induction proof appears like a big tautology only very superficially masked with a rather transparent shell game.

Now confronted with all this major bulk of self-referential weirdness it is easy to forget that all of it hinges, after all, on the truth of the proposition for $n=0$. So suddenly some specificness creeps into all that circular logic (which actually is not circular as much as spiralling).

The bulk of the work seems mostly of the kind that you have been painstakingly taught to recognize as meaningless because of being tautological.

It's like opening window blinds by drilling a tiny hole in them. Particularly if you are a skilled handiworker, it appears quite absurd as an interface to seeing the whole light.

The fifth Peano axiom and the abstract induction proof structure are easy to pin down and have some intuition. But the bulk of the actual hard work in an induction proof looks like something else entirely.

Distinguishing an actual tautology from a valid induction step requires a deep understanding separate from the skills needed for doing the bulk of the work. Being secure in the mapping from the proof structure to the required work requires practice, confidence, and understanding. With most other math work, you can learn the steps first and get the understanding some time later.

That's a bit more danger-fraught with induction.

Answer 7

As someone who took math courses but does not teach, I would claim that inductive techniques are taught with two rather separate approaches:

• A step-by-step recipe to take a problem that tells you to use induction and write down the series of symbols such as "n" and "n+1" in the right order to get full credit for the problem.
• An understanding of how induction actually works, and why we use it.

Induction is a very axiomatic process. If you try to dig down to the "rule" that shows that it works, it ends up being the Axiom of Induction from the Peano Axioms. Its actually the only second order axiom in the entire set of Peano Axioms! Induction is so fundamental that we don't even have an explanation for why it works; we accept it as an axiom for use in proofs involving natural numbers.

If a student has not developed a strong inductive reasoning skillset, this axiom will appear foreign to them. they may be able to see that f(0) f(1) f(2) and f(3) are all true, leading onwards, but the step to f(N) is true for all N is actually a leap of logic requiring students to develop a way to use their brains that they didn't use before. (On the other hand, if a student has strong inductive reasoning skills, they may pick it up quite easily, frustrating all of their friends.)

I do know that many approaches for teaching mathematics decry intuitive approaches such as induction until the day they show inductive proofs. In many situations (especially proofs), its deductive logic or bust! If a student is not aware that it's okay to think inductively in mathematics, they may have put up barriers to prevent themselves from doing something that gets them a bad grade. Inductive proofs are deemed an acceptable way to put inductive reasoning into a field that is otherwise taught as deduction-dominated, so it takes a while for them to click. You may have to nurture them to encourage it.

Just to brainstorm a potential solution (I haven't tried it yet), try to give students a simple induction word problem, and ask them to "convince themselves" that the statement in the problem is true. They don't have to "prove" it mathematically, they need to prove it to themselves enough to feel comfortable that the statement is true, and write down their logic on the paper. Then you can look at what they have done, and try to identify the spark of induction in their work, and try to kindle it into a form that you can give traditional mathematical syntax to. We all do inductive logic (its one of the major branches of thought as defined by the Greek philosophers), so its just a matter of convincing them its safe to use it.

Answer 8

I have no evidence for this, but I speculate that one reason students are so bad at induction is that it is so unlike real world reasoning. In ordinary English, we say things like "If I miss the bus, I'll be late to work." Well, maybe not! Maybe a friend will happen to drive by and offer me a ride! Maybe there will be a fire alarm at work, and everyone will start an hour late today. What one really means is "If I miss the bus, there is a high probability (say 95%) that I'll be late to work."

Now, start stacking those implications: "If I miss the bus, I'll be late to work." "If I'm late to work, the students who are waiting for my office hours will be annoyed with me." "If my students are annoyed with me, they'll write poor evaluations of my course." ... and eventually you end with "If I miss the bus, I'll be living homeless in People's Park." Most of us understand that stringing together long chains of causation like this is invalid, roughly because $(0.95) \times (0.95) \times (0.95) \times \cdots \times (0.95)$ gets small pretty fast.

I think that this innate revulsion to long logical chains is a problem for students getting used to any kind of mathematical proof. But it is particularly bad for induction, because the chain gets longer at every step. Outside of mathematics, is there any chain of argument with a dozen if/then links which you would accept?

Answer 9

Logic foundation

In my opinion, the only way for anyone to really understand induction is to really understand the logical structure behind it. So a prerequisite is a complete grasp of working in first-order logic, for which I recommend both boolean algebra and natural deduction (Fitch-style) in conjunction. It is unfortunate that many people, teachers and students alike, don't actually appreciate how important this is, and hence they try to teach induction to students who are so weak in logic that they cannot possibly know what they understand or do not understand about induction.

In contrast, for someone who is capable of working in first-order logic, the axiom of induction would be trivial to state and easy to use with confidence. Not only that, when students are at that point they will understand the subtle difference between reasoning in first-order logic and reasoning outside, which is crucial to a full understanding of induction. The reason is that induction has a meta-logical basis, not a logical one. All the other deduction rules are trivial to check via truth-tables, but the underlying intuition for induction is not at all the same. $\def\nn{\mathbb{N}}$ $\def\imp{\rightarrow}$

Intuition for Induction (after the logic foundation is firm)

Basically we could define natural numbers as exactly those that we can get by counting upwards from $0$. What does counting upwards mean? Well, the usual one, which is incrementing the previous number by $1$. Using the decimal system it would go $0,1,2,3,4,5,6,7,8,9,10,\cdots$. For simplicity let's just assume that for any natural number $n$, $n+1$ is the next natural number after $n$.

Now let's say we have some 1-input predicate $P$ on the natural numbers and we have proven:

$P(0)$. (1)

$\forall n \in \nn\ ( P(n) \imp P(n+1) )$. (2)

Without induction, what can we do? Certainly, one can prove:

$P(0) \imp P(1)$ [from instantiating (2)]. (3)

$P(1)$ [from (1) and (3)]. (4)

$P(1) \imp P(2)$ [from instantiating (2)]. (5)

$P(2)$ [from (4) and (5)]. (6)

...

It is now clear that given any natural number $n$ written in decimal notation, one can prove $P(n)$ by continuing the above proof up to a length of $2n$ lines. Of course, this fact about what we can prove is not something proven within the formal system itself, but is an external fact observed from the outside. All this fact requires is that we have the same common understanding about strings from a fixed alphabet (with which we form proofs) and how we can manipulate strings (joining them together, reading each symbol in order, ...). But it is not a fact provable within the formal system. In other words, this fact is a meta-logical fact. "Meta-logic" means "about logic", since we're now thinking not within the logical framework we set up but thinking about the logical framework from the outside.

So there are two questions:

(A) Is it true that for any $n \in \nn$, there some proof that $P(n)$ is true? Yes, and we've shown above how to construct one.

(B) Is it true that there some proof that $P(n)$ is true for any $n \in \nn$? No!

And this is why we want to have the axiom of induction, because if our deductive rules are sound, then according to our definition of natural numbers the answer to (A) shows that in fact $\forall n \in \nn\ ( P(n) )$ is a true assertion, and so we are justified in adding induction as an axiom so that the answer to (B) becomes "Yes".

Together with the earlier comment about the meta-logical intuition behind induction, it should now be even clearer why the induction axiom is really a meta-logical axiom intrinsically. The quantification in (A) is outside the formal system with the usual deductive rules, while the quantification in (B) is inside the formal system. It essentially stipulates that whenever we can systematically generate a proof of $P(n)$ for every $n \in \nn$ in the above manner, we can transfer this meta-logical universal quantifier inside the formal system itself.

Notes (only for the teacher, not the student learning induction!)

I used "decimal system" in my above explanation so that it is understandable to those who are not familiar with formal systems, but of course one has to be careful with the difference between the natural number and an encoding of it. In formal logic, usually the language of arithmetic only has a single constant $0$, the successor function symbol $S$, and addition and multiplication function symbols, and of course equality. In that case there may be no such thing as decimal notation in the formal system itself, but it's no harm to add them in, for example we use "$3$" instead of $S(S(S(0)))$".

Also, induction does not imply that (A) always implies (B). If (A) always implies (B), then the formal system is ω-complete. However, PA is ω-incomplete if it is consistent, because it cannot prove $\mathrm{Con}(PA)$, which is a sentence of the form $\forall n\ ( \neg \mathrm{CodesAProofOfFalse}(n) )$, even though it can prove $\neg \mathrm{CodesAProofOfFalse}(n)$ for each natural number $n$ encoded as $\underbrace{1+1+\cdots+1}_{\text{$n$ times}}$.

Finally, note that throughout this answer, in the meta-logic "natural number" refers to the true natural numbers (which is ultimately undefinable), while in the logic "natural numbers" are simply defined by the properties they obey, such as the axiom of induction. The axioms including induction serve as part of how we characterize the natural numbers, but no recursive axiomatization can ever fully characterize them. So although the true natural numbers are exactly those that we can get by counting upwards from $0$, there will never be a systematic non-circular definition of them. (In particular, "we can get by counting upwards" presupposes natural steps.)

Answer 10

A short, true story.

Two years ago, working with a colleague, we found what we thought was a beautifully clean induction proof of an old theorem that had, 'til then, only a complex, intricate proof, standing unimproved for ~25 yrs. We started to write it up for publication, only to realize that the base case—which we thought was obvious—could sometimes fail. We were unsuccessful in repairing the new proof, and have since pretty much abandoned the pursuit.

This is my only experience with an induction proof floundering on the shoals of the base case.

Answer 11

Seems to me that there are (at least) two types of induction problems: 1) Show something defined recursively follows the given explicit formula (e.g. formulas for sums or products), and 2) induction problems where the relation between steps is not obvious (e.g. Divisibility statements, Fund. Thm. of Arithmetic, etc.).

For 1) the problem typically seems to be that students don't understand the recursion, e.g. that $\sum_{i=1}^{n+1}f(i) = \sum_{i=1}^nf(i)+f(n+1)$. If they do understand this (but still can't do it), then they are typically just weak in the algebra skills required to manipulate after the inductive substitution.

For 2) the problem is just that: the relation between steps is not obvious and some intuition/experience is required to find the $n$th statement within the $(n+1)$th case. (Heck, even I struggle with this at times when going over homework problems.)

A note on base cases: There are a few instances I've noticed where the base case is so simple that students struggle to know what to write down to prove it. For example, they'll write something trivial like $0=0$ with a check mark instead of $1^2-1=0=\frac{1}{3}(1-1)(1)(1+1)$. I think this just comes from years of schooling that emphasized the end result (and omitting mental calculations in work shown) instead of the process that brought it about.

Answer 12

The reason why learning mathematical induction is difficult is developmental. Your audience of under-prepared college students probably accept "proof by verifying the first few cases" as more convincing than proof using the formalism of mathematical induction. Sure, they grasp that "proof by verifying the first few cases" is somehow inadequate, even though they find it convincing. But proof by mathematical induction to them is too abstract and formal, and hence not emotionally convincing.

It just takes time for mathematical maturity to develop. Gradually mathematical induction becomes less abstract and eventually it seems intuitive and obvious. Analogy: it was really hard to learn how to tie my shoe laces when I was young, but now I am bewildered when I see a young person having difficulty learning how to tie their own shoelaces.

Answer 13

I've noticed that the main problem is in how people teach induction. Often teachers use examples with number theoretical identities or other examples which by their nature require understanding something else in addition to induction. In my opinion, induction should be taught by itself first in isolation with hypothetical "Hilbert hotel" type scenarios.

For instance, consider an infinite lunch line of students. A student in line will laugh if the student in front of him/her laughs. If the first student in line laughs, is there a student that will not eventually laugh? Have your students think this out.

Now consider the same example, but now a student in line will laugh if two or more students ahead of him/her laughs. The first student in line laughs, what happens now? Can you be sure every student end up laughing?

Here's a final example. Suppose the rule is now that a student will laugh for certain if there is a student two spots ahead in line and that student laughs. The first student in line laughs. Which students will laugh? Suppose instead of the first student, the second student laughs. What happens?

Answer 14

As already touched on here, perhaps proof by induction should not be the first real method of proof that students learn. (The two-column proofs of geometry common in North American schools don't really count somehow.) Perhaps it ought to be the culmination of an introductory course on the basic methods of proof.

In the self-study, interactive tutorial that comes with my DC Proof software (a free, downloadable proof checker), I present other more elementary methods first:

1. Direct proof
2. Proof by contradiction
3. Proof by contrapositive
4. Proof by cases
5. Proof of biconditionals
6. Manipulating Quantifiers
7. Very basic set theory
8. Very basic number theory (an introduction to Peano's Axioms)
9. Finally, proof by induction

Each worked example is followed by exercises with hints and full solutions.

The first proof presented is about as simple as it gets: Prove $P \land Q \implies Q \land P$ (i.e. if propositions $P$ and $Q$ are true, then propositions $Q$ and $P$ are true). Baby steps compared to proof by induction.

Answer 15

I have another explanation for why it is so difficult to get right.

I don't know how it is in other countries, but usually students (here in Germany) learn it the wrong way, either at school already or in Bachelor studies.

Here is how that happens:

Some teacher or even assistant of a professor takes an example and then says something like: "Whatever we add to this, we always end up with another thing that satisfies what we need it to satisfy. Then we can do the same with the resulting thing and so on. So it's true for all of them." This initially sounds very logical and since you're learning something new, you might not spot the mistake they all make at that point.

It's only been in one lecture in my Master studies (which was mostly about graph theory), that a professor (a mathematician and physicist) explained in detail what's wrong with such a proof. It's lacking something. It's lacking the additional proof you'd have to bring for the example you start out with. You'd have to prove, that this example can stand for all others you could possibly pick and that proof can be very had to do. He recommended us to always use a "destructive" way of doing it, which is to say: "I can any example, take it apart in any way I want, and then all the parts satisfy the conditions and whatever we add to those, it still satisfies what needs to be satisfied."

Since it's been a while, I don't fully remember the procedure anymore, but I think it's exactly what user21820 described as reducing. To go the other way around always requires more proving and is way more difficult to get correct than this way of reducing.

Because this is so often taught in a wrong way, with examples, where going the wrong way around works, students think they know how to do it, but then it is simply wrong. Then they'll get confused, when you tell them how it's actually done.

Also there are simply so many steps with several names for each of them (at least in German), that it is difficult to keep their order and and names and what to do in them in memory for a long time. In Computer Science, you'll learn this method of proving something at some point, but never really use it on a day to day basis as you use programming languages and frameworks. This is why everytime you repeat learning it in some lecture, it is like something new, that needs to be understood first. I once understood it, when that professor explained it in detail and also explained why the other way, which everyone learned so far was wrong, but now I also don't know how to do this kind of proof anymore. It's been two semesters since I understood it ... To be honest, if I had the choice of asking a mathematician, I'd always go for that, instead of trying to do that myself and making mistakes. That's what mathematicians are for. Let them do what they're good at, which should be proving stuff and let computer scientists do the computer stuff.

As you can see from my probably quite imprecise way of describing things, I am not a mathematician myself ;)

Answer 16

Because for us students it seems that there is no structure for it. We get the impression that there is a lot of assumption that one might do in order to prove by induction and there is no formula for it. Every question is different and brings in a new factor or a new way of creating the base case, or splitting the equation to be proved, or inserting a random number at the end that makes the equation still valid, etc. There is always something that we haven't seen in previous proofs that makes it really challenging for us to just come up with this new "trick" for every new thing we try to prove. And it is frustrating. There seems to be no method to learn it. We see other people doing it and think it is a natural talent that we don't have and no matter how much we practice we will never learn. When I see someone doing a proof by induction, during the the process I am often like: "Where did you get that from?!?!". And the answer is always like "Oh, that is simple, you just do this, this, and that... tadah!!" And what the person does is always something I have never seen before. Always. How did he come up with that?!! So, yeah, that is why I struggle with induction.

Answer 17

I will add my own rough theory here. Since American students are not trained in basic logic, I think the critical fact is that they have no familiarity or understanding about implication statements $P \Rightarrow Q$. In many cases they'll be learning about the form of an implication statement, as well as induction, all at the same time, and they can't distinguish between the two issues.

If there was more teaching of basic logic, and completely separate exercises on proving implication statements alone, then I would expect the difficulty of induction to be at least somewhat reduced.

Answer 18

In my experience, the most difficult part of mathematical induction is understanding where to focus my attention when creating proofs.

In the two courses I've taken that teach mathematical induction, the professor has begun with an analogy, and then moved on to perform a series of examples. It was fairly easy to understand the math involved with the examples, and analogies such as dominoes made enough intuitive sense that I believed in the principle. But when i was left to create my own proofs on homework, I found it very difficult. It just never seemed clear what the next step was. I became doubtful that I understood the concept at all, and wasn't sure how to get better. After working through many problems with examples, however, I started to see patterns and developed a mental catalog of common strategies. I think I would have benefited more from explanations on the processes used for developing inductive proofs.

Answer 19

I found this post as a student trying to figure out why induction proofs are so difficult to understand. There are good answers here, but I think many are not specific enough to why induction proofs (rather than proofs in general) are so challenging.

The metaphor and principle of induction is straightforward. For me, the real issues arise in following along with what's happening in an actual induction proof, and being able to replicate it myself.

1: Most of the proofs involve "algebraic cleverness." Every induction proof I've seen so far involves some unusual algebra trick that I have never had a reason to use outside of the context of induction. Examples: removing an element from a factorial, or adding/subtracting some element so that something else can be substituted in. From the perspective of someone who has only used algebra in a conventional, solution-oriented way, this is difficult to wrap my head around. As a result, as I'm trying to read or watch an induction proof, most of my time is spent just figuring out why the algebraic manipulations make sense, and convincing myself that they are correct.

2: The notation. Up to this point in my proofs course, we have generally dealt with notation that is easy to distinguish in terms of "what it is." As an example, it's very clear that the notations $p/q$ for rational numbers, $2k$ for even numbers, etc. are integers, and generally these are the same letters that are always used. But because induction proofs often deal with sums, products, and factorials, suddenly we're dealing with $i$'s, $k$'s, $n$'s, $n + 1$'s, and $m$'s, depending on the statement. This is frustrating because the inconsistent notation from problem to problem distracts from the logic and makes the student expend energy just keeping track of what represents what.

Two things I think would help are: First, giving some preceding exercises that will help students improve their skills at being clever with algebra. Many of the "tricks" used in induction proofs probably feel mundane to an experienced professor, but to a student, they are utterly flabbergasting the first time you see them. Second: Be very explicit about what each piece of notation is. Write it on the board during the first few problems, so that students are not trying to keep track in their head while also following along with the problem.

I also agree that it's hard to see the motivation behind a proof by induction. All but the most number theory-oriented students will probably not care that the sum of some amount of numbers is equal to some algebraic expression. If time permits, providing some examples of where this is actually useful (like in applied math or statistics) may help struggling students replace their frustration with curiosity.

Answer 20

I'll not touch the problem of convincing your students that induction actually proves anything, but just some practical problems.

Usually you start: A (0) is true, A (n) implies A (n+1) for all n ≥ 0, => A (n) is true for all n ≥ 0.

Often the induction step doesn't work for n = 0 or n = 2 or other small n. Student must learn that instead they can prove A (n) is true for n = 0, n = 1, ..., n = k. A (n) implies A (n+1) for all n ≥ k.

Often the induction step doesn't work at all. Student must learn that often you can find a stronger statement B (n) which implies A (n) and which can be proved by induction.

Often a step n->n+1 doesn't work. Student must learn that they can instead prove: If A (k) is true for all k ≤ n then A (n+1) is true.

Also good to learn is another principle: If A (n) is not true for all n ≥ 0 then there is a smallest such n. Assume that there is a smallest n where A (n) is false and prove that there is an even smaller one. Which is of course complete equivalent to induction.

Answer 21

I think a lot of the issue is the algebraic complexity. Having to write a lot, carry a lot of relationships, etc. It's just more work. Note, humans are far from computers in our ability to carry a lot of relations at one time. And many students are not as used to being drilled and working on writing a lot of expressions. We even routinely see "questions" (more like arguments) to have everyone use a CAS versus doing manipulations.

Add onto that, the limited utility (at least early) of the technique.

P.s. I'm a little wondering why you talk about teaching it in calculus. It is normally a part of the algebra 2 course. Arguable one of the harder, less pleasant parts of it.