Excellent uses of induction and recursion - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-25T13:45:13Z http://mathoverflow.net/feeds/question/92696 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/92696/excellent-uses-of-induction-and-recursion Excellent uses of induction and recursion Lorenzo Lami 2012-03-30T16:49:59Z 2012-04-03T11:41:40Z <p>Can you make an example of a <strong><em>great</em></strong> proof by induction or construction by recursion?</p> <p>Given that you already have your own idea of what "great" means, here it can also be taken to mean that the chosen technique :</p> <ul> <li>is vital to the argument;</li> <li>sheds new light on the result itself;</li> <li>yields an elegant way to fulfill the task;</li> <li>conveys a powerful and simple view of an intricate matter;</li> <li>is just the only natural way to deal with the problem.</li> </ul> <p>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...</p> <p>Elementary examples are especially appreciated, but non-elementary ones are welcome too!</p> http://mathoverflow.net/questions/92696/excellent-uses-of-induction-and-recursion/92698#92698 Answer by Uday for Excellent uses of induction and recursion Uday 2012-03-30T17:01:48Z 2012-04-01T12:48:39Z <p>1)Proof of Euler's formula, V-E+F=2, with induction on F (number of faces). </p> <p>2)Backward induction proof of generalized AM-GM inequality. </p> <p>3)Proof of Heine-Borel theorem using <strike>Transfinite</strike> Topological induction.</p> http://mathoverflow.net/questions/92696/excellent-uses-of-induction-and-recursion/92701#92701 Answer by Edgar A. Bering IV for Excellent uses of induction and recursion Edgar A. Bering IV 2012-03-30T17:44:34Z 2012-03-30T17:44:34Z <p>A problem I enjoyed in my undergraduate algorithms course is as follows:</p> <p>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.</p> <p>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.</p> <p>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. </p> <p>The problem is originally from Knuth Vol. 1, and stack sorting is further elaborated on in <a href="http://www.combinatorics.org/Volume_9/PDF/v9i2a1.pdf" rel="nofollow">this survey</a>.</p> http://mathoverflow.net/questions/92696/excellent-uses-of-induction-and-recursion/92709#92709 Answer by Kevin Beanland for Excellent uses of induction and recursion Kevin Beanland 2012-03-30T20:52:37Z 2012-04-01T16:13:10Z <p>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$. </p> <p>For $n \in \mathbb{N}$ the norm $\|x\|_{n+1}$ norm is defined by </p> <p>$\|x\|_{n+1}= \sup{\frac{1}{2} \sum^k_i \|E_ix\|_{n} }$</p> <p>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 &lt; \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</p> <p>$\|x\|_T= \max ( \|x\|_0 , \sup \frac{1}{2} \sum^k_i \|E_ix\|_T ).$</p> <p>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). </p> <p>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): <a href="http://gowers.wordpress.com/2009/02/17/must-an-explicitly-defined-banach-space-contain-c_0-or-ell_p/" rel="nofollow">http://gowers.wordpress.com/2009/02/17/must-an-explicitly-defined-banach-space-contain-c_0-or-ell_p/</a></p> <p>Check out Boris Tsirelson's website for more info on his space: <a href="http://www.math.tau.ac.il/~tsirel/Research/myspace/main.html" rel="nofollow">http://www.math.tau.ac.il/~tsirel/Research/myspace/main.html</a></p> http://mathoverflow.net/questions/92696/excellent-uses-of-induction-and-recursion/92714#92714 Answer by Asher M. Kach for Excellent uses of induction and recursion Asher M. Kach 2012-03-30T21:38:13Z 2012-03-30T21:38:13Z <p>A Classic: <strong>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.</strong></p> <p>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.</p> http://mathoverflow.net/questions/92696/excellent-uses-of-induction-and-recursion/92716#92716 Answer by Jon Bannon for Excellent uses of induction and recursion Jon Bannon 2012-03-30T21:42:13Z 2012-03-30T22:15:25Z <p>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:</p> <p>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:</p> <p><a href="http://mathoverflow.net/questions/48184/a-synopsis-of-adyans-solution-to-the-general-burnside-problem" rel="nofollow">http://mathoverflow.net/questions/48184/a-synopsis-of-adyans-solution-to-the-general-burnside-problem</a></p> <p>Certainly the simultaneous induction technique is an important idea in constructing such monster groups.</p> http://mathoverflow.net/questions/92696/excellent-uses-of-induction-and-recursion/92738#92738 Answer by Johan Wästlund for Excellent uses of induction and recursion Johan Wästlund 2012-03-31T07:59:22Z 2012-03-31T07:59:22Z <p>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.</p> http://mathoverflow.net/questions/92696/excellent-uses-of-induction-and-recursion/92809#92809 Answer by Harry for Excellent uses of induction and recursion Harry 2012-04-01T13:29:30Z 2012-04-01T13:29:30Z <p>In pro-algebraic geometry you get to see some nice arguments by induction. For example, M. Kim proves that the continuous cohomology <code>$$H^1(G_{\mathbf{Q}_p},\pi_{1,et}^{uni}(X))$$</code> 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.</p> <p>For a reference, see page 639 in <a href="http://www.ucl.ac.uk/~ucahmki/siegelinv.pdf" rel="nofollow">http://www.ucl.ac.uk/~ucahmki/siegelinv.pdf</a> </p> http://mathoverflow.net/questions/92696/excellent-uses-of-induction-and-recursion/92821#92821 Answer by Dan Piponi for Excellent uses of induction and recursion Dan Piponi 2012-04-01T16:30:26Z 2012-04-01T18:15:28Z <p>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.</p> http://mathoverflow.net/questions/92696/excellent-uses-of-induction-and-recursion/92831#92831 Answer by Steven Gubkin for Excellent uses of induction and recursion Steven Gubkin 2012-04-01T18:33:27Z 2012-04-01T18:33:27Z <p>The following famous puzzle is a great example:</p> <p><a href="http://terrytao.wordpress.com/2008/02/05/the-blue-eyed-islanders-puzzle/" rel="nofollow">http://terrytao.wordpress.com/2008/02/05/the-blue-eyed-islanders-puzzle/</a></p> http://mathoverflow.net/questions/92696/excellent-uses-of-induction-and-recursion/92862#92862 Answer by Frank Thorne for Excellent uses of induction and recursion Frank Thorne 2012-04-02T01:55:41Z 2012-04-02T01:55:41Z <p>The $n$-level Tower of Hanoi can be solved in $2^n - 1$ moves. </p> <p>Not only does induction prove this, it actually shows you the solution!</p> http://mathoverflow.net/questions/92696/excellent-uses-of-induction-and-recursion/92971#92971 Answer by none for Excellent uses of induction and recursion none 2012-04-03T07:18:21Z 2012-04-03T10:39:14Z <p><a href="http://en.wikipedia.org/wiki/Goodstein%27s_theorem" rel="nofollow">Goodstein's theorem</a> 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.</p> http://mathoverflow.net/questions/92696/excellent-uses-of-induction-and-recursion/92985#92985 Answer by Lorenzo Lami for Excellent uses of induction and recursion Lorenzo Lami 2012-04-03T10:27:56Z 2012-04-03T11:41:40Z <p>The "Ercules and the Hydra" problem, as found in "L. Kirby and J. Paris. Accessible independence results for peano arithmetic. <em>London Mathematical Society</em>, 4:285 293, 1982.".</p> <p>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.</p>