Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question

2 Answers 2

up vote 4 down vote accepted

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

share|improve this answer
    
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.

share|improve this answer
    
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

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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