1
$\begingroup$

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?

$\endgroup$

1 Answer 1

3
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ 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. $\endgroup$
    – super.t
    Commented Nov 4, 2019 at 7:57

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .