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.

  • $\begingroup$ Have you got any example in mind? $\endgroup$ – Amir Asghari Apr 20 '16 at 20:20
  • $\begingroup$ 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? $\endgroup$ – Jessica B Apr 20 '16 at 21:15
  • 1
    $\begingroup$ The most basic non-trivial example: the termination of the recursive definition of the Ackermann function. $\endgroup$ – dtldarek Apr 25 '16 at 8:15
  • 1
    $\begingroup$ @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? $\endgroup$ – cheyne May 9 '19 at 14:00

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.