# Strong induction without a base case

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.

-
Interesting question. (I confess that, in the introduction to proofs class I taught twice in the last year, I didn't want to address the logical superfluity of the base case in strong induction for fear it would confuse my students. But I guess MIT students are not so easily confused.) Why is it tagged combinatorics? – Pete L. Clark Jan 16 '10 at 6:47
This comment is too facetious to be an answer, but you could let P(n) be the statement "P(t) is true for all 0<=t<n" ;-) – Kevin Buzzard Jan 16 '10 at 8:35
Bjorn, this phenomenon is not limited to induction on the natural numbers, but arises naturally in transfinite recursion also. Indeed, it is usually considered a feature of a properly performed transfinite recursion if it has the property you state. Perhaps you want to generalize your question? – Joel David Hamkins Jan 16 '10 at 23:03
Yes, I'm aware of transfinite induction, but since the thrust of my question is the same in that setting as in the natural number setting, I phrased my question in the most elementary terms. – Bjorn Poonen Jan 16 '10 at 23:33
@Pete: As for the combinatorics tag: I couldn't find a better one. I was thinking that "discrete math" might be appropriate, and combinatorics seemed to be closest to this. Feel free to re-tag the question. – Bjorn Poonen Jan 16 '10 at 23:49

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.

-
I like this lead. Fermat's proof that $x^4 - y^4 = z^2$ has no nontrivial integer solutions might be a more convincing example. See http%3A%2F%2Fen.wikipedia.org%2Fwiki%2FProof_of_Fermat%27s_Last_Theorem_for_spec‌​ific_exponents%23n.C2.A0.3D.C2.A04 – François G. Dorais Jan 17 '10 at 2:03
Why, any proof that uses Fermat's method of infinite descent invariably uses the strong induction. Or am I committing a blunder here? – Abhishek Parab Jan 17 '10 at 4:01
Infinite descent was Fermat's signature tool. He at least deserves credit for popularizing the method. Earlier uses of induction that I'm aware of were either "Greek style" (case 1, case 2, case 3, end with etc.) or the more sophisticated: start with n and keep going down by 1 until you reach the base case. The first occurrence of real induction that I know is from Pascal, so shortly after Fermat. – François G. Dorais Jan 17 '10 at 5:01
It doesn't work since verifying descent requires proving p/2 < p so requires proof that p isn't 0, i.e. disproving the base case P(0). Even if you start at 1 vs. 0 there are still analogous objections. – Bill Dubuque Jul 7 '10 at 21:10
@Joel Yes, without a rigorous definition of what it means to "not treat the base case separately" the question cannot be answered. I've seen many dozens of similar questions in various forums and a consensus is never reached due to the lack of such precision. – Bill Dubuque Jul 22 '10 at 22:13

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.

-
You're ok, this does use strong induction. – François G. Dorais Jan 17 '10 at 2:10
Really? Although one could run through the argument as a strong induction type statement, it only involves two adjacent cases. I tend to think of true strong inductive arguments as those (like factorization into primes) where you prove one case by appealing to some earlier case, but it in practice is not going to be the immediately preceding case. – KConrad Jan 17 '10 at 2:29
It's not the immediately preceding case: $d(X)$ has degree less than $n$, not necessarily $n-1$. (The $n+1$ is misleading, it's just the smallest integer bigger than $n$.) – François G. Dorais Jan 17 '10 at 2:32
Good example! One comment: The claim is stronger, and the inductive step clearer, if in the claim you change "polynomial of nonzero degree" to "nonzero polynomial". – Bjorn Poonen Jan 18 '10 at 6:07
Not only is it not an example, it is not a correct proof. The difference $d(X)$ has not been shown to have nonzero degree, so the induction hypothesis does not apply. If you replace "of nonzero degree" by "nonzero" in the statement, then the argument becomes correct. The smallest case $n=0$ then constructs to a nonzero polynomial of negative degree which ...(vacuous); this is a contradiction in itself. Since no appeal is made to the induction hypothesis for $n=0$, one might say the case is handled differently though. In any case it falls under the "minimal counterexample cannot exist" label. – Marc van Leeuwen Nov 16 '11 at 14:56

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

