# Examples of mathematical induction

What are the best examples of mathematical induction available at the secondary-school level---totally elementary---that do not involve expressions of the form $\bullet+\cdots\cdots\cdots+\bullet$ where the number of terms depends on $n$ and you're doing induction on $n$?

Postscript three years later: I see that I phrased this last part in a somewhat clunky way. I'll leave it there but rephrase it here:

--- that are not instances of induction on the number of terms in a sum?

-
I suffered greatly the first time I saw induction, because it was also my first serious exposure to $\sum$ notation, and the two pills were too much to swallow at once. – MJD May 14 '12 at 20:34
Good question! The "sum" examples are of necessity all of the collapsing sum kind. So although induction is needed in principle, they are not persuasive. – André Nicolas May 14 '12 at 22:44
This is quite nice IMO. – Ragib Zaman May 15 '12 at 2:27
@Ragib, The Blue Eyed Islanders problem is a horrible example of induction because it is very confusingly about knowledge as being separate from truth, which is a huge distraction. – Old Pro May 15 '12 at 19:20
@OldPro Yet it gives an example of how subtle mathematical inductions can be. And it's just plain fun. – k.stm Nov 12 '12 at 15:07

My favorite induction problem goes like this:

Consider a long circular road that has a number of fuel depots along the way. All in all, the depots contains just the right amount of fuel to get your car around. You start with an empty tank. Show that you can always find a depot at which to start so that it's possible to get all the way round. (You can make the road one-way if you like.)

-
Oooh, I like that one! – Cameron Buie May 14 '12 at 21:16
@OldPro. Mathematical cars tend to have infinite fuel tanks, just as mathematical cows are spherical. On a more serious note: while I wouldn't use this as my first (or second) example when teaching induction, in my opinion the beauty of the problem is that it looks nothing like the standard examples. As such it helps illustrating the real power of induction. If all you do is use induction for strange sums, many students will believe that that is the sole purpose of induction. – mrf May 15 '12 at 4:49
@OldPro: I don’t know what you mean by scale to infinity; this is clearly an argument by induction on the number of depots, which can be as large as one likes. – Brian M. Scott May 15 '12 at 4:51
This also has a simple non-inductive proof: plot the amount of fuel starting at any depot, and pick the lowest point. – Yuval Filmus May 15 '12 at 5:00
@OldPro: Induction proofs are just proofs by contradiction where you prove that the smallest counterexample doesn't exist. – JeffE May 15 '12 at 18:38

Here is the first example I saw of induction, and I still think it's a beautiful one.

Problem: Prove that a $2^n \times 2^n$ sheet of graph paper with one box removed, can be tiled with L-shaped trominos.

Proof: For the $n=1$ case, there is nothing to prove: a $2 \times 2$ grid with one box removed is exactly a L-tromino.

For $n=2$, consider the $4 \times 4$ grid. You can divide it into four $2\times 2$ grids. The removed box is in one of those four sub-grids, so that sub-grid can be covered with an L-tromino (is an L-tromino, rather). What about the other 3 sub-grids? Put an L-tromino right in the center of the huge grid, which covers them!

Now the remaining part of each of them is a $2\times2$ grid with one box removed. I leave it to you to complete the proof, and teach it to the students as you best see fit.

The figures above are from Mathematical Circles: Russian Experience by Dmitri Fomin, Sergey Genkin, and Ilia Itenberg, specifically the chapter on Induction which is written by I.S. Rubanov. The book actually doesn't use a variable $n$, but asks for a $16\times 16$ square, then in the form of a discussion between a teacher and a student works through the $2\times 2$ and $4\times 4$ and $8\times 8$ cases, until it is obvious that we have in fact proved a theorem for any $2^n \times 2^n$ ('It looks like we have a "wave of proofs running along the chain of theorems $2\times2 \longrightarrow 4\times4 \longrightarrow 8\times8 \longrightarrow$ It is quite evident that the wave will not miss any statement in this chain.')

As an aside, this is a lovely book with quite a bit of non-trivial mathematics suitable for elementary school and high-school students (though I read in late high school).

