31
$\begingroup$

Many examples of induction are silly, in that there are more natural methods available. Could you please post examples of induction, where it is required, and which are simple enough as examples in a course on proofs (or which includes proofs, e.g. a first course on discrete mathematics)?

$\endgroup$
  • $\begingroup$ There is discussion on this at Mathematics Stack Exchange: math.stackexchange.com/questions/423513/… $\endgroup$ – Mike Jones Aug 24 '14 at 14:59
  • 1
    $\begingroup$ I want to challenge the premise here just a little - not because I don't agree with it, but because it implies that induction isn't "needed" for e.g. the famous sum of the first $n$ positive integers. Okay, it isn't - but how exactly do you show that the "reverse 'em and divide by two" method works for all n? Any time we use "dot dot dot" or "and so on" we need to be careful; even if we're not actually using Well-Ordering implicitly then it is still worth pointing out when "dot dot dot" can lead to trouble. We are careful about this with series, we should be with "non-induction" as well. $\endgroup$ – kcrisman Mar 8 '16 at 15:31

17 Answers 17

20
$\begingroup$

Two more examples.

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

  2. Proving that a convex $n$-gon can be divided into $n-2$ triangles.

$\endgroup$
  • 2
    $\begingroup$ 1. I think this is a great example; so I posted a bit about its history in this same thread. 2. Perhaps you want to say a convex $n$-gon? The statement is true as is, but I'm not sure whether the more general proof qualifies as simple... $\endgroup$ – Benjamin Dickman Apr 3 '14 at 1:54
  • 2
    $\begingroup$ True on 2, thanks! $\endgroup$ – Santiago Canez May 20 '14 at 23:11
20
$\begingroup$

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:

  1. Find the first ten derivatives of $x\cdot e^x$.
  2. What seems to be the formula for the $n$th derivative of $x\cdot e^x$?
  3. Prove that your formula is right by induction.
  4. Find and prove a formula for the $n$th derivative of $x^2\cdot e^x$. When looking for the formula, organize your answers in a way that will help you; you may want to drop the $e^x$ and look at the coefficients of $x^2$ together and do the same for $x$ and the constant term.

I'd have the students work this out in class and in teams of two and their work was corrected and counted as a homework. Of course, the use of a CAS helped getting rid of the messy part of finding derivatives. Not all students found this interesting. But those who did started to learn what it was to do (elementary) research.

$\endgroup$
17
$\begingroup$
  • 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 prove, by induction on $n$, that necessarily $a_k=k$ for all $k$.
  • Proving the Well-Ordering Principle of $\mathbb{N}$ by induction on whether the set in question has $n$ as an element. I designed a scaffolded version of this as a homework exercise, and it also has the students think about why induction on the size of the set in question does not prove the claim!
  • Have not personally used this, but perhaps Cauchy's "backward induction" proof of the AGM inequality is of interest.
$\endgroup$
  • 4
    $\begingroup$ or $a_k=0$ for all $k$... $\endgroup$ – Matthew Towers Jan 21 '16 at 11:18
17
$\begingroup$

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.

$\endgroup$
17
$\begingroup$

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 $3$ squares, because $64$ is not divisible by $3$. Instead, it shall be asked: Can the $8 \times 8$ board be covered with $21$ trominoes and $1$ monomino (a single square)? (p. 20).

In this particular problem, Golomb is talking about trominoes that look like extended dominoes. He demonstrates that this is only possible when the monomino is placed in one of four different squares, and then begins his discussion of L-shaped trominoes:

When another type of tromino is considered, the result is surprisingly different: No matter where on the checkerboard a monomino is placed, the remaining squares always can be covered with $21$ right trominoes [i.e., L-shaped trominoes] (p. 21).

He then proceeds to prove this for the $8 \times 8$ board, but also for the $2^n \times 2^n$ board, remarking:

The proof just given proceeds by mathematical induction... (p. 22).

As a spoiler, here is a proof:

enter image description here

The pasted image above comes from a nice article based on earlier work by Norton Starr:

Soifer, A. (2010). Norton Starr’s 3-Dimensional Tromino Tiling. Geometric Etudes in Combinatorial Mathematics, 221-225. Springer New York.

You can find further information about this problem on Starr's site here. In particular, you can find a list of related references as well as a gamefied version of the problem that can be played online (or purchased as an actual puzzle - a nice gift!).

Though the latter tromino problem is solved using induction, the former one is also quite nice. The first to formulate that problem was, apparently, prolific problem poser Murray S. Klamkin:

