Easier induction proofs by changing the parameter - MathOverflow

Easier induction proofs by changing the parameter

2011-01-11T15:00:56Z

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.

König's theorem. 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)$.

Proof. 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,

$v(G)=|M|=v(G-e)=\rho(G-e)$.

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$.

Question. What are some other instances (not necessarily in graph theory), where simply changing the induction parameter results in a nice shorter proof?

Answer by Lloyd Smith for Easier induction proofs by changing the parameter

2011-01-11T15:27:15Z

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.

Answer by Pietro Majer for Easier induction proofs by changing the parameter

2011-01-11T15:46:39Z

Cauchy's proof by induction of the inequality between the arithmetic and geometric means (written in his 1821 Cours d'Analyse).

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$

Answer by Andres Caicedo for Easier induction proofs by changing the parameter

2011-01-11T17:28:36Z

Gauss' "second" (1815) proof of the fundamental theorem of algebra (Werke, Volume 3, 33-56, or see Paul Taylor's translation, currently available here) 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.)

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.

So the pattern is induction not on the degree $n$ of the polynomial, but on the largest power of 2 dividing $n$.

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.)

The skeleton of Derksen's proof is as follows: One actually shows that:

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.

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.

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)$.

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.

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)$.

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)$.

(I must confess I haven't worked through the details enough to comment on whether this is essentially Gauss' proof in a different language.)