Strong induction without a base case - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-24T10:35:31Z http://mathoverflow.net/feeds/question/11964 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/11964/strong-induction-without-a-base-case Strong induction without a base case Bjorn Poonen 2010-01-16T06:16:42Z 2011-11-17T05:41:39Z <p>Strong induction proves a sequence of statements $P(0)$, $P(1)$, $\ldots$ by proving the implication </p> <p>"If $P(m)$ is true for all nonnegative integers $m$ less than $n$, then $P(n)$ is true." </p> <p>for every nonnegative integer $n$. There is no need for a separate base case, because the $n=0$ instance of the implication <em>is</em> the base case, vacuously. But most strong induction proofs nevertheless seem to involve a separate argument to handle the base case (i.e., to prove the implication for $n=0$).</p> <p><strong>Can you think of a natural example of a strong induction proof that does <em>not</em> treat the base case separately?</strong> Ideally it should be a statement at the undergraduate level or below, and it should be a statement for which strong induction works better than ordinary induction or any direct proof.</p> http://mathoverflow.net/questions/11964/strong-induction-without-a-base-case/11971#11971 Answer by Gerhard Paseman for Strong induction without a base case Gerhard Paseman 2010-01-16T07:34:47Z 2010-01-16T07:34:47Z <p>I posted an answer on sci.math.research recently where I used induction with a base case, and then thought I could use strong induction instead. Later another poster came up with a nice argument that hid or did away with the induction. Perhaps you can frame it to fit your needs.</p> <p>The problem: Given an ascending sequence b_i and descending sequence a_i, both containing n positive numbers, show that for every permutation p on n letters that max (a_i*b_i, 1 &lt;=i &lt;= n) &lt;= max (a_i*b_p(i), 1 &lt;= i &lt;= n) .</p> <p>Proof sketch (by strong induction?): Assume the result is true for all m &lt; n. If p fixes n, we're done. Otherwise, swap b_n and b_p(n) and note that the maximum will not increase. Done.</p> <p>The above may not be the most natural example nor the best proof of the result.<br /> It may suggest something that will help. Although it could be argued that this is a "strong inductive" example of a different proof, I think it could also be argued that the different proof is one that hides the inductive principle at work. Now let the community judge.</p> <p>Gerhard "Ask Me About System Design" Paseman, 2010.01.15</p> http://mathoverflow.net/questions/11964/strong-induction-without-a-base-case/12030#12030 Answer by Mike Shulman for Strong induction without a base case Mike Shulman 2010-01-16T22:15:06Z 2011-11-17T05:41:39Z <p>Any constructively valid proof by well-founded induction, specialized to the natural numbers as a particular well-founded set, will be an example. Recall that a set $A$ with a relation &lt; is <em>well-founded</em> if for any $S\subseteq A$, if $(\forall y\lt x)(y\in S) \Rightarrow x\in S$, then $S=A$. A proof by well-founded induction proceeds by proving that the set $S$ of "all $x\in A$ such that blah" satisfies that condition, i.e. that if blah is true for all $y\lt x$, then it is also true for $x$. In classical logic, one can separate out such a proof into "case 1: there are no $y\lt x$" and "case 2: there are some $y\lt x$", but in constructive logic this is not generally possible. (It is still possible in the particular case of strong induction on the naturals, since equality of naturals is decidable.) However, interesting proofs by well-founded induction do still exist constructively.</p> <p>For example, if $A$ is well-founded, and $B$ is equipped with a function $t\colon P B \to B$, then one can prove by well-founded induction on $A$ that there is a unique function $f\colon A\to B$ defined by well-founded recursion, i.e. such that for all $x\in A$ we have $f(x) = t(\lbrace f(y) \mid y \in A \wedge y \lt x\rbrace)$. Define an <em>attempt</em> to be a partial function $A\rightharpoonup B$ whose domain is down-closed for &lt; and which satisfies the desired condition insofar as it is defined. We can then prove by well-founded induction that any two attempts are equal on the intersection of their domains, and that for all $x$ there exists an attempt whose domain contains $x$, hence the union of all attempts is the desired function.</p> <p>In classical logic, where emptiness of a set is decidable, we <em>could</em> separate out the empty set as a special case in this argument (or any other), but it wouldn't gain us anything; it would be just as "non-genuine" as Tran Chieu Minh's construction in the other direction.</p> http://mathoverflow.net/questions/11964/strong-induction-without-a-base-case/12037#12037 Answer by Joel David Hamkins for Strong induction without a base case Joel David Hamkins 2010-01-16T23:11:04Z 2010-01-16T23:24:23Z <p>I think the best example of this will be the <a href="http://en.wikipedia.org/wiki/Fundamental%5Ftheorem%5Fof%5Farithmetic" rel="nofollow">fundamental theorem of aithmetic</a>: the assertion that every natural number greater than 1 is either prime or the product of primes (and uniquely so). </p> <p>Proof of existence is by strong induction. Assume true below n. If n is prime, we're done. Otherwise, n = ab for some a,b &lt; n, and by induction these are products of primes, so n is also. QED (and no need for special anchor case).</p> <p>Proof of uniqueness does not use induction.</p> http://mathoverflow.net/questions/11964/strong-induction-without-a-base-case/12054#12054 Answer by Joel David Hamkins for Strong induction without a base case Joel David Hamkins 2010-01-17T00:12:09Z 2010-01-17T00:31:08Z <p>The cumulative hierarchy in set theory is the hierarchy V<sub>&alpha;</sub> that is often defined by the transfinite recursion:</p> <ul> <li>V<sub>0</sub> = emptyset</li> <li>V<sub>&alpha;+1</sub> = P(V<sub>&alpha;</sub>), taking the power set at successor stages</li> <li>V<sub>&lambda;</sub> = U{ V<sub>&alpha;</sub> | &alpha;&lt;&lambda; }, taking unions at limits.</li> </ul> <p>And if one wants to consider only the class HF of hereditarily finite sets, one restricts to the natural number induction &alpha;=n, leading to HF = V<sub>&omega;</sub> = U V<sub>n</sub>. These definitions, however, split into separate cases for zero, successor and limit.</p> <p>An equivalent definition, however, completely avoids this split. Namely:</p> <ul> <li>For any ordinal &alpha;, let V<sub>&alpha;</sub> = U { P(V<sub>&beta;</sub>) | &beta; &lt; &alpha; }. </li> </ul> <p>This is easily seen to be equivalent to the previous definition.</p> <p>Similarly, one can define the hereditary finite sets HF as the union of V<sub>n</sub>, where V<sub>n</sub> = U { P(V<sub>m</sub> | m &lt; n }. This definition needs no base case, and does not split into cases.</p> <p>One can now prove all the basic facts about the V<sub>&alpha;</sub> hierarchy, also without splitting into zero, successor and limit cases. For example, every V<sub>&alpha;</sub> is transitive, since by induction it is the union of transitive sets. Similarly, the hierarchy is increasing, etc.</p> http://mathoverflow.net/questions/11964/strong-induction-without-a-base-case/12055#12055 Answer by François G. Dorais for Strong induction without a base case François G. Dorais 2010-01-17T00:39:16Z 2010-01-17T01:15:03Z <p>This is perhaps a rather strange example. There is a paper of Andreas Blass <a href="http://www.math.lsa.umich.edu/~ablass/kfin.pdf" rel="nofollow"><em>An induction principle and pigeonhole principle for K-finite sets</em></a> (J. Symbolic Logic 59, 1995, 1186-1193) where the goal is to give an intuitionistic proof of that there is no surjection from $X$ onto $X+1$ when $X$ is finite (Theorem 2). Before proving this result, Blass proves a strong induction principle for finite sets (Theorem 1). The proof of Theorem 1 uses ordinary induction with a base case, but the proof of Theorem 2 uses the strong induction principle of Theorem 1 instead. Blass' proof of Theorem 2 very straightforward, but I think that a direct proof of Theorem 2 (along the same lines) would be unbearably long.</p> <p><hr /></p> <p>I guess it's hard to understand this one without seeing the proofs. So I'll give a similar proof (without the intuitionistic fuss, for clarity). The strong induction on finite sets I will use is the following.</p> <p>(SI) If $\mathcal{K}$ is a family of sets such that if all proper subsets of $A$ are in $\mathcal{K}$ then $A$ is in $\mathcal{K}$ too, then $\mathcal{K}$ contains all finite sets.</p> <p>Let $\mathcal{K}$ be the family of all sets $A$ such that if $A$ is a proper subset of $B$ and $f:A \to B$ then the image $f[A]$ is not all of $B$. I claim that $\mathcal{K}$ satisfies the hypothesis of (SI).</p> <p>Suppose all proper subsets of $A$ are in $\mathcal{K}$. Let $B$ be a proper superset of $A$. Given $f:A \to B$, we consider two cases. </p> <p>If $f^{-1}[A] = A$, then $f[A] \subseteq A$ and so $f[A]$ is certainly not all of $B$. </p> <p>If $A' = f^{-1}[A]$ is a proper subset of $A$. Then $A' \in \mathcal{K}$ and hence $f[A']$ is not all of $A$. But then $A \setminus f[A'] = A \setminus f[A] \subseteq B \setminus f[A]$, which shows that $f[A]$ is not all of $B$.</p> http://mathoverflow.net/questions/11964/strong-induction-without-a-base-case/12061#12061 Answer by Joel David Hamkins for Strong induction without a base case Joel David Hamkins 2010-01-17T01:39:16Z 2010-01-17T03:08:17Z <p>My example is the classical proof that sqrt(2) is irrational.</p> <p>More generally, many proofs that proceed by showing that there are no <a href="http://en.wikipedia.org/wiki/Minimal%5Fcounterexample" rel="nofollow">minimal counterexamples</a> exemplify your phenomenon. The method of no-minimal-counterexamples is exactly the same as strong induction, but where one proves the required implication by contradiction. In many applications of this method, it is often clear that the smallest numbers are not counterexamples, and this would not ordinarily regarded as a separate base "case".</p> <p>In the classical proof that sqrt(2) is irrational, for example, we suppose sqrt(2) = p/q, where p is minimal. Now, square both sides and proceed with the usual argument, to arrive at a smaller counterexample. Contradiction! This amounts to a proof by strong induction that no rational number squares to 2, and there seems to be no separate base case here.</p> <p>People often carry out the classical argument by assuming p/q is in lowest terms, but the argument I just described does not need this extra complication. Also, in any case, the proof that every rational number can be put into lowest terms is itself another instance of the phenomenon. Namely, if p/q is a counterexample with p minimal, then divide by any common factor and apply induction. There seems to be no separate base case here where it is already in lowest terms, since we were considering a minimal <em>counterexample</em>. Perhaps someone objects that there is no induction here at all, since one can just divide by the gcd(p,q). But the usual proof that any two numbers have a gcd is, of course, also inductive: considering the least linear combination xq+yp amounts to strong induction, again with no separate base case.</p> http://mathoverflow.net/questions/11964/strong-induction-without-a-base-case/12062#12062 Answer by KConrad for Strong induction without a base case KConrad 2010-01-17T01:53:41Z 2011-11-17T04:01:06Z <p>I hope the following will satisfy Bjorn. It is a proof by induction which naturally skips over the base case and is at the undergraduate level. I saw the argument for the first time today in the paper containing 10 proofs in Russian of the Fundamental Theorem of Algebra which Ilya Nikokoshev made a link to in his answer to a question asking for lots of different proofs of that theorem. Here we go:</p> <p>Claim: A nonzero polynomial (over a field) has no more roots than its degree.</p> <p>Proof: We prove this by induction on the degree $n$ of the polynomial. Assume that the polynomial $$p(X) = a_nX^n + \cdots + a_1X + a_0$$ of degree $n$ has at least $n+1$ different roots $r_1,\dots, r_{n+1}$. Consider the polynomial $$q(X) = a_n(X-r_1)\cdots (X-r_n).$$ We have $p(X) \not= q(X)$ since $p(r_{n+1}) = 0$ and $q(r_{n+1}) \not= 0$. The difference $d(X) = p(X) - q(X)$ is a nonzero polynomial of degree less than $n$ having at least $n$ roots $r_1,\dots,r_n$. This contradicts the inductive hypothesis. QED</p> <p>[EDIT: IGNORE what follows in the next paragraph, which was in the original post, since I confused myself about strong vs. ordinary induction. The above proof is by strong induction since the degree of d(X) is merely less than n and not necessarily n-1 itself.]</p> <p>One aspect of this which does not fit Bjorn's request is that this argument uses ordinary induction, not strong induction. But really, is that such a big deal? I suspect his main interest is seeing an inductive argument at all where the base case is naturally not mentioned, rather than specifically one using strong induction. </p> http://mathoverflow.net/questions/11964/strong-induction-without-a-base-case/12270#12270 Answer by Ravi Boppana for Strong induction without a base case Ravi Boppana 2010-01-19T03:04:01Z 2010-01-19T03:04:01Z <p>Here's another possible example. Let S(0), S(1), S(2), ..., be the sequence of numbers defined by the formula $S(n) = 1 + \sum_{k=0}^{n-1} S(k)$ for every nonnegative integer n. Then we can show that $S(n) = 2^n$ by strong induction on $n$.</p> http://mathoverflow.net/questions/11964/strong-induction-without-a-base-case/12521#12521 Answer by steve for Strong induction without a base case steve 2010-01-21T09:53:02Z 2010-01-21T09:53:02Z <p>@RaviB: You still got the "base case" issue, namely, 2^0 =1; @poonen: structurally speaking, we will always be in need of a base case regardless of whether strong or ordinary reduction is used. </p> http://mathoverflow.net/questions/11964/strong-induction-without-a-base-case/12534#12534 Answer by Ravi Boppana for Strong induction without a base case Ravi Boppana 2010-01-21T12:38:03Z 2010-01-21T12:38:03Z <p>@steve: I'm not sure I understand your objection, but how about this modification. Let A be defined by $A(n) = \sum_{k=0}^{n-1} A(k)$ for every nonnegative integer n. Then by strong induction we can show that A(n) = 0. That's a trivial example, but if we wanted to, we could make it less trivial: $B(n) = 1 - n + \sum_{k=0}^{n-1} B(k)$, which has solution $B(n) = 1$. </p> http://mathoverflow.net/questions/11964/strong-induction-without-a-base-case/30372#30372 Answer by Himanshu for Strong induction without a base case Himanshu 2010-07-03T04:25:24Z 2010-07-03T04:25:24Z <p>I'm confused a little about not proving base case in strong induction. Can someone point out the error in following proof( I'm using strong induction)?</p> <p>Theorem: Prove that for all $n \in N$, $1.3^0 + 3.3^1 + 5.3^2 + .. + (2n+1)3^n = n3^{n+1}$</p> <p>Proof:</p> <p>Let n be arbitrary natural number. Suppose, for all natural numbers k smaller than n, $1.3^0 + 3.3^1 + 5.3^2 + .. + (2k+1)3^k = k3^{k+1}$</p> <p>Since (n-1) &lt; n, Then it follows from our assumption that $1.3^0 + 3.3^1 + 5.3^2 + .. (2n-1)3^{n-1} = (n-1)3^n$</p> <p>So, $1.3^0 + 3.3^1 + 5.3^2 + .. + (2n+1)3^n$ = $1.3^0 + 3.3^1 + 5.3^2 + .. (2n-1)3^{n-1} + (2n+1)3^n$ = $(1.3^0 + 3.3^1 + 5.3^2 + .. (2n-1)3^{n-1}) + (2n+1)3^n$ = $(n-1)3^n + (2n+1)3^n$ = $3n.3^n$ = $n3^{n+1}$</p> <p>Hence, by the assumptions of strong induction, $1.3^0 + 3.3^1 + 5.3^2 + .. + (2n+1)3^n = n3^{n+1}$</p> http://mathoverflow.net/questions/11964/strong-induction-without-a-base-case/30448#30448 Answer by Arturo Magidin for Strong induction without a base case Arturo Magidin 2010-07-03T19:02:00Z 2010-07-03T19:02:00Z <p>This may qualify, though there is a special case hidden inside the argument.</p> <p>Consider a simplified game of nim in which there are $n>0$ matchsticks, a player may remove $1$, $2$, or $3$ matchsticks each turn, and the player who takes the last matchstick wins.</p> <p><b>Theorem.</b> The first player has a winning strategy if $n\not\equiv 0\pmod{4}$; the second player has a winning strategy if $n\equiv 0\pmod{4}$.</p> <p><i>Proof.</i> Strong induction on $n$. Assume the result holds for all $k\lt n$. If $n\equiv 0\pmod{4}$, then after player 1's turn there will be $k\lt n$ matchsticks left, with $k\not\equiv 0 \pmod{4}$. By the induction hypothesis, the first person to play at this point has a winning strategy, this being player 2; thus, player 2 has a winning strategy.</p> <p>If $n\not\equiv 0\pmod{4}$, then write $n=4\ell + t$ with $1\leq t\leq 3$. Have player 1 take $t$ matchsticks, leaving $4\ell$ matchsticks. If $\ell=0$, player 1 just won. If $\ell>0$, then there are $k\lt n$ matchsticks left, with $k\equiv 0\pmod{4}$. By the induction hypothesis, the player who moves second has a winning strategy, this being the original player 1. So player 1 has a winning strategy in this case. </p> http://mathoverflow.net/questions/11964/strong-induction-without-a-base-case/30957#30957 Answer by Bill Dubuque for Strong induction without a base case Bill Dubuque 2010-07-07T21:14:21Z 2010-07-07T21:14:21Z <p>It's difficult to answer such questions without a rigorous definition of what it means for a proof to 'treat the base case separately'. What if the base case is proved as the first step in a lemma that is invoked? Or explicitly somewhere way down the line in some long chains of lemmas. Does that count or not? It's really a subtle proof-theoretical question. @Born: did any reply satisfy you? If so, I'd be very interested to know which one(s).</p> http://mathoverflow.net/questions/11964/strong-induction-without-a-base-case/30959#30959 Answer by Mariano Suárez-Alvarez for Strong induction without a base case Mariano Suárez-Alvarez 2010-07-07T21:23:41Z 2010-07-07T21:23:41Z <p>One context in which one does inductive proofs without a base case is that of Conway's games/numbers, which are defined inductively without a base case.</p> http://mathoverflow.net/questions/11964/strong-induction-without-a-base-case/50312#50312 Answer by David Feldman for Strong induction without a base case David Feldman 2010-12-24T22:31:34Z 2010-12-25T18:30:04Z <p>One may transform any strong induction proof into one which (legalistically speaking!) doesn't explicitly treat the base case.</p> <p>Proving $P(n)$ by induction, one assumes <code>$\forall k&lt;n \ P(k)$</code> which weakens to <code>$\forall k&lt;n\ P(0)\implies P(k)$.</code> Now one may adapt whatever proof one had for the induction step to establish from this that $P(0)\implies P(n)$. Now one proves $P(0)$ and concludes $P(n)$ by modus ponens.</p> <p>Yes, I know, morally the base case still got special treatment, but formally now that happens in the induction step. Thus finding a formal distinction between theorems that require special treatment for the base case and those that don't seems impossible.</p> <p>In any case, if you can prove $\forall n\geq 0\ P(n)$ by strong induction, you can prove $\forall n>0 \ P(0)\implies P(n)$ by strong induction with no special treatment for the base case, morally or formally. So examples abound.</p>