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?
 A: 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: I think that he presents strong or complete induction, whereas your definition is that of regular (weak?) induction.
