Next week I am going to teach two lessons on induction to very motivated students from high schools. At some point I would like to talk about ordered sets, well-ordered sets, and mention the fact that induction works on well-ordered sets. More precisely, I will prove the following formulation of induction: let $S$ be a well-ordered set with minimal element $0$, and let $P$ be a property such that $P(0)$ is true and if $P(x)$ is true for every $x < y$, then $P(y)$ is true. Then $P(x)$ is true for every $x\in S$.

I would like to provide a (sufficiently elementary) application of this principle in a case when $S$ is not (isomorphic to) the set of natural numbers. For example, one could try to find an example for $S=\mathbb{N}\times \mathbb{N}$, endowed with the lexicographical order. I am looking for examples such that:

the problem is sufficiently "natural" and elementary (the audience is from high school!)

possibly, it should not reduce to an induction "in one variable" (for example, the induction on $(m,n)\in\mathbb{N} \times\mathbb{N}$ should not reduce to an induction on $n+m\in\mathbb{N}$)

Of course any induction on $\mathbb{N}\times\mathbb{N}$ may be reduced to a double induction on $\mathbb{N}$, but in order to avoid this I should look for too complicated well-ordered sets, so this does not bother me too much... Anyway, if anyone knows some reasonably simple examples with more complicated well-ordered sets, then this would be very good for me!

4more comments