# Tag Info

66

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: Many students don't know what proof is. Many students don't realise it's actually about statements. Many students don't ...

34

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

29

The problem with induction proofs is that too often the problem is given by "Prove that..." After a few examples and explanations of induction, if the students know elementary calculus, the following sequence might prove interesting: Find the first ten derivatives of $x\cdot e^x$. What seems to be the formula for the $n$th derivative of $x\cdot e^x$?...

28

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

26

Two more examples. Proving that a $2^n \times 2^n$ chessboard with a single square missing can be covered using L-shaped (made out of three squares) pieces. Proving that a convex $n$-gon can be divided into $n-2$ triangles.

25

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

22

Historical remark. Though it has already been mentioned in an answer, I can't resist posting a bit more about the following wonderful example of a proof by induction. I quote directly from the original printing of Polyominoes (1965) by Solomon Golomb: T R O M I N O E S It is impossible to cover an $8 \times 8$ board entirely with trominoes, polyominoes of $... 21 Proving DeMorgan's Laws for$n$sets. I like this example because it requires the$n=2$case in the induction step. It's common to have students prove that$\sum_{k=1}^n k^3 = \left(\sum_{k=1}^n k\right)^2$. A great follow up is to assume you have a sequence$\langle a_k\rangle$that satisfies$\sum_{k=1}^n a_k^3 = \left(\sum_{k=1}^n a_k\right)^2$and ... 20 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 ... 19 I suspect that the issue is not so much the ellipsis per se but a problem with notation in general, and in particular with the correct use of the equals sign. At the risk of repeating what I wrote in this answer, students often regard the equals sign not as a symbol meaning "these two expressions are the same" but rather as a symbol separating a ... 18 One example that I recently came across was to prove that the function $$f(x)=\begin{cases} e^{-1/x},&x>0\\ 0,&x\leq0 \end{cases}$$ is smooth (i.e.$f\in\mathcal{C}^\infty$). Here is a link to a proof online. 18 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, ... 16 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 ... 16 I like having students show that the Euler characteristic ($\chi=V-E+F$, where$V$,$E$, and$F$are the number of vertices, edges, and faces, including the exterior face, of the graph) of a planar graph is always 2. Planar graphs are easy to define for those who have not seen them before, and the proof is a (relatively) straightforward induction on the ... 14 Prove that the Tower of Hanoi puzzle can be solved for any number of disks. Indeed, that it can be solved in$2^n - 1$moves for$n$disks. 14 I indeed think$\sum_{k = 1}^n k = \frac{n(n + 1)}2$is not a good first example as writing the sum forwards and backwards is more clever and natural for a newcomer. But proving “the sum of the$n$first odd numbers is$n^2$”, while really close to the equality above, is a better example, because the induction part of the proof is really simple:$\sum_{k = ...

13

Encourage your students to actually read the problem to themselves, similar to how they would if they were reading a book. Starting from left to right, read the problem: "Zero squared plus one squared plus two squared plus dot dot dot plus n squared equals..." etc. I find that this not only reinforces that there is that "..." there and it needs to be ...

13

"A well-chosen example illustrates ... and is entirely convincing." For me, all of what is usually called "generic proof" satisfy your criterion. Consider the Euclidean algorithm for finding the greatest common divisor of two numbers. A well-chosen example tells your students all they need including why the algorithm gives the greatest common divisor, how ...

12

Induction receives far too much attention as a proof technique. But, if you are to give it attention, it is probably worth-while going through the equivalence of the principle of induction and the well-ordering of the naturals. In fact, when I teach induction I proceed as follows: Suppose an inductive property does not hold for all naturals. Look at the set ...

11

Base problem Some positive integers are written on the board. At each step one of the integers $n$ is erased and replaced with any number of positive integers that are all less than $n$. Of course, if the erased integer is $1$ then no new positive integers can be written on the board. Prove that no matter how this procedure is carried out the board must ...

11

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

10

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

10

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

9

Here is another one: $\color{blue}{\text{Prove that the power of$13$can be writen as a sum of two squares}}.$ I will give two proofs of it. First one is more involved and includes following fact: $$(a^2+b^2)(x^2+y^2)= (ax+by)^2+(bx-ay)^2$$ yet second one takes step 2 and it is much more elegant. 1.st proof Base: $n=1$, then $13 = 2^2+3^2$ and we are ...

9

I suggest the following counter-example. (Added in edit: I agree with kcrisman comment that this may be misleading to beginners, and should probably be kept for people that master induction relatively well and start being lazy verifying the base case). Theorem. In a (finite) color pencils box, all pencils must have the same color. Proof. We proceed ...

9

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

9

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

8

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

8

Disclaimer: It's not simple, but it might be useful. The context in which it happend is algorithms, but it would be great if someone could test if this approach is useful during other courses, e.g. when introducing induction. Reason why I'm writing about this here is, that when I did the exercise described below, my students (not all, but a lot) had this "...

8

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

Only top voted, non community-wiki answers of a minimum length are eligible