Easier induction proofs by changing the parameter - MathOverflow most recent 30 from http://mathoverflow.net 2013-06-19T16:06:22Z http://mathoverflow.net/feeds/question/51766 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/51766/easier-induction-proofs-by-changing-the-parameter Easier induction proofs by changing the parameter Tony Huynh 2011-01-11T15:00:56Z 2011-01-11T17:28:36Z <p>When performing induction on say a graph $G=(V,E)$, one has many choices for the induction parameter (e.g. $|V|, |E|$, or $|V|+|E|$). Often, it does not matter what choice one makes because the proof is basically the same. However, I just read the following ingenious proof of König's theorem due to Rizzi.</p> <p><strong>König's theorem.</strong> For every bipartite graph $G$, the size of a maximum matching $v(G)$ is equal to the size of a minimum vertex cover $\rho(G)$.</p> <p><strong>Proof.</strong> Induction on $|V|+|E|$. Base case is clear. Now if $G$ has maximum degree 2, then $v(G)=\rho(G)$, so we may assume that $G$ has a vertex $x$ of degree at least 3. Let $y$ be a neighbour of $x$ and let $Y$ be a minimum vertex cover of $G - y$. Evidently, $Y \cup y$ is a vertex cover of $G$. But, by induction $|Y|=v(G-y)$, so we are done unless $v(G)=v(G-y)$. Thus, $G$ has a maximum matching $M$ avoiding $y$. Let $e \in E - M$ be incident to $x$ but not to $y$. By induction, </p> <p>$v(G)=|M|=v(G-e)=\rho(G-e)$. </p> <p>Let $Z$ be a vertex cover of $G-e$ of size $|M|$. Note that $y \notin Z$, since $M$ does not cover $y$. This implies $x \in Z$, since $xy \in E$. But then $Z$ also covers $e$ and hence is a vertex cover of $G$. </p> <blockquote> <p><strong>Question.</strong> What are some other instances (not necessarily in graph theory), where simply changing the induction parameter results in a nice shorter proof?</p> </blockquote> http://mathoverflow.net/questions/51766/easier-induction-proofs-by-changing-the-parameter/51770#51770 Answer by Lloyd Smith for Easier induction proofs by changing the parameter Lloyd Smith 2011-01-11T15:27:15Z 2011-01-11T15:27:15Z <p>Perhaps Ramsey's theorem, where the existence of R(n) is proved by showing the existence of R(n,m), using induction on n+m. I don't think there's a direct proof without this trick.</p> http://mathoverflow.net/questions/51766/easier-induction-proofs-by-changing-the-parameter/51772#51772 Answer by Pietro Majer for Easier induction proofs by changing the parameter Pietro Majer 2011-01-11T15:46:39Z 2011-01-11T17:10:56Z <p>Cauchy's proof by induction of the inequality between the arithmetic and geometric means (written in his 1821 <em>Cours d'Analyse</em>).</p> <p>Of course, the base of the induction, for $n=2$, immediately comes from $(\sqrt x_1-\sqrt x_2)^2\ge0$, but then, although it is actually possible to follow the natural induction steps, making the inequality $M_G\le M_A$ for $n+1$ nonnegative real numbers follow from the inequality for $n$ numbers, it appears that the other implication is much easier: actually, the inequality for $n$ numbers can be easily seen as a particular case of the inequality for $n+1$ numbers. (For $n$ numbers, just append to them their arithmetic mean as an $(n+1)$-th number, use the inequality for $n+1$ numbers, and simplify). Also, the inequality for $2n$ numbers easily follows from the inequalities resp. for $2$ and for $n$ numbers. As a consequence, we have an induction proof that follows a funny jumping path along natural numbers (if you like to see it this way; that's not exactly Cauchy's description): $(2)\Rightarrow (4)\Rightarrow (3)\Rightarrow (6)\Rightarrow (5)\Rightarrow (10)\Rightarrow (9)\Rightarrow(8) \Rightarrow(7) \Rightarrow (14)\Rightarrow \dots$</p> http://mathoverflow.net/questions/51766/easier-induction-proofs-by-changing-the-parameter/51778#51778 Answer by Andres Caicedo for Easier induction proofs by changing the parameter Andres Caicedo 2011-01-11T17:28:36Z 2011-01-11T17:28:36Z <p>Gauss' "second" (1815) proof of the fundamental theorem of algebra (Werke, Volume 3, 33-56, or see Paul Taylor's translation, currently available <a href="http://www.paultaylor.eu/misc/gauss-web" rel="nofollow">here</a>) follows an interesting pattern, similar to the one in Cauchy's proof of the AM-GM inequality mentioned in Pietro's answer. (It does more than this: It introduces the discriminant, for example.)</p> <p>Gauss shows that a polynomial with real coefficients can be factored into real polynomials of first and second degree. We have that a polynomial of odd degree has a root. From this, he argues by assigning to a polynomial $p$ of degree $n$ a new polynomial $p^+$ of degree $n(n-1)/2$, in such a way that pairs of (possibly complex) roots of $p^+$ determine (possibly complex) roots of $p$ via quadratic equations. </p> <blockquote> <p>So the pattern is induction not on the degree $n$ of the polynomial, but on the largest power of 2 dividing $n$.</p> </blockquote> <p>I first encountered this neat idea not through Gauss work, but through a proof by Derksen of the fundamental theorem of algebra via linear algebra (Harm Derksen, "The fundamental theorem of algebra and linear algebra", American Mathematical Monthly, 110 (7) (2003), 620–623.)</p> <p>The skeleton of Derksen's proof is as follows: One actually shows that:</p> <blockquote> <p>If $V$ is a complex ﬁnite dimensional vector space, and ${\mathcal F}$ is a (possibly inﬁnite) family of pairwise commuting linear operators on $V$, then the operators in ${\mathcal F}$ admit a common eigenvector. </p> </blockquote> <p>For this, one considers the statement $E(K,d,\kappa)$: If $V$ is a vector space over $K$ of ﬁnite dimension, and $d\not{\mathrel{|}}{\rm dim}(V)$, then any family ${\mathcal F}$ with $|{\mathcal F}|=\kappa$ of pairwise commuting linear maps from $V$ to itself admits a common eigenvector. </p> <p>One easily checks that the case $\kappa$ infinite follows from the finite one, and this follows by a straightforward induction, so it is enough to show $E({\mathbb C},d,1)$.</p> <p>For this, one first shows $E({\mathbb R},2,1)$: A linear map from ${\mathbb R}^n$ to itself, say, with $n$ odd, admits a real eigenvalue. This follows from odd degree real polynomials having roots.</p> <p>Then, one shows $E({\mathbb C},2,1)$. For this, let $V$ be a ${\mathbb C}$-vector space of odd degree n, and let $L(V)$ be the space of ${\mathbb C}$-linear transformations of $V$ to itself. Given a linear $T:V\to V$, one associates to it a real-vector subspace of $L(V)$ of real dimension $n^2$, and a pair of commuting linear maps there, in a way that from any common (real) eigenvalue we can reconstruct a complex eigenvalue of $T$. Then one uses $E({\mathbb R},2,2)$.</p> <p>One then argues by induction on $k$ that $E({\mathbb C},2^k,1)$ holds. As before, to a $T:V\to V$ with $V$ of appropriate dimension $n$, one associates a complex subspace of $L(V)$ of dimension $n(n-1)/2$ and a pair of commuting linear maps there, so the result follows from $E({\mathbb C},2^{k-1},2)$.</p> <p>(I must confess I haven't worked through the details enough to comment on whether this is essentially Gauss' proof in a different language.)</p>