Strong Induction: Choosing values for the ranges[Q]

Question

In the following example, why is the highlight value not $k >= 0$ ?

Answer 1

In principal, we could certainly carry out induction by

1. Showing that the statement $P(0)$ is true (base case)

2. Assuming that the statement holds for $P(k)$ (induction hypothesis)

3. Show that the statement holds for $P(k+1)$, i.e., $P(k) \implies P(k+1)$. (induction step)

However, I think that the author chose to show $P(0)$ and $P(1)$ and start with induction on $k \geq 1$ in order to highlight what the behavior is, and since there can sometimes be pathological issues with taking the base case to be too small--see Polya's proof that all horses are the same color for what can happen if the base case is improperly established for induction. Additionally, note that the proof for $s_{k+1}$ references both $s_k$ and $s_{k-1}$. Thus, in order for the proof to hold for $s_2$, we first need that it is true for $s_1$ and $s_0$.