Strong induction without a base case - MathOverflow

Strong induction without a base case

2010-01-16T06:16:42Z

Strong induction proves a sequence of statements $P(0)$, $P(1)$, $\ldots$ by proving the implication

"If $P(m)$ is true for all nonnegative integers $m$ less than $n$, then $P(n)$ is true."

for every nonnegative integer $n$. There is no need for a separate base case, because the $n=0$ instance of the implication is 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$).

Can you think of a natural example of a strong induction proof that does not treat the base case separately? 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.

Answer by Gerhard Paseman for Strong induction without a base case

2010-01-16T07:34:47Z

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.

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 <=i <= n) <= max (a_i*b_p(i), 1 <= i <= n) .

Proof sketch (by strong induction?): Assume the result is true for all m < 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.

The above may not be the most natural example nor the best proof of the result.
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.

Gerhard "Ask Me About System Design" Paseman, 2010.01.15

Answer by Mike Shulman for Strong induction without a base case

2010-01-16T22:15:06Z

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 < is well-founded 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.

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 attempt to be a partial function $A\rightharpoonup B$ whose domain is down-closed for < 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.

In classical logic, where emptiness of a set is decidable, we could 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.

Answer by Joel David Hamkins for Strong induction without a base case

2010-01-16T23:11:04Z

I think the best example of this will be the fundamental theorem of aithmetic: the assertion that every natural number greater than 1 is either prime or the product of primes (and uniquely so).

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 < n, and by induction these are products of primes, so n is also. QED (and no need for special anchor case).

Proof of uniqueness does not use induction.

Answer by Joel David Hamkins for Strong induction without a base case

2010-01-17T00:12:09Z

The cumulative hierarchy in set theory is the hierarchy V_α that is often defined by the transfinite recursion:

V₀ = emptyset
V_α+1 = P(V_α), taking the power set at successor stages
V_λ = U{ V_α | α<λ }, taking unions at limits.

And if one wants to consider only the class HF of hereditarily finite sets, one restricts to the natural number induction α=n, leading to HF = V_ω = U V_n. These definitions, however, split into separate cases for zero, successor and limit.

An equivalent definition, however, completely avoids this split. Namely:

For any ordinal α, let V_α = U { P(V_β) | β < α }.

This is easily seen to be equivalent to the previous definition.

Similarly, one can define the hereditary finite sets HF as the union of V_n, where V_n = U { P(V_m | m < n }. This definition needs no base case, and does not split into cases.

One can now prove all the basic facts about the V_α hierarchy, also without splitting into zero, successor and limit cases. For example, every V_α is transitive, since by induction it is the union of transitive sets. Similarly, the hierarchy is increasing, etc.

Answer by François G. Dorais for Strong induction without a base case

2010-01-17T00:39:16Z

This is perhaps a rather strange example. There is a paper of Andreas Blass An induction principle and pigeonhole principle for K-finite sets (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.

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.

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

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

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.

If $f^{-1}[A] = A$, then $f[A] \subseteq A$ and so $f[A]$ is certainly not all of $B$.

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

Answer by Joel David Hamkins for Strong induction without a base case

2010-01-17T01:39:16Z

My example is the classical proof that sqrt(2) is irrational.

More generally, many proofs that proceed by showing that there are no minimal counterexamples 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".

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.

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

Answer by KConrad for Strong induction without a base case

2010-01-17T01:53:41Z

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:

Claim: A nonzero polynomial (over a field) has no more roots than its degree.

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

[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.]

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.

Answer by Ravi Boppana for Strong induction without a base case

2010-01-19T03:04:01Z

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

Answer by steve for Strong induction without a base case

2010-01-21T09:53:02Z

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

Answer by Ravi Boppana for Strong induction without a base case

2010-01-21T12:38:03Z

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

Answer by Himanshu for Strong induction without a base case

2010-07-03T04:25:24Z

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

Theorem: Prove that for all $n \in N$, $1.3^0 + 3.3^1 + 5.3^2 + .. + (2n+1)3^n = n3^{n+1}$

Proof:

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

Since (n-1) < 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$

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

Hence, by the assumptions of strong induction, $1.3^0 + 3.3^1 + 5.3^2 + .. + (2n+1)3^n = n3^{n+1}$

Answer by Arturo Magidin for Strong induction without a base case

2010-07-03T19:02:00Z

This may qualify, though there is a special case hidden inside the argument.

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.

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

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

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.

Answer by Bill Dubuque for Strong induction without a base case

2010-07-07T21:14:21Z

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

Answer by Mariano Suárez-Alvarez for Strong induction without a base case

2010-07-07T21:23:41Z

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.

Answer by David Feldman for Strong induction without a base case

2010-12-24T22:31:34Z

One may transform any strong induction proof into one which (legalistically speaking!) doesn't explicitly treat the base case.

Proving $P(n)$ by induction, one assumes $ \forall k<n \ P(k)$ which weakens to $\forall k<n\ P(0)\implies P(k)$. 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.

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.

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.