Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|improve this question
9  
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
1  
This is quite nice IMO. –  Ragib Zaman May 15 '12 at 2:27
5  
@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
add comment

17 Answers

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

share|improve this answer
    
Oooh, I like that one! –  Cameron Buie May 14 '12 at 21:16
3  
@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
2  
@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
4  
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
2  
@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
show 6 more comments

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.
L-tromino L-tromino, blue

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!

n=2

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.

share|improve this answer
1  
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
add comment

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.

share|improve this answer
    
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
1  
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
add comment
  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.

share|improve this answer
add comment

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

The Simple Idea Behind Mathematical Induction

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

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

share|improve this answer
    
I love this; it makes an old thing look elegent and more beautiful than it was before. –  000 May 18 '12 at 1:16
add comment

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

share|improve this answer
add comment

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.

share|improve this answer
    
Brian, is this "secondary-school level"? –  Pedro Tamaroff May 14 '12 at 20:50
1  
@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
add comment

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

share|improve this answer
add comment

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

share|improve this answer
add comment

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.

share|improve this answer
add comment

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.

share|improve this answer
10  
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
2  
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
1  
@MarkDominus: Actually, as non-examples of induction go, my favourite is one that you wrote about. :-) –  ShreevatsaR May 15 '12 at 11:44
show 1 more comment

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

share|improve this answer
5  
Append "&t=3m9s" to get: this –  The Chaz 2.0 May 14 '12 at 20:39
add comment
  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)$.
share|improve this answer
add comment

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.

share|improve this answer
add comment

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.

share|improve this answer
add comment

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.

share|improve this answer
add comment

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.

share|improve this answer
11  
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
3  
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
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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