# 'Low-algebra' examples of induction

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.

• It's not clear what is meant by "series formulae". Sep 13 '18 at 16:12
• In a perverse way, the algebra rich nature of series induction can be a feature. Students need to build those muscles. Probably they need overall manipulative skill more than they need the method of induction. Sep 13 '18 at 16:22
• 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.
– TT_
Sep 13 '18 at 21:35
• @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. :) Sep 14 '18 at 1:45
• 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.
– Ovi
Sep 14 '18 at 7:27

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.

• How can you "prove" that if the students don't have a logic class? ;) Sep 13 '18 at 18:34
• 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. Sep 13 '18 at 19:08
• 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! Sep 14 '18 at 1:42

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

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?

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

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.

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

• 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. Sep 18 '18 at 12:45