Wednesday, 27 April 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=a1 makes the statement iZ((aik)P(i)) vacuously true, but can't grasp why replacing kb (and hence ka since ba) to ka1 proves the basis step implicitly. Why is it?


Answer



Because the statements P(a),...,P(a1) 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 aib, P(i) is true," so that the interval of integers was more clear.


No comments:

Post a Comment

real analysis - How to find limhrightarrow0fracsin(ha)h

How to find limh0sin(ha)h without lhopital rule? I know when I use lhopital I easy get $$ \lim_{h\rightarrow 0}...