I'm reading about strong mathematical induction in Susanna Epp's Discrete Mathematics, and here's the principle as it's stated in the textbook:
- P(a), P(a + 1), . . . , and P(b) are all true. (basis step)
- For any integer k ≥ b, if P(i) is true for all integers i from a through k, then P(k + 1) is true. (inductive step)
The principle is followed by the text that's confusing me:
Strictly speaking, the principle of strong mathematical induction can be written without a basis step if the inductive step is changed to “∀k ≥ a − 1, if P(i) is true for all integers i from a through k, then P(k + 1) is true.” The reason for this is that the statement “P(i ) is true for all integers i from a through k” is vacuously true for k = a−1. Hence, if the implication in the inductive step is true, then the conclusion P(a) must also be true,∗ which proves the basis step
∗If you have proved that a certain if-then statement is true and if you also know that the hypothesis is true, then the conclusion must be true.
I understand why $k = a − 1$ makes the statement $\forall i \in Z ((a \leq i \leq k) \land P(i)) $ vacuously true, but can't grasp why replacing $k \geq b$ (and hence $k \geq a$ since $b \geq a$) to $k \geq a-1$ proves the basis step implicitly. Why is it?
Because the statements $ P(a), ..., P(a-1) $ are all true, since there are no statements in this list. The author is using a somewhat confusing but common convention with ellipses: when you list $ firstElement ... lastElement $ where $lastElement$ precedes $firstElement$, you interpret that as an empty list. I will add, the author should have written the basis step as "for all $i$ with $a \leq i \leq b $, $P(i)$ is true," so that the interval of integers was more clear.