This theorem and proof are also on the cut-the-knot website: Tromino Puzzle and Golomb's Inductive Proof.

-
This is one of the first ones I saw, and it seemed a lot more elegant than all the 'nasty-looking sum = complicated expression I pulled out of a hat' ones. It was the example that convinced me that induction was a powerful technique for discovering new results, not just an overly-complicated way of proving things we already know. – James May 15 '12 at 11:35

Some I can think of off the top of my head:

1. Number of moves to solve the Towers of Hanoi puzzle.

2. Factorization into primes (uses strong induction, though).

3. Also using strong induction, the winning strategy for a simplified game of nim described at the bottom of this answer.

4. Formula for combinations, using $\binom{n+1}{k} = \binom{n}{k}+\binom{n}{k-1}$.

I'll add more later if I think of any.

-
Every one of these was before university for me. I think that learning technique and becoming familiar with ideas is hugely important Very impressed that these are all spot on. – Mark Bennet May 14 '12 at 20:49
I like Towers of Hanoi because it easily translates into visual and tactile learning, which can help a lot of kids who otherwise have trouble with abstract math concepts. – Old Pro May 15 '12 at 2:13
The one for winning nim is good because it makes induction practical. By understanding it, you can actually win a game. – dspyz May 15 '12 at 21:20

I'd use a visual method to explain the concept before "complicating" it with numbers. Falling dominoes seem intuitive and capture the essence of induction.

To visualize it, think of the statements as dominoes, lined up in a row. Imagine you can prove the ﬁrst statement S1, and symbolize this as domino S1 being knocked down. Additionally, imagine that you can prove that any statement Sk being true (falling) forces the next statement Sk+1 to be true (to fall). Then S1 falls, and knocks down S2. Next S2 falls and knocks down S3, then S3 knocks down S4, and so on. The inescapable conclusion is that all the statements are knocked down (proved true).

(Source: p143 of Book of Proof by Richard Hammack)

(You could also go off on a tangent about abstraction in mathematics analogies.)

-
I love this; it makes an old thing look elegent and more beautiful than it was before. – 000 May 18 '12 at 1:16
@jabolotai : What do you do about the commonplace empirical observation that this does not work: students who see just this explanation fail to understand it? I was puzzled by this at one time. I suspect now that it had never before occurred to those students that in mathematics one should learn to understand why something must be true rather than simply learning to execute algorithms that come from textbooks and instructors. Then they come to this topic and it's the only time they've thought about how to prove something, and they don't know what "prove something" means. ${}\qquad{}$ – Michael Hardy Jan 25 '15 at 18:48
@MichaelHardy Give the kids real dominoes. If that fails give them a real text book. If I have to explain the rest step by step, you might not understand it :) Seriously, perhaps teach "proof" by another means first then do induction. Knowing when to use an algorithm is still a good start towards truly grokking something. – jabolotai Jan 26 '15 at 0:57
@jabolotai : To think that giving them real dominoes would help is silly. Everyone among them already has a perfect understanding of how real dominoes work. To teach "proof" from scratch would help, but the big obstacle is that students treat learning the subject as a price paid to get a grade rather than as the thing they showed up for, and that makes everything hopeless. – Michael Hardy Jan 26 '15 at 5:07
@MichaelHardy It's not hopeless; Some students passion lies elsewhere so even with a perfect inductive teaching method they still wouldn't intrinsically get or appreciate it. Occasionally though you might inspire someone. Real dominoes and the algorithmic explanation was my attempt at a joke. Ha. Although, a good physical analogy can be a powerful visualising tool - e.g. domino computer youtube.com/watch?v=OpLU__bhu2w People learn in a variety of styles, so perhaps mix up the delivery method a bit if they still don't get it. – jabolotai Jan 27 '15 at 14:34
1. All sorts of stuff about the Fibonacci numbers.

a. Many, many identities such as $F_n^2 = F_{2n}\pm1$.

b. The number of domino tilings of a $2\times n$ rectangle.

c. The closed-form formula for Fibonacci numbers in terms of $\frac12(1+\sqrt5)$.

2. Analogously, all sorts of stuff about recursively-defined anything.

