3
$\begingroup$

In the book How to Prove It, they say that strong induction requires no base case. My professor's notes also say this. However, while I understand weak and strong induction, as well as the difference and reasoning as to why we would use one versus the other, something about "not having a base case" really bothers me.

The argument made by all those texts which say strong induction requires no base case go as follows. Strong induction requires: if we have that $[\forall k \in N, k<n, P(k)] \rightarrow P(n)$ holds true, then $P(n)$ is true for all $n\in N$.

The argument for $P(0)$ holds true vacuously since $[\forall k \in N, k<0, P(k)]$ is always false (i.e. there are no natural numbers that are less than zero) so we have that $[\forall k \in N, k<0, P(k)] \rightarrow P(0)$. Therefore, $P(0)$ is proven as the base case while proving the inductive hypothesis.

However this is obviously not true. The statement $a \rightarrow b$ doesn't prove $b$ unless $a$ is true. If $a$ is always false, we don't know anything about $b$; we just know that the statement if $a$ then $b$ is correct. So my issue is that we know nothing about $P(0)$. Here I can use "strong induction" to prove something that is false if I don't have to prove a base case:

All natural numbers are even. No base case required. Well, suppose that $[\forall k \in N, k<n, P(k)]$ this is true. Then it's clearly true for $n$, since $n=(n-2)+2$. Since $n-2$ is even by the hypothesis, and $n-2+2$ is just adding 2 to an even number, we still have an even number.

If you required base cases, this would obviously fail. Am I missing something? Why do these books still say that no base case is required? The Wikipedia page for induction still says a base case is needed, and many similar questions on StackExchange regarding this subject seem to be in the middle of a debate around this.

$\endgroup$
6
  • 3
    $\begingroup$ I have never heard that claim before. It's baseless. $\endgroup$ – Randall Oct 19 '17 at 0:27
  • 5
    $\begingroup$ $[\forall k\in\Bbb N, k<0:P(k)]$ is vacuously true. $\endgroup$ – Graham Kemp Oct 19 '17 at 0:32
  • $\begingroup$ @GrahamKemp If this is the case, then it forces $P(0)$ to be true. Then doesn't this make it possible to prove false things for $k=0$ such as the above all natural numbers $n$ are even? Where did I go wrong there? $\endgroup$ – user7240099 Oct 19 '17 at 0:39
  • 1
    $\begingroup$ Induction and strong induction alike are akin to knocking down dominoes. In normal induction you have one long line of dominoes that once you push over the domino at the front will cause a chain reaction that knocks down all of the rest. Each domino individually is heavy enough to knock down the next. Strong induction on the other hand is a potentially much more complicated setup of dominoes which requires the added weight of the previous dominoes to continue to knock more down. The base case or base cases are those initial dominoes you knock down. Without them starting, nothing happens. $\endgroup$ – JMoravitz Oct 19 '17 at 0:40
  • 2
    $\begingroup$ @user7240099 It doesn't force $P(0)$ to be true unless you can make a valid logical argument that $\forall n\in\Bbb n:\big([\forall k\in\Bbb N, k<n: P(k)]\to P(n)\big)$ holds. $\endgroup$ – Graham Kemp Oct 19 '17 at 0:47
8
$\begingroup$

The argument is off a bit: in fact, $[\forall k \in \mathbb{N}, k < 0 \rightarrow P(k)]$ is vacuously true. This is because for any $k \in \mathbb{N}$, $k < 0$ is false, so the implication $k < 0 \rightarrow P(k)$ is true. So, if you've proven the required statement $\forall n \in \mathbb{N}, [ \forall k \in \mathbb{N}, k < n \rightarrow P(k) ] \rightarrow P(n)$, then the special case with $n=0$ always has the hypothesis true, which implies that the conclusion $P(0)$ is also true.

As for your bogus proof that all natural numbers are even: in applying the inductive hypothesis, you're implicitly assuming that $n-2 \in \mathbb{N}$. But for $n=0$ and for $n=1$, this is not valid, so it is not valid to apply the inductive hypothesis. And in fact, $[\forall k \in \mathbb{N}, k < 1 \rightarrow P(k)] \rightarrow P(1)$ is false: the hypothesis is true because the only possible $k$ is $k=0$, but the conclusion $P(1)$ is invalid.

(For a similar situation in which an inductive proof looks good at first, but on closer examination the proof of the inductive step implicitly assumes $n$ is large and the argument breaks down for small $n$: see the bogus proof that "all horses are the same color".)

This illustrates what will often happen in practical proofs by strong induction: there will in fact be cases in which you cannot apply the inductive hypothesis to smaller cases, so you will have to prove those cases by a separate argument. These special cases will end up looking very much like base cases.

So, for instance, the following argument that every natural number is either even or odd is valid: we assume the strong inductive hypothesis $[\forall k \in \mathbb{N}, k < n \rightarrow even(k) \vee odd(k)]$; and we need to prove $even(n) \vee odd(n)$. Now if $n=0$, $n$ is even; and if $n=1$, $n$ is odd. Otherwise, $n-2 \in \mathbb{N}$ and $n-2 < n$, so by the inductive hypothesis, either $n-2$ is even or $n-2$ is odd. In the first case, $n = (n-2) + 2$ is even; in the second case, $n = (n-2) + 2$ is odd.

$\endgroup$
2
  • 2
    $\begingroup$ So, just to reinforce what you've already said: it is strictly logically true that you don't need a base case for strong induction. But in practice, it's rare for your proof of the inductive step to hold for the early cases. $\endgroup$ – Jason DeVito Oct 19 '17 at 0:49
  • 1
    $\begingroup$ I see, so this is why so many strong induction examples have base cases. We have to basically make sure the hypothesis implies the base case (or applies to/covers the case of $n=0$), we can't just assume so, correct? $\endgroup$ – user7240099 Oct 19 '17 at 1:01
2
$\begingroup$

Strong Induction :

We let $n$ refer to some arbitrary natural number, and by assuming $P(0),..., P(n-1)$, we make a valid argument that this infers, $P(n)$.   Thus we conclude $\forall n\in\Bbb N:P(n)$.

Thus we don't need to prove the base case $P(0)$ is true to make the strong inductive argument.   Although a proof might do so; there is nothing prohibiting it.

The argument for $P(0)$ holds true vacuously since $[\forall k \in N, k<0, P(k)]$ is always false (i.e. there are no natural numbers that are less than zero) so we have that $[\forall k \in N, k<0, P(k)] \rightarrow P(0)$. Therefore, $P(0)$ is proven as the base case while proving the inductive hypothesis.

No, the argument is that $[\forall k\in N, k<0: P(k)]$ is vacuously true.   There does not exist a natural number less than $0$ where the premise does not hold.

So, since $[\forall k\in\Bbb N, k<0:P(k)]$ is vacuously true, and if $[\forall k\in\Bbb N, k<n:P(k)]\to P(n)$ can be proven for an arbitrary natural number, then $P(0)$ will be true.   And then so will $P(1)$, $P(2)$, and cetera.

Still, it is safest to check.


All natural numbers are even. No base case required. Well, suppose that $[\forall k \in N, k<n, P(k)]$ this is true. Then it's clearly true for $n$, since $n=(n-2)+2$. Since $n-2$ is even by the hypothesis, and $n-2+2$ is just adding 2 to an even number, we still have an even number.

No, to have a valid strong induction you need an argument that establishes that the truth of $P(n)$ is entailed by $P(k)$ holding for all $k$ which are naturals less than $n$; not just for some of them.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.