10
$\begingroup$

What are good examples of proofs by induction that are relatively low on algebra? Examples might include simple results about graphs.

My aim is to help students get a sense of the logical form of an induction proof (in particular proving a statement of the form 'if $P(k)$ then $P(k+1)$'), independent of the way one might show that in a proof about series formulae specifically.

Improve this question
$\endgroup$
9
  • $\begingroup$ It's not clear what is meant by "series formulae". $\endgroup$
    – Bill Dubuque
    Commented Sep 13, 2018 at 16:12
  • 1
    $\begingroup$ Does not answer your question but still related: it's interesting to discuss with students wrong usage of induction (like proving that all intersecting lines intersect in the same point). Counterexamples are very useful for understanding. $\endgroup$
    – TT_ stands with Russia
    Commented Sep 13, 2018 at 21:35
  • 1
    $\begingroup$ @TT_, agreed; the false inductive proof of "in a group of n horses, all of them are the same color" is a great one. (That's also in the "Induction" section of MIT OCW's Mathematics for Computer Science.) It's even better in the videoed lecture than in the reading material. :) $\endgroup$
    – Wildcard
    Commented Sep 14, 2018 at 1:45
  • 1
    $\begingroup$ Honestly, the moment I really understood induction well was when my number theory professor taught it more rigorously. She proved that if $A$ is a subset of $\mathbb{N}$ which satsfies 1) $1 \in A$, and 2) If $k \in A$, then $k+1 \in A$, then $A = \mathbb{N}$. This made a lot of sense and was easy to understand.Then, whenever we would do a proof by induction, we would say "Let $A$ be the subset of all $n \in \mathbb{N}$ such that $P(n)$ is true. Then the goal was clear; show that those two conditions hold, and we are concinved that $P(n)$ is true for any natural number. $\endgroup$
    – Ovi
    Commented Sep 14, 2018 at 7:27
  • 1
    $\begingroup$ Similar question on Math SE $\endgroup$
    – Maesumi
    Commented Mar 20, 2023 at 8:27

6 Answers 6

Reset to default
9
$\begingroup$

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

The induction step is easy and vivid: divide the board into four smaller $2^{n-1}$ boards. By induction we can tile the board with the missing (pink) square, and we can tile the other three omitting their (purple) corner squares (in the center of the big square), leaving 3 central squares that form an "L", which we tile with one final tromino.

enter image description here

Improve this answer
$\endgroup$
3
  • $\begingroup$ How can you "prove" that if the students don't have a logic class? ;) $\endgroup$
    – guest
    Commented Sep 13, 2018 at 18:34
  • $\begingroup$ Presumably you're joking about the prior question on that topic. But that's a different question(er). Btw, ncr's answer wasn't there when I loaded the page, but since it doesn't mention the "strengthening" part I will leave this. $\endgroup$
    – Bill Dubuque
    Commented Sep 13, 2018 at 19:08
  • 2
    $\begingroup$ I first read about this one on MIT's Open Courseware site, in the induction section of Mathematics for Computer Science. Actually, that was my first introduction to induction, so I can attest to the workability of the example for teaching! $\endgroup$
    – Wildcard
    Commented Sep 14, 2018 at 1:42
6
$\begingroup$

How about: A tree with $n\ge 1$ vertices has $n-1$ edges.

Improve this answer
$\endgroup$
6
$\begingroup$

I am going to try the following activity as a first introduction to Mathematical Induction on Monday next week. I will let you know how it goes.

The implication $P(k) \implies P(k+1)$ let's you "hop around" the natural numbers, deciding the proof of new statements using your knowledge of the truth value of old statements. However, it is a bit too straightforward to see what all the fuss is about. The underwhelming and boring nature of the hopping (just put one foot in front of the other) doesn't really permit any play. Without play there can be no learning. So here, I first pose two more interesting rules for "hopping" which give interesting play opportunities (they are actually a puzzle). The final example gives the "obvious" induction rule, which should now feel truly obvious to the student. At this point we will formalize what we have learned as the principle of mathematical induction.

Alice, Bob, and Chelle are three mathematicians. As mathematicians, they have a love of certain numbers. Also, as mathematicians, their love is quite idiosyncratic.

Alice loves the natural numbers 1 and 2. Also, if she loves the natural number $k$, then she also loves the natural number $k+5$. Which natural numbers can you be certain that Alice loves? Are there any natural numbers you can be sure she does not love? Are there any natural numbers you just do not have enough information about to decide this question?

Bob loves the natural number 5. If he loves the natural number $k$, then he also loves the natural number $2k$. Also, if he loves the natural number $j$, he also loves $j-2$. Which natural numbers can you be certain that Bob loves? Are there any natural numbers you can be sure he does not love? Are there any natural numbers you just do not have enough information about to decide this question?

Chelle loves the natural number 1. If she loves the natural number $k$, then she also loves the natural number $k+1$. Which natural numbers can you be certain that Chelle loves? Are there any natural numbers you can be sure she does not love? Are there any natural numbers you just do not have enough information about to decide this question?

Improve this answer
$\endgroup$
4
$\begingroup$

A couple of simple examples come to mind:

1) Prove that there are $2^n$ subsets of an $n$-element set.

2) Prove the power rule of derivatives for non-negative integer powers using the product rule.

Improve this answer
$\endgroup$
4
$\begingroup$

I think tiling problems are good for this kind of thing. See, for example, this. There they describe how to prove the statement "if you have a $2^n\times 2^n$ chessboard with one square missing, then you can tile it with L-shaped trominoes." There are other tiling questions, as well, such as the ones here that deal with triangular chessboards and trominoes. Yet others ask students to count the number of ways to tile something (e.g., here) via linear recurrences (which usually can easily be proved inductively).

Improve this answer
$\endgroup$
2
$\begingroup$

How about the Tower of Hanoi puzzle and finding the optimal number of moves?

This link describes the recursive solution procedure and a proof of optimality using induction.

https://proofwiki.org/wiki/Tower_of_Hanoi

Improve this answer
$\endgroup$
1
  • 1
    $\begingroup$ I really like this idea as a lesson plan. Start the class out by just introducing the rules and playing a game with 3 disks. Ask them the find the fewest moves. Then after they are confident in moving three pieces around, give every group a 4th piece and ask for the fewest number of moves again. Hopefully most of them will stumble onto the fact that once they move one of the pieces out of the way, they have 'reduced' the n=4 case into the n=3 case, which they know how to handle. Then give them n=5 and n=6 to see if they can build on their knowledge of n=3 and n=4. $\endgroup$
    – ruferd
    Commented Sep 18, 2018 at 12:45

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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