...back in $1948$ ... I had begun to submit a rather large number of problem proposals to the American Mathematical Monthly. ...Since probably at that that time, in retrospect, most of my proposals were not particularly good, they just got filed away. Unfortunately for me, this included one favorite one. This was to determine whether or not one could remove one square from a chess board and cover the deleted board with $21$ $3 \times 1$ trominoes. This was no loss to problem solvers, since several years later, Solomon Golomb's book on polyominoes came out which included this problem plus many more goodies (p. 73).

This remark comes from (N.B. Good luck tracking down part one of this article...):

Klamkin, M. S. (1994). Mathematical Creativity in Problem Solving and Problem Proposing II. In Eves' circles, (34), 73-95.

Sorry if the tangent here seems unrelated; problem histories can be surprisingly tough to figure out, so I thought it might be nice to include a bit of the back-story online.

$\endgroup$
  • 2
    $\begingroup$ Thank, will see if I can track those down... $\endgroup$ – vonbrand Apr 3 '14 at 1:51
  • 1
    $\begingroup$ @vonbrand If you are talking about tracking down part one of the Klamkin piece (which I would be most interested in seeing...) I believe the citation is: Crux Mathematicorum 11 (1985), 115, 218. $\endgroup$ – Benjamin Dickman Apr 3 '14 at 1:57
11
$\begingroup$

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 of counter-examples, and pick the smallest one. Arrive at a contradiction and conclude the property did hold for all naturals. I find that this approach is very natural (pun not intended). The equivalent formalism of prove case $k=1$, then prove $P(k)\implies P(k+1)$ is something I only introduce later. For the life of me I don't understand why this formalism is the standard one and not the "look at all counter-example....".

It is probably also a good idea to talk about the status of the principle of induction. It is not a theorem but rather a proof principle. It is ok not to accept it (though most mathematicians do). It is important to understand that what we accept by proof by induction is that a single recipe for proofs (i.e., for each $k$ we have a recipe for how to concoct a proof for $P(k)$) is accepted as a single proof for an infinitude of statement (i.e., all the $P(k)$ for all natural $k$). It is a good idea to talk about this in relation to the demand that proofs are finite. It is also a good idea to explain this in the context of the axiom of choice.

It is indeed quite hard to find good examples of proof by induction (which is part of the reason why I claimed that induction receives far too much attention). Other than the classical (more or less silly) exercises, some that actually do require induction include: the generalized associativity rule and other generalized algebraic rules but also proving properties of recursively defined sequences (e.g., monotonicity, boundedness etc.).

$\endgroup$
  • 5
    $\begingroup$ Upvote for "induction receives far too much attention as a proof technique". $\endgroup$ – Jim Belk Mar 16 '14 at 2:13
  • 7
    $\begingroup$ That being said, I think the reason to focus on the $P(k) \Rightarrow P(k+1)$ technique over the "minimal counterexample" technique is that $P(k) \Rightarrow P(k+1)$ is more like a direct proof, while "minimal counterexample" is essentially a proof by contradiction. $\endgroup$ – Jim Belk Mar 16 '14 at 2:20
  • 1
    $\begingroup$ What is wrong with proof by contradiction? $\endgroup$ – Ittay Weiss Mar 16 '14 at 2:30
  • 9
    $\begingroup$ They're a little bit harder to understand and follow, because everything that you prove during a proof by contradiction is false. A direct proof occurs in the "real world" of true statements, while a proof by contradiction occurs in an absurd world that you construct solely for the purpose of pointing out its absurdity. Since we all live in the real world, direct proofs tend to make more sense to the reader. In addition, proofs by contradiction usually convey less insight than direct proofs, since none of the intermediate results that were proved are actually true. $\endgroup$ – Jim Belk Mar 16 '14 at 2:35
  • 7
    $\begingroup$ I must disagree on most accounts @JimBelk. People often engage in proof by contradiction in real life. E.g., "I did not eat that chocolate bar" claims little brother. Well, let's suppose you are telling the truth, then your face would not be smeared with chocolate. Hence you are lying! I do agree that at times a proof by contradiction may seem more obscure than a direct proof, but sometimes the opposite is true. What makes a proof easier to follow is not its mode (contrapositive, direct, by contradiction) but the flow of the arguments. $\endgroup$ – Ittay Weiss Mar 16 '14 at 2:42
10
$\begingroup$

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 = 1}^{n + 1} 2k + 1 = \left(\sum_{k = 1}^n 2k + 1\right) + 2n + 1 = n^2 + 2n + 1 = (n + 1)^2$.

