# Tag Info

61

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

31

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

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

24

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

23

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.

22

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

18

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

18

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

18

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

18

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

17

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 a link to a proof online.

16

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

15

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

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

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 = ... 11 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 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 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 ... 10 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 ... 9 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 ... 9 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. 9 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 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 ... 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 There are many situations in which we have a clear collective understanding of intention, or goals, and examples which persuade us that these goals are plausible, as well as illustrating apparent causal mechanisms identifiable as "reasons" for things being the way they are. For many reasons, the contemporary style of proof-writing, especially in intensely ... 8 One thing that you have to keep in mind here, is that you don't need to understand recursion to implement it. There is a big difference between "we were taught to do it like that, I implement it and it works" and really understanding the concepts and why it works as it does. With induction, on the other hand, you are supposed to write down a complete, formal ... 8 Tiling problems might meet your constraints. A nice simple example is Golomb's Theorem that a chessboard of side$2^n\$ with any square omitted can be tiled by trominoes ("L" shapes of 3 squares). In fact we can modify it to give an example of how strengthening the induction hypothesis is often needed: simply replace "any square omitted" by "central square ...

7

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

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