Knuth algorithm on constructing a proof

Question

I'm going through mathematical induction section of Knuth's book "The Art of Computer Programming" (pg. 11). I'm having a hard time understanding Algorithm I on constructing a proof. Here is the algorithm:

I1. [Prove P(1).] Set $k \leftarrow$ 1, and, according to (a), output a proof of P(1).
I2. [$k=n?$] If $k=n$ terminate the algorithm; the required proof has been output.
I3. [Prove P(k+1)] According to (b), output a proof that "If all of P(1),..., P(K) are true, then P(k+1) is true." Also output "We have already proved P(1),...,P(k);hence P(k+1) is ture"
I4. [Increase k.] Increase $k$ by 1 and go to step I2.

Here is (a) and (b) mentioned in the algorithm from the previous induction example in the book:

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"; this proof should be valid for any positive integer n.

There is a neat little diagram in the book illustrating the algorithm.

I am why confused about why the the algorithm cycles through all $k$ until $n$. I thought when doing an induction proof you prove $P(k+1)$ once after proving the base case. Is this a simple brute force algorithm testing each k? Why does it cycle through each k?

Answer 1

Given $a)$ and $b)$ hold, the algorithm has to cycle through all $k$ up to $n$ because only two facts about $P(n)$ are known:

a) It holds for $P(1)$.

b) Given $P(k)$ holds, $P(k+1)$ also holds.

If you were to build a machine from these atomic principles, all you can do is to start at the (only known) true statement $P(1)$ and, successively, make your way through up to $n$.

Like in $P(16) = $ There is an integer larger than 16.

We start off at $P(1)$, which we already proved by means of $a)$ by noting that the community agreed on $2 > 1$. Computer says:

P(1) holds since 2 > 1.

Computer checks if $1 = 16$, which is not the case, branching into a proof for $P(2)$. Since we've already done all the work prior to designing the machine by giving a proof for $b)$, the machine simply outputs:

If all of P(1) are true, then P(2) is true.
We have already proved P(1); hence P(2) is true.

Consecutively, the counter is incremented, test for end carried out and the machine keeps going on until it reaches $k = 16$.

Admittedly, this is a no-brainer and to us it seems pointless to put any effort in designing (and maintaining) a machine that is hardly more than a counter. But if you had no chance whatsoever for reasoning, the only way for you, as a machine, to guarantee that $P(n)$ holds, is to go through every single step.