Proof by induction is more necessary and useful in a computer science scenario, where some objects are defined in an inductive way: “a complete binary tree of height $n$ has $2^n - 1$ nodes”: straightforward for $n = 1$; for $n \geqslant 2$, its left and right child are binary trees of height $n - 1$, so it has $2(2^{n - 1} - 1) + 1 = 2^n - 1$ nodes.

Another example where a special method of inductive reasoning called infinite descent is useful: “show that $\sqrt2$ is irrational”. Let us assume there exist two natural numbers $p, q$ such that $\sqrt2 = p/q$. Then $2q^2 = p^2$, so $p$ is even, thus there exists some natural number $p'$ such that $p = 2p'$, therefore $2q^2 = 4p'^2$ gives $q^2 = 2p'^2$ so $q$ is even as well, i.e. $q = 2q'$ holds for some natural number $q'$. We then get $2q'^2 = p'^2$, so $(p', q') = (p / 2, q / 2)$ is a strictly lesser representation of $\sqrt2$. As there is no infinite decreasing sequence of natural numbers, this leads to a contradiction, so $\sqrt2$ is irrational.

$\endgroup$
  • $\begingroup$ Infinite descent can easily be made into a proof by contradiction: Assume $n$ is the smallest natural such that ...; the descent step gives a smaller one; contradiction. $\endgroup$ – vonbrand Mar 16 '14 at 23:30
  • 2
    $\begingroup$ Why is the first example bad but the second one good? "Writing the sum forwards and backwards" for $1, 3, \ldots, 2n-1$ also gives $n$ pairings adding up to $2n$; then the total is $n(2n)/2 = n^2$. $\endgroup$ – Benjamin Dickman Mar 30 '14 at 4:23
  • $\begingroup$ I like the proof of the sum of the geometric series better than the arithmetic series, precisely because the arithmetic series have alternative, simple proofs. $\endgroup$ – vonbrand Apr 4 '14 at 14:19
  • $\begingroup$ Sorry @BenjaminDickman, it was stupid :D $\endgroup$ – Jill-Jênn Vie May 24 '14 at 16:30
9
$\begingroup$

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 number of edges in a graph.

Further, after giving the definition of a planar graph, there is ample opportunity for students to explore and come up with a conjecture on their own (assuming you have the time for this). This seems a much more natural way to show how induction is used by mathematicians, rather than just stating "Prove that...".

Another benefit is giving a concrete example of a topological invariant, likely the first seen by your students. Finally, it's not too difficult to motivate why non-math majors should care about graphs. There are dozens and dozens of applications (e.g. neural networks). It is likely that whatever the major of the student, there is some problems in that field for which graphs are useful tools.

$\endgroup$
  • $\begingroup$ I'm doing this in my evening class tonight! $\endgroup$ – Santiago Canez May 20 '14 at 23:11
  • $\begingroup$ Best example I've seen so far :) $\endgroup$ – Ruben May 21 '14 at 0:40
  • $\begingroup$ Graph theory is a great place to explore for statements easy to conjecture and which "need" induction in some sense to prove. $\endgroup$ – kcrisman Mar 8 '16 at 15:34
9
$\begingroup$

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 eventually become empty.

This problem is just the right difficulty and can ensure that students really understand what induction is.

General problem

Prove that the following game always terminates regardless of the initial configuration and the choices (of node, subtree and number of copies) throughout the game.

(1) Start with any finite tree rooted at $r$

(2) At each step:

  (2.1) Select any node $x$ and a child node $y$ of $x$

  (2.2) Remove the subtree rooted at $y$ (and of course the edge $(x,y)$ as well)

  (2.3) If $x$ is not $r$, attach finitely many copies of the subtree rooted at $x$ to its parent node

For example, the following diagram shows one step, where the chosen subtree to be removed is shown in red and the subtree that would be copied is shown in green.

The base problem is equivalent to the special case of this general problem where the initial tree has depth at most $2$. This generalization is a harder problem that is an extension of the Hydra Game. A hint is to define a total ordering on trees:

For any finite trees $S,T$:

  $S \le T$ iff:

    Either:

      $S$ is a leaf node

    Or:

      $S,T$ are both not leaf nodes

      The subtrees of $S$ when ordered forms a lexicographically smaller sequence than that of $T$

