Examples of "exotic" induction 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!
 A: Goodstein's Theorem 
http://en.wikipedia.org/wiki/Goodstein%27s_theorem 
is proved using an induction of length $\epsilon_0$.
A: The Ackermann function is well-defined.  
This is easily proved by lexicographic induction on $\mathbb N\times \mathbb N$. But perhaps not easily formulated -- I can only think of this awkward formulation: For every $x,y$ there is a unique function on the initial segment determined by $(x,y)$ satisfying the Ackermann recursion.
A: The following example is not completely elementary, in that it requires the notion of sum of a family of non-negative real numbers (defined as supremum of the finite sub-sums), and some topology of the real line. But it allows a nice picture, and leads to a visualization of ordinal numbers as subsets of $\mathbb{R}$, so that it could be understood and appreciated by well-motivated high-school students, if you take the time to explain the problem, possibly skipping the technicality, and solving particular cases first. Moreover, it is close to the birth-place of the ordinal numbers. 
The additivity of the length on the family of all left-closed, right-open intervals  of the real line.
Let $P$ be the family of all left-closed, right-open intervals of the real line. Suppose $I=:[a,b)\in P$ is partitioned into a family elements $J_x:=[x,x')$ of $P$, that we may indicize by the left end-point $x\in S$, that is,   $I=\cup_{x\in S} J_x $. Then,
$$|I|=\sum_{x\in S} |J_x|\, .$$ 
Proof: You  may first consider and solve the case of finitely many intervals, and the case of a sequence of intervals accumulating at $b$, that gives rise to a telescopic sum. For the general case, the key point is  that $S$ is well-ordered by the natural order of $\mathbb{R}$. This allows to prove
$$\Big|\bigcup_{x\in S\atop x \le u} J_x \Big|= \sum_{x\in S\atop x \le u} |J_x|  \, .$$
by transfinite induction on $u\in S$.
A: You may find some nice examples at https://math.stackexchange.com/questions/145189/examples-of-mathematical-induction
