Sunday, December 25, 2016

discrete mathematics - 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?


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 \leq i \leq b $, $P(i)$ is true," so that the interval of integers was more clear.


No comments:

Post a Comment

analysis - Injection, making bijection

I have injection $f \colon A \rightarrow B$ and I want to get bijection. Can I just resting codomain to $f(A)$? I know that every function i...