Then one must show that at each step the whole tree decreases according to the ordering, and also that any decreasing sequence of trees must terminate. That last part is the hardest. Basically, induct on the tree depth first, which then allows inducting on the biggest subtree, and then induct on the number of copies of the biggest subtree.

Note that this proof shows that with the right definitions and inductions it is quite intuitive, and there is no need to introduce ordinals.

$\endgroup$
7
$\begingroup$

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 "being enlightened" face expression, and as it was not about the algorithm itself, then it had to be about the other thing and in that case it was induction (i.e. it seemed that they grasped something important about induction).

Exercise:

The task was on dynamic programming and was given as follows:

A company plans to organize a party. The hierarchy of employees is a rooted tree (not necessarily binary), and each employee can be characterized by a form of sociability, given by a positive number. Write a program that will pick the guests so that:

  • no guest would meet their immediate superior at the party,
  • the sum of sociability coefficients is maximal,
  • the company founder (the root of the tree) has to be at the party.

The program should output a single number, namely the sum of sociability coefficients of the guests.

The algorithm to calculate it is easy, let the symbol $\mathcal{T}$ denote the set of abstract people with their hierarchies

\begin{align*} \newcommand{soc}{\mathtt{sociability}} \newcommand{sub}{\mathtt{subordinates}} \newcommand{with}{\mathtt{with}} \newcommand{without}{\mathtt{without}} \soc &: \mathcal{T} \to \mathbb{R}^+\\ \sub &: \mathcal{T} \to 2^\mathcal{T} \\ \end{align*} then in mathematical notation it would be \begin{align*} \with(t)&= \soc(t) + \sum_{s\ \in\ \sub(t)} \without(s), \\ \without(t) &= \sum_{s\ \in\ \sub(t)} \max\big\{ \with(s), \without(s) \big\}. \end{align*}

where the result will be given by $\with$ as the founder has to be included. Now, the challenge is to prove that it is optimal (i.e. it returns the correct result). The proof is via induction on the structure of the tree, that is, we start from leaves and then go up to the root, with the assumption that each time when make the step in some node, all its subtrees are already done.

The base step is easy, as for each leaf we have $\sub(l) = \varnothing$ so \begin{align}\with(l) &= \soc(l) \\ \without(l) &= 0 \end{align} what is obviously true.

Now, for the induction step, $\with(t)$ requires all the subtrees to skip their roots, and besides that they are all independent, so we can just take the sociability of $t$ and add all the optimal subsolutions (we can use them because of the induction hypothesis) and that is exactly what the formula is doing. As for $\without(t)$ the $t$ itself isn't a guest, so from each subtree we can pick the best option and sum it all together. This works, but only because we know that the subsolutions were calculated correctly from induction hypothesis, the shape of the tree ensures, that there weren't any circular arguments.

Sometimes students benefit from an alternative proof: take an optimal solution and prove that one returned by the algorithm isn't worse. Again, prove it via induction on the structure of the tree, the hypothesis being that our algorithm returns an optimal subsolution for each node of the tree. Base case is easy, because there is no choice available in the leaves. For the inner nodes we show that our algorithm returns a pick of guests at least as good as the optimal solution (in $\with$ it follows from induction hypothesis and the fact that all the numbers are positive, for $\without$ it follows from properties of $\max$ function).

Some commentary:

Each time I did this it was an introductory course in programming, and for many the first time where they would see a non-linear induction (in fact this can be proved with induction on the height of the tree, but I did complicate it on purpose). Drawing a diagram with arrows, describing how the induction progresses and how it relies on the subtrees being already calculated helps a lot. After this exercise the topic would come back again several times and students would have much easier time proving that some algorithm (e.g. the Ackermann function) terminates.

Of course, it is hard to draw any reliable conclusions from this experience (it might be just a coincidence that it worked for me), so it would be great if someone could test it themselves. I'd also love to hear your opinions and suggestions.

I hope this helps $\ddot\smile$

$\endgroup$
7
$\begingroup$

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 by induction on the number of pencils. If the box has one pencil, then obviously all its pencils have the same color. Now, assume that in all boxes of $n$ pencils, the pencils are all of the same color and let $X$ be a box with $n+1$ pencils. Order the pencils arbitrarily and consider the $n$ first pencils: by the induction hypothesis, they all have the same color, call it $c$. Consider now the $n$ last pencils: by the induction hypothesis, they all have the same color, call it $c'$. Since the $n-1$ central pencils have color $c$ and $c'$, we have $c=c'$ so that all $n+1$ pencils have the same color.

The goal here is to stress that if one fails to properly identify and test the base case, then things can go dead wrong.

