# Examples of multiple induction

It is easy to find/construct cases that can be proven by nested induction, i.e., some variation of the theme to prove the statement $P(m, n)$ you prove $P(1, n)$ by induction as a base case for $m$, and given $P(m,n)$ you prove $P(m + 1, n)$.

I'm interested in cases in which it is natural/simpler to define some order between pairs $(m, n)$ and the induction proof is along this order, not two nested inductions as outlined above.

• Have you got any example in mind? – Amir Asghari Apr 20 '16 at 20:20
• In a sense a lot of research works like this - define a complexity and show you can always reduce it. What aspect about education are you interested in? – Jessica B Apr 20 '16 at 21:15
• The most basic non-trivial example: the termination of the recursive definition of the Ackermann function. – dtldarek Apr 25 '16 at 8:15
• @dtldarek why don't you make that an answer? In general, this is a question of mine: why do people post potential answers as comments? – cheyne May 9 '19 at 14:00