# The Art of Computer Programming (2nd ed.): Mathematical Induction

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?

-

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

-
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

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

-
Yes, but in complete induction, should you not prove P(1)...P(n) first? – Korchkidu Mar 15 '13 at 10:11
@Korchkidu: No: they are your induction hypothesis, just as $P(n)$ is your induction hypothesis in the form of induction that you have in mind. – Brian M. Scott Mar 15 '13 at 10:35