$\endgroup$
  • $\begingroup$ The problem in this "proof" is really in the step $n = 1$ to $n = 2$. An example of missing/faulty base case(s) would also be nice. $\endgroup$ – vonbrand Apr 4 '14 at 14:10
  • 2
    $\begingroup$ This example is in some sense a problem of base case: given the induction step only works from $n=2$, then $n=2$ should be the base case, not $n=1$. The point is to show that the two steps have to work together. $\endgroup$ – Benoît Kloeckner Apr 5 '14 at 8:11
  • $\begingroup$ See also en.wikipedia.org/wiki/All_horses_are_the_same_color $\endgroup$ – András Bátkai Apr 22 '14 at 21:51
  • 1
    $\begingroup$ I saw a "proof" that $n > n + 10$ that illustrates the "missing base" very nicely. Details are left as an exercise :-) $\endgroup$ – vonbrand Apr 25 '14 at 0:37
  • 1
    $\begingroup$ I usually do this one as "everyone has the same color eyes" - but have found it is not helpful until they really "get" induction; it is confusing when students are first introduced, unless they've had significant previous proof exposure. $\endgroup$ – kcrisman Mar 8 '16 at 15:22
6
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Nice, as that incorporates recursion in the solution. $\endgroup$ – vonbrand May 26 '14 at 13:08
5
$\begingroup$

Three connected induction proofs:

(1) For a really easy one: Every tree of $n$ arcs has $n+1$ nodes. ($0$ arcs $\implies$ $1$ node. Remove a leaf node and its incident arc; induct.)

(2) A bit more difficult: Every polygon triangulation can be $3$-colored. Assume every polygon has a triangulation. See below. Argue that the dual graph is a tree. Remove a leaf node by clipping off an "ear tip." $3$-color the remainder and return the ear triangle, coloring its tip different from its two neighbors.


      3-coloring


(3) Every polygon has a triangulation. Prove there exists an interior diagonal. Induct on the two halves. Proved, e.g., in Discrete and Computational Geometry, p.4.

$\endgroup$
  • $\begingroup$ (2) is wrong as it stands. Suppose that the polygon is a triangle, and its triangulation is $K_4$. Perhaps the theorem is intended to apply to a graph only if it is planar and it is a cycle and some chords of that cycle? That is, a polygon triangulation without extra vertices? $\endgroup$ – Rosie F Jul 23 '16 at 18:37
  • $\begingroup$ @RosieF: In this case a triangulation is a maximal set of noncrossing interior diagonals connecting pairs of vertices. $\endgroup$ – Joseph O'Rourke Jul 24 '16 at 12:10
4
$\begingroup$

Computational geometry is a good source for basic induction proofs where non-inductive methods are either impossible or hard to conceive.

Also graph theory. Someone already mentioned Euler's Formula which is great. It's also simple to prove that every connected simple graph can be 6-colored using induction. (You can assume in such a graph that there exists a vertex whose degree is less than or equal to 5 -- or prove it separately.)

For a CS-oriented audience, proofs of correctness for recursive algorithms are a great way to motivate induction -- especially because induction and recursion go hand in hand. Here's a nice video proof from Udacity on the correctness of the Russian peasant's algorithm for integer multiplication: https://www.youtube.com/watch?v=GGBEiIuheTY

$\endgroup$
3
$\begingroup$

Prove that the greedy algorithm for the change-making problem with Fibonacci denominations produces an optimal solution (uses the minimum number of coins possible).

This problem is not as easy as it looks. Note that there may be more than one optimal solution. It would also be instructive to try and minimize the number of times the induction axiom is used. (But no, I won't suggest that one should also try to prove this minimum. =P)

$\endgroup$
2
$\begingroup$

Every natural number is odd or even.

$\endgroup$
  • 9
    $\begingroup$ Could you expand on this and explain how a student would prove this by induction? As written so succinctly, this is much better suited as a comment. $\endgroup$ – Brendan W. Sullivan Apr 22 '14 at 17:40
  • $\begingroup$ It's hard to evaluate the appropriateness of this without understanding what definitions and axioms are assumed. If odd numbers are defined as those that aren't even, then this is trivial. Would this be proved from the Peano axioms...? $\endgroup$ – Ben Crowell Jan 8 at 23:27
1
$\begingroup$

Although building up to it might be beyond the time available in many courses introducing induction, an interesting elementary example that seems unbelievable but is very easy to verify in any given case is Pick's Theorem.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.