3

In 1.2.1 Mathematical Induction section, Knuth presents mathematical induction as a two steps process to prove that P(n) is true for all positive integers n:

a) Give a proof that P(1) is true;

b) Give a proof that "if all P(1), P(2),..., P(n) are true, then P(n+1) is also true";

I have serious doubt about that. Indeed, I believe that point b) should be:

b) Give a proof that "if P(n) is true, then P(n+1) is also true". The major difference here is that you are only assuming that P(n) is true, not P(n-1), etc.

Or, at least, we should prove that P(1)...P(n) is true before proving P(n) => P(n+1).

However, these books are old and have been read by many people (most of them being much more clever than I am^^).

So what is my confusion here?

Community
  • 1
Korchkidu
  • 317

2 Answers2

4

Your statement and the one in Knut's book are equivalent. The latter is also known as complete induction. The difference is in the inductive hypothesis: while usually you assume that $P(n)$ is true to prove that $P(n+1)$ is true, complete induction tells you that you can assume more, i.e. that $P(m)$ is true for all $m\leq n$ to prove that $P(n+1)$ is true.

To see the equivalence, simply let $Q(n)$ be the property "$P(m)$ holds for all $0\leq m \leq n$". Then by "usual" induction if $Q(n+1)$ holds when we assume that $Q(n)$ does, then $Q(n)$ holds $\forall n\in \Bbb N$.

Let's examine the example @Korchkidu provided in the comments:

Given $a\in \Bbb N$, let $P_a(n)$ be the property "$a^n=1$", and let $Q_a(n)$ be the property "$a^m=1$ for all $0\leq m \leq n$". We wish to use the fact that $a^n=a^{n-m}a^m$ for every $0\leq m\leq n$ to prove that $P_a(n)$ holds for every $n\in\Bbb N$. Observe, though, that to construct an inductive argument we actually need to use $0<m<n$, since otherwise we have the identities $a^n=a^na^0$ and $a^n=a^0a^n$.

  • By usual induction we would prove a base case and then prove that $P_a(n+1)$ holds if $P_a(n)$ does. Then by our previous remark $n=0$ doesn't actually provide a useful base case. So we need to prove $P_a(1)$, too, before we use the inductive hypothesis.

  • Similarly, to prove $Q_a(n+1)$ by assuming $Q_a(n)$, by the same remark we need to prove the base case $Q_a(1)$.

A.P.
  • 9,728
  • Yes, but in complete induction, should you not prove P(1)...P(n) first? – Korchkidu Mar 15 '13 at 10:11
  • @Korchkidu No, you assume that by hypothesis. – A.P. Mar 15 '13 at 10:15
  • $P(1)$, your initial hypothesis, is an instance of $P(1), ..., P(n)$ where $n=1$. – Jean-Claude Arbaut Mar 15 '13 at 10:50
  • @arbautjc Sure. Edited to reflect your comment. – A.P. Mar 15 '13 at 10:57
  • @A.P. It was just for Korchkidu to make it clearer ;-) – Jean-Claude Arbaut Mar 15 '13 at 11:00
  • So what's wrong in: P(n): for all a, a^(n-1)=1. P(1): a^0, OK. Suppose P(1)..P(n) OK. P(n+1): a^((n+1)-1) = a^(n-1) x a^(1) = 1. – Korchkidu Mar 15 '13 at 11:09
  • If $a=1$, there is nothing wrong. If $a \neq 1$, please tell us how you can write $a^{n-1} \cdot a^1 = 1$ ? – Jean-Claude Arbaut Mar 15 '13 at 11:32
  • @Korchkidu I see what you mean now. I just showed you how to prove that $P(n+1)$ holds if $P(m)$ does for every $0\leq m \leq n$. To prove that it is actually true, indeed you have to show that your hypothesis is true. – A.P. Mar 15 '13 at 12:08
  • @arbautjc: because we supposed that P(1)..P(n) is true. In particular, P(2) implies that a^1 = 1 and P(n) implies that a^(n-1) = 1. – Korchkidu Mar 15 '13 at 12:26
  • @A.P.: so, I also have to prove P(1)..P(n) while proving P(n+1) => P(n). Right? – Korchkidu Mar 15 '13 at 12:35
  • But you only proved P(1), and your n -> n+1 step is wrong. Thus you have nothing except P(1). – Jean-Claude Arbaut Mar 15 '13 at 12:44
  • @arbautjc: no, based on my hypothesis that P(1)..P(n) is true, P(n+1) is also true. My hypothesis is wrong. That's why I believe that we should also prove P(1)..P(n). – Korchkidu Mar 15 '13 at 12:53
  • But to use the fact that $n \geq 2$ in your hypothesis, you must have already proved it in a case where $n \geq 2$. But you have only $P(1)$. It's the usual case where one asks too much from the recursion hypothesis. – Jean-Claude Arbaut Mar 15 '13 at 12:57
  • @arbautjc: this is exactly what I asked in my question actually. To use such an hypothesis P(1)..P(n) is true, I must prove it first. Right? And why n > 1 ? n > 0 is sufficient right? – Korchkidu Mar 15 '13 at 13:02
  • You must not prove P(1)...P(n) in the general case to use recursion, it's recursion that will give you that. But you must prove an initial case, $n_0$ (which $n_0$, that depends), and you must prove $(n \geq n_0 \wedge P(1)...P(n)) \Rightarrow P(n+1)$. If, in this step, you use the fact that $n > n_0$, you are obviously wrong, becasue you have not that in your recursion initialization. – Jean-Claude Arbaut Mar 15 '13 at 13:59
  • let us continue this discussion in chat – Korchkidu Mar 15 '13 at 14:31
  • Thanks a lot for all the explanations! It is much clearer now. – Korchkidu Mar 15 '13 at 15:40
2

I think that he presents strong or complete induction, whereas your definition is that of regular (weak?) induction.

Sam
  • 1,136