TAOCP 1.2.1 Exercise 1
To prove a statement $P(n)$ for all nonnegative integers $n = 0, 1, 2, \ldots$, we modify the usual induction procedure by changing the base case.
Section 1.2.1: Mathematical Induction
Exercise 1. [05] Explain how to modify the idea of proof by mathematical induction, in case we want to prove some statement $P(n)$ for all nonnegative integers, that is, for $n = 0$, $1$, $2$, $\ldots$ instead of for $n = 1, 2, 3, \ldots,$.
Verified: yes
Solve time: 31s
To prove a statement $P(n)$ for all nonnegative integers $n = 0, 1, 2, \ldots$, we modify the usual induction procedure by changing the base case. Instead of proving $P(1)$, we first prove $P(0)$. Then we proceed as before: assume that $P(0), P(1), \ldots, P(n)$ are all true for some nonnegative integer $n$, and deduce that $P(n + 1)$ is true. Algorithm I from Section 1.2.1 can be applied with this new base case $k \leftarrow 0$, and all subsequent steps remain identical. This establishes $P(n)$ for all $n \ge 0$ by mathematical induction.
This completes the proof.
∎