• V0 = 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 Vn. 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 Vn, where Vn = U { P(Vm | 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.

-
It seems to me that, when you use the improved (non-case-splitting) definition of the hierarchy, the particular facts you mention at the end --- transitivity and monotonicity --- can be proved without any induction at all (provided you know that the < relation on ordinals is transitive). But I agree that other facts about the hierarchy become provable by non-case-splitting inductions. – Andreas Blass Dec 25 '10 at 0:11

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.

-
Neither of those cases hold if n = 1, so I guess you want to start the induction at n = 2. In that case the existence proof with "prime" replaced by "irreducible" works in any Noetherian commutative ring and this Noetherian induction also doesn't have a base case, I guess. – Qiaochu Yuan Jan 16 '10 at 23:15
Nitpick: Perhaps replace positive by $\geq 2$ in the statement, otherwise the base case is different, though clearly not an "anchor case." – François G. Dorais Jan 16 '10 at 23:18
Thanks, I corrected. @Qiaochu: Yes, but the question wants the most elementary example, so I complied. – Joel David Hamkins Jan 16 '10 at 23:25
@Joel: That is a nice example of strong induction, but I am really hoping for an argument that does not need a separate case to get started (here the separate case is the case where n is prime). Sorry if my question is vague; I'm not sure I can formalize what I want. – Bjorn Poonen Jan 16 '10 at 23:26
OK, I'm beginning to understand what you want. So I posted another example, on the cumulative hierarchy (see below....or above?) – Joel David Hamkins Jan 17 '10 at 0:24

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.

-

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.

-
There is another of this same fact called noetherian induction by applying the descending chain condition on the spectrum of a noetherian ring. – Harry Gindi Jan 17 '10 at 1:06

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

-

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

-
This doesn't seem to be the kind of example that was requested. First, the argument here seems more naturally carried out with (weak) induction, rather than strong induction, since the induction appeals to the immediately preceding case. Secondly, the nature of the argument at n=0, even if you do it with strong induction, is not the same as for other n, so it treats what amounts to the base case differently. – Joel David Hamkins Jan 21 '10 at 13:19
Here is the proof by strong induction I had in mind. Suppose by strong induction that $S(k) = 2^k$ for all $k < n$. Then $S(n) = 1 + \sum_{k=0}^{n-1} S(k) = 1 + \sum_{k=0}^{n-1} 2^k = 1 + (2^n - 1) = 2^n$. (The third equation is using the usual formula for geometric series.) The proof seems to be using strong induction, not weak induction. I don't think I needed to handle n = 0 separately. If you'd rather avoid the appeal to the formula for geometric series, then the examples in my other answer might be better. – Ravi Boppana Jan 21 '10 at 13:59
@Ravi: Yes, I thought that is what you had had in mind. My point was that your defining recurrence formula simplifies in one step to S(n+1)=S(n)+S(n), which avoids the series and seems naturally treated with weak induction. – Joel David Hamkins Jan 21 '10 at 19:10

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

-

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.

-

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

-

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.

-

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.

-

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

-
@RaviB: how on earth did your comment get minused ? I understand where trying to get. The problem that I am referring to is one of systemic level. The way we build up definitions for various systems necessitates base cases. – steve Jan 22 '10 at 6:22

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

-
To apply the induction hypothesis "for all natural numbers k smaller than n ..." to n-1, you need not only that (as you said) n-1 < n but also that n-1 is a natural number. That fails when n=0, so your argument doesn't cover the case n=0. – Andreas Blass Jul 3 '10 at 4:45
Right, so basically we need to check the base case, n = 0. I'm feeling that, the assumption that $\forall k < 0 P(k)$ is true leads to these kind of problems and even in the strong induction I should check the base case. That said, I don't understand why strong induction says that you don't need to prove the base case. – Himanshu Jul 3 '10 at 5:04
Strong induction doesn't require you to prove the base case provided you really prove all the things that strong induction does require you to prove, namely the "strong induction step" for all n, not just (as you did) for n not equal to 0. In some cases, like your example, a complete proof of the strong induction step may involve treating the n=0 case separately, and then it looks like a base case. Nevertheless, it's a part of the strong induction step. – Andreas Blass Jul 3 '10 at 17:18
Somehow Andreas's explanation reminds me of the "proof" that all horses are of the same colour. – Willie Wong Jul 7 '10 at 21:25
In broad terms, this is the same story as the horses: An alleged proof by induction on n fails to handle one value of n, and thus gives nonsense for that value and for larger n. The difference is that Himanshu's argument failed to cover the case n=0, while the horse argument fails to cover the case n=2. – Andreas Blass Jul 8 '10 at 1:09