Excellent uses of induction and recursion - MathOverflow

Excellent uses of induction and recursion

2012-03-30T16:49:59Z

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!

Answer by Uday for Excellent uses of induction and recursion

2012-03-30T17:01:48Z

1)Proof of Euler's formula, V-E+F=2, with induction on F (number of faces).

2)Backward induction proof of generalized AM-GM inequality.

3)Proof of Heine-Borel theorem using ~~Transfinite~~ Topological induction.

Answer by Edgar A. Bering IV for Excellent uses of induction and recursion

2012-03-30T17:44:34Z

A problem I enjoyed in my undergraduate algorithms course is as follows:

Suppose you have a computing machine with the following architecture. There are $k$ stacks (for some $k$), input can be pushed onto the first stack, output is popped off of the last, and intermediate operations pop from one stack and push to the next in a line. The top of the stack may also be inspected and compared. Given a permutation of ${1,\ldots,n}$ in order as input, how many stacks $k$ do you require to sort the permutation? Describe an algorithm that achieves this bound.

One can prove the bound ($\log_2 n$) by induction, and then just state that this gives a natural recursive algorithm. The same technique was useful for a couple of other problems in a similar vein.

I think this certainly fits the bill of an elegant way to fulfill the task (prove a bound and give an achieving algorithm) in a nice class of cases.

The problem is originally from Knuth Vol. 1, and stack sorting is further elaborated on in this survey.

Answer by Kevin Beanland for Excellent uses of induction and recursion

2012-03-30T20:52:37Z

Tsirelson's space (1974) is a good example from Banach space theory. His space is the completion of a $c_{00}$ (all finitely supported scalar sequences) under an inductively defined norm. The base norm is the sup-norm $\|\cdot \|_0$.

For $n \in \mathbb{N}$ the norm $\|x\|_{n+1}$ norm is defined by

$ \|x\|_{n+1}= \sup{\frac{1}{2} \sum^k_i \|E_ix\|_{n} } $

where the supremum is taken over all sets $(E_i)_{i=1}^k$, where $E_i$ is a finite interval in $\mathbb{N}$, $\max E_i < \min E_{i+1}$ and $k \leq E_1$ (here $Ex$ denotes the restriction of $x$ to the coordinates of $E$). The Tsirelson norm is $\|x\|_T = \sup_n \|x\|_n$ and satisfies the following implicit equation

$ \|x\|_T= \max ( \|x\|_0 , \sup \frac{1}{2} \sum^k_i \|E_ix\|_T ).$

The space $T$ does not contain a copy of any $\ell_p$ or $c_0$. This solved a major open problem at the time (I should point out that Tsirelson actually defined the dual of $T$ which also has the property).

The, inductive, method he devised for producing this space eventually lead to the solutions of numerous problems in Banach space theory (way to numerous to mention). Moreover, the `necessity' of the inductive construction to produce spaces not containing any $\ell_p$ of $c_0$ is a problem that has been considered by Gowers as a polymath project (unfortunately not much progress here): http://gowers.wordpress.com/2009/02/17/must-an-explicitly-defined-banach-space-contain-c_0-or-ell_p/

Check out Boris Tsirelson's website for more info on his space: http://www.math.tau.ac.il/~tsirel/Research/myspace/main.html

Answer by Asher M. Kach for Excellent uses of induction and recursion

2012-03-30T21:38:13Z

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.

Answer by Jon Bannon for Excellent uses of induction and recursion

2012-03-30T21:42:13Z

Simultaneous induction as used in combinatorial group theory, for example in the proof of the Adyan-Novikov theorem providing the counterexample to the General Burnside Problem:

Some nice references about the nuts and bolts of this were supplied by Mark Sapir in an answer to one of my questions about this proof:

http://mathoverflow.net/questions/48184/a-synopsis-of-adyans-solution-to-the-general-burnside-problem

Certainly the simultaneous induction technique is an important idea in constructing such monster groups.

Answer by Johan Wästlund for Excellent uses of induction and recursion

2012-03-31T07:59:22Z

The original proof of Van der Waerden's theorem on monochromatic arithmetic progressions comes to mind. Well, the more recent ones too by the way.

Answer by Harry for Excellent uses of induction and recursion

2012-04-01T13:29:30Z

In pro-algebraic geometry you get to see some nice arguments by induction. For example, M. Kim proves that the continuous cohomology $$H^1(G_{\mathbf{Q}_p},\pi_{1,et}^{uni}(X))$$ is representable by induction on the terms in the lower central series of the $\mathbf{Q}_p$ pro-unipotent algebraic group associated to the etale fundamental group of a curve $X$. Not very surprising, but still crucial for the argument.

For a reference, see page 639 in http://www.ucl.ac.uk/~ucahmki/siegelinv.pdf

Answer by Dan Piponi for Excellent uses of induction and recursion

2012-04-01T16:30:26Z

Let $P(p)$ = "there is no natural $q$ such that $(p/q)^2=2$". A simple induction argument shows that P holds for all naturals $p$ and hence that $\sqrt 2$ is irrational. All descent arguments are basically induction.

Answer by Steven Gubkin for Excellent uses of induction and recursion

2012-04-01T18:33:27Z

The following famous puzzle is a great example:

http://terrytao.wordpress.com/2008/02/05/the-blue-eyed-islanders-puzzle/

Answer by Frank Thorne for Excellent uses of induction and recursion

2012-04-02T01:55:41Z

The $n$-level Tower of Hanoi can be solved in $2^n - 1$ moves.

Not only does induction prove this, it actually shows you the solution!

Answer by none for Excellent uses of induction and recursion

2012-04-03T07:18:21Z

Goodstein's theorem hasn't yet been mentioned. A straightforward-looking arithmetic theorem with a surprise proof using transfinite induction. Also (the main interesting characteristic of the theorem), there is NO proof from ordinary first-order Peano arithmetic. It's actually equivalent to the formalized $\Sigma^0_1$-soundness (aka 1-consistency) of PA.

Answer by Lorenzo Lami for Excellent uses of induction and recursion

2012-04-03T10:27:56Z

The "Ercules and the Hydra" problem, as found in "L. Kirby and J. Paris. Accessible independence results for peano arithmetic. London Mathematical Society, 4:285 293, 1982.".

Using transfinite induction, it is possible to show that Hercules will always kill the hydra (with a finite number of blows) regardless of the strategy chosen to chop off hydra's heads. Moreover, this fact is not provable within Peano Arithmetic.