# Strong mathematical induction without basis step

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:

1. P(a), P(a + 1), . . . , and P(b) are all true. (basis step)
2. 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.

• okay I think I get it. P(a) is true as the conclusion of the implication because the hypothesis P(a-1) is true by default and we'll yet show that the implication is true. The conclusion of a true implication with a true hypothesis is true. Now that we know that P(a) is true, P(a+1) will be also true for the same reasons and so the inductive step "for all 𝑖 with 𝑎≤𝑖≤𝑏, 𝑃(𝑖) is true" is proven. So k=a-1 is only needed as a hypothesis that we know is true. Commented Nov 4, 2019 at 7:57