a. For example, let $a_0 = 2$, and $a_{i+1} = 3a_i +2$; show that $a_i = 3^i-1$. It's easy to make up such identities.

b. As Brian Scott suggested, stuff about binary trees. Lots of combinatorial identities: How many full binary trees are there of order $n$? How many paths from the upper right corner of an $n\times n$ checkerboard to the lower left? How many ways to lace a sneaker with $n$ pairs of holes?

c. High school students love higher dimensional geometry. Count the number of vertices, edges, etc. in an $n$-cube.

d. There is an infinite family of solutions to $|a^2 - 2b^2| = 1$, because $(1,0)$ is a solution, and if $(a_i, b_i)$ is a solution, then so is $(a_i + 2b_i , a_i + b_i)$.

e. Or you can present the preceding in terms of "Let's find rational approximations to $\sqrt 2$". Make a table of $n^2$ and another table of $2n^2$. Find entries in the left table that are close to entries in the right table. This gives approximations $\frac11, \frac32, \frac75, \frac{17}{12}, \frac{41}{29}\ldots$. Guess that the next term is $a_i+2b_i\over a_i+b_i$ and prove by induction that with this definition, $(a_n,b_n)$ satisfies the equation and that $a_n\over b_n$ is close to $\sqrt2$.

f. Consecutive elements $\frac ab, \frac cd$ of the Farey series always satisfy $bc-ad = 1$. Other stuff related to the Stern-Brocot tree.

3. Let $a_i = \langle 4, 484, 48484, \ldots\rangle$ and $b_i = \langle 8, 848, 84848, \ldots\rangle$.

a. Show that for each $i$, $4b_i - 7a_i = 4$

b. Let $c_i$ be the concatenation of $a_i$ and $b_i$, so for example $c_2 = 484848$. Then $c_i = b_i^2 - a_i^2$.

-

Does proving statements like $f(n) \leq g(n)$ fit your bill? For instance, prove that $2^n \leq 2n!$.

-

These come to mind immediately; I may have more later.

1. The number of vertices in a tree is one more than the number of edges.

2. If $n>0$, exactly half of the subsets of $\{1,\dots,n\}$ have even cardinality.

3. Any of the many two implies finite arguments. For example, if $\mathscr{C}$ is a collection of sets with the property that $C_0\cap C_1\in\mathscr{C}$ whenever $C_0,C_1\in\mathscr{C}$, then $\mathscr{C}$ is closed under finite intersections.

4. The postage stamp induction: given an unlimited supply of $3$ and $5$ cent stamps, every integer amount greater than $8$ can be made. Or if you prefer: if $A$ is a set of positive integers such that $3,5\in A$ and $a+b\in A$ whenever $a,b\in A$, then $A$ contains every integer greater than $8$.

5. All sorts of simple inductions based on recursive definitions of strings of symbols. For example, $aba$ is a legal word, and if $w$ is a legal word, so are $abw,awb,wab,baw,bwa$, and $wba$; prove that every legal word contains more $a$’s than $b$’s.

-
Brian, is this "secondary-school level"? – Pedro Tamaroff May 14 '12 at 20:50
@Peter: Why not? You’d obviously have to explain tree, for instance, but the ideas are all very simple. – Brian M. Scott May 14 '12 at 20:51
I'm just asking. I don't know what is taught in secondary schools these days. – Pedro Tamaroff May 14 '12 at 20:59
Item 2 has a nice non-inductive proof: Pair off the even-sized sets with the odd-sized ones by the rule "If a set contains 1 delete the 1; if it doesn't contain 1, adjoin 1." – Andreas Blass Jan 21 '13 at 23:11
@Andrew: I know. I’m quite fond of that proof. But it also has a perfectly good inductive proof. – Brian M. Scott Jan 21 '13 at 23:13

I like the ones that involve division.

For instance, prove that $7 \mid 11^n-4^n$ for $n=1, 2, 3, \cdots$

Another example would be perhaps proving that

$$(3+\sqrt{5})^n+(3-\sqrt{5})^n$$

is an even integer for all natural numbers $n$.

-

I think we did things we already knew to start with, like the formula for triangular numbers, then squares. The binomial coefficients provided examples too. Actually this developed into expressions for the coefficients of power series and generating functions.

There is some magic in discovering such things for yourself rather than being told. My maths teacher pointed me in the right direction and let me discover ...

-

How about that a graph always has an even number of vertices of odd degree, by induction on the number of edges? But perhaps the counting argument is simpler.

Along the same lines: Euler's $F-E+V=2$ formula for graphs. Chromatic polynomials.

-

Sometimes no-examples teach a good deal. Check the following proof that all human beings on Earth right now are the same age:

Proof for 1: clearly, in a set with only 1 person all the people in it are the same age

Inductive hypothesis: in all the sets with n persons we have that all of them are the same age.

Let A be a set with $n+1$ persons, say $A=\{a_1,...,a_n,a_{n+1}\}$, and let $A':=\{a_1,...,a_n\}$ , $A'':=\{a_2,...,a_{n+1}\}$ . The ind. hyp. tells us that all the persons in A' are the same age and all the persons in A'' are the same age, and since $a_2$ belongs to both then all the elements in A are the same age as $a_2$ , ergo: all of the elements in A are the same age. QED.

-
I've seen this done, and it was a really bad idea. The students were not completely convinced of induction to begin with, and to see a demonstration that it seemingly proved a nonsensical result ruined their trust in the method. – MJD May 15 '12 at 0:09
I think the explanation of the flaw above is pretty simple and well within the reach of H.S. students studying this mathematics' level. Also, I'd teach it after studying thoroughly the basics and after giving some examples of its use. – DonAntonio May 15 '12 at 1:50
All I said was that I had seen it done and it worked very badly. Perhaps you can make it work better. – MJD May 15 '12 at 1:52
I’m with @Mark on this. Some variant of this argument appears as an example or an exercise in a number of introductory discrete math texts, and in my experience the students who get the point of it are a proper (and often rather small) subset of those who have managed to develop some genuine understanding of induction. – Brian M. Scott May 15 '12 at 3:58
@MarkDominus: Actually, as non-examples of induction go, my favourite is one that you wrote about. :-) – ShreevatsaR May 15 '12 at 11:44

Check this http://www.youtube.com/watch?v=oU60TuGHxe0&t=3m9s. Mathematical induction explained on simple properties of strings.

-
Append "&t=3m9s" to get: this – The Chaz 2.0 May 14 '12 at 20:39
1. The sum of the measures of the interior angles in a convex $n$-gon is $180^\circ(n-2)$.
2. $n$ coplanar lines in general position divide the plane into $\frac{1}{2}n(n+1)+1$ regions
3. The maximal number of regions obtained by joining $n$ points around a circle by straight lines is $\frac{1}{24}(n^4-6n^3+23n^2-18n+24)$.
-

The number of diagonals in a convex polygon is $n(n-3)/2$.

Proof

For $n=3$, the result follows.

Suppose true for $n$ and look at $n+1$. By joining vertex $1$ with vertex $3$, we obtain a polygon with $n$ sides. The inductive hypothesis means we have $n(n-3)/2$. diagonals, plus the one we just drew. We only need to add the missing diagonals from $2$ to all other vertices $\neq 1,3$, which accounts to $n-2$ more diagonals. Thus we get $$\frac{n(n-3)}2+n-2+1=\frac{n(n-3)+2(n-1)}{2}=\frac{n^2-n-2}{2}=\frac{(n-2)(n+1)}2$$

and the result follows.

-

At the risk of beating a dead horse, any good book on competition mathematics is sure to have lots of examples at the level you want. Here's one from Putnam and Beyond by Gelca and Andreescu, which demonstrates how recursive definitions can be used to do induction:

Prove that any function $f : \mathbb{R} \rightarrow \mathbb{R}$ can be written as a sum of two functions, each of which is a shift of an odd function (i.e. there exists some $g,h : \mathbb{R} \rightarrow \mathbb{R}$ and $a,b \in \mathbb{R}$ such that $g(x-a)$ and $h(x-b)$ are odd functions and $f = g+h$)

