8
$\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$
8
  • $\begingroup$ It's not clear what is meant by "series formulae". $\endgroup$ – Bill Dubuque Sep 13 '18 at 16:12
  • $\begingroup$ 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. $\endgroup$ – guest Sep 13 '18 at 16:22
  • 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_ Sep 13 '18 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 Sep 14 '18 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 Sep 14 '18 at 7:27
8
$\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 Sep 13 '18 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 Sep 13 '18 at 19:08
  • 1
    $\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 Sep 14 '18 at 1:42
4
$\begingroup$

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

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$
3
$\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$
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 Sep 18 '18 at 12:45

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.