[Math] Excellent uses of induction and recursion

big-listexampleslo.logicsoft-questionteaching

Can you make an example of a great proof by induction or construction by recursion?

Given that you already have your own idea of what "great" means, here it can also be taken to mean that the chosen technique :

  • is vital to the argument;
  • sheds new light on the result itself;
  • yields an elegant way to fulfill the task;
  • conveys a powerful and simple view of an intricate matter;
  • is just the only natural way to deal with the problem.

Here induction and recursion are meant in the broadest sense of the words, they can span from induction on natural numbers to well-founded recursion to transfinite induction, and so on…

Elementary examples are especially appreciated, but non-elementary ones are welcome too!

Best Answer

A Classic: Fix a positive integer $n$. Show that it is possible to tile any $2^n \times 2^n$ grid with exactly one square removed using 'L'-shaped tiles of three squares.

It serves as a wonderful introductory example to proof by induction. Indeed, the proof can almost be represented with two appropriate figures. Yet, for those just learning induction, it is a significant problem where the application of the inductive hypothesis is far from obvious.