The proof is by constructing $g$ and $h$ on increasing subintervals of $\mathbb{R}$, with $a=0$ and $b=1$. Let $g(x)=x f(1)$ on $[-1,1]$, and $h(x)=f(x)-g(x)$ on the same interval. For $n \ge 1$ let $h(x)= -h(2-x)$ on $(2n-1,2n+1)$ and $g(x)=f(x)-h(x)$ on the same interval. Then let $g(x)=-g(-x)$ on $[-2n-1,-2n+1)$ and $h(x)=f(x)-g(x)$ on the same interval.

To prove that $g$ and $h$ defined this way satisfy the required properties uses induction. Specifically, assume at each stage, we have $g$ and $h$ defined on $[-2n-1,2n+1]$ with $f=g+h$, $g$ odd, and $h(x)=-h(2-x)$ for $x \in [-2n-3,2n+1]$. It follows directly from the definitions of $g$ and $h$ that $f=g+h$ on $[-2(n+1)-1,2(n+1)+1]$ and that $g$ remains odd and $h(x)=-h(2-x)$ for $x \in [-2(n+1)-3,2n+1]$. Since these intervals cover $\mathbb{R}$ we have $g$ and $h$ defined everywhere with the desired properties.

Admittedly, this is a bit harder than what most secondary students would be able to solve, but it is still totally elementary and with some watering down and drawing pictures they could at least understand it.

-

Suppose that in a group of $2n + 1$ people, for every group of $n$ people there exists one person (which is not one of them) who knows each of them. Here the relation "knows" is symmetric.

Then, there exists one person who knows all the other $2n$ people.

-

Why not some properties of powers of (natural) numbers: $$\forall\,a,b,m,n\in\mathbb{N}\setminus\{0\},\quad a^m\cdot a^n=a^{m+n},\quad (a^m)^n=a^{mn},\quad a^n\cdot b^n=(ab)^n.$$

Another one, which is not totally elementary as you meant it but I think may be very formative in secondary school level is the following:

If $p$ is a polynomial in variable $x$, its degree is $\deg(p)=n\ge 1$, its coefficients $a_0,\ldots,a_n\in\mathbb{R}$, then for all $x_0\in\mathbb{R}$, exist $b_0,\ldots,b_n\in\mathbb{R}$ such that $$p(x)=\sum^n_{k=0}b_k(x-x_0)^k,\quad\forall\,x\in\mathbb{R}.$$

This can be shown very quickly also without induction and has a nice meaning in the $x,y$ plane drawn on the blackboard.

-

Ramsey's theorem

For any given number of colors c, and any given integers n1, . . . ,nc, there is a number, R(n1, ..., nc), such that if the edges of a complete graph of order R(n1, . . . , nc) are colored with c different colors, then for some i between 1 and c, it must contain a complete subgraph of order ni whose edges are all color i.

The two color case should be introduced first, of course. If the children get a good feel for this case, then they can attempt to understand the proof for this special case and then later move on to understand the general theorem and the proof of that.

-

Maybe it would be good to start with something that the students already know is obviously true. For example, you could develop an inductive proof that $2n$ is always even.

I think this would make it easy for them to see what the base case, inductive hypothesis and inductive steps mean.

For the base case we show our statements holds for the smallest possible $n$. In this case it is $0$ and $2(0)=0$, which is even.

For the inductive step we have to show that $2(n+1)$ is even but we get to use the inductive hypothesis: $2n$ is even. Then it's just a matter of the distributive property to get $2n+2$ and the common knowledge that adding $2$ to an even number gets another even number.

Other candidates could be anything shown with straightforward structural induction on Peano numbers.

-
In my experience this has exactly the opposite effect: when the result is obvious, many students fail to see the point of proving it in the first place. This example, however, is bad for a more fundamental reason: that $m$ is even if it can be written in the form $2n$ for some integer $m$ is generally taken to be a definition and hence not subject to proof. – Brian M. Scott May 15 '12 at 3:55
By definition, an even number is $2$ times an integer. So it's hard to see what you could have in mind when you speak of an inductive proof of something that is the very definition of the concept involved. – Michael Hardy May 15 '12 at 17:10