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 ∀i∈Z((a≤i≤k)∧P(i)) vacuously true, but can't grasp why replacing k≥b (and hence k≥a since b≥a) to k≥a−1 proves the basis step implicitly. Why is it?
Answer
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≤i≤b, P(i) is true," so that the interval of integers was more clear.
No comments:
Post a Comment