Chapter 5.4, Problem 33ES

Prove that if a statement can be proved by strong mathematical induction, then it can he proved by ordinary mathematical induction. To do this, let P(n) be a property that is defined for each integer n, and suppose the following two statements are true:

1. $P\left(a\right),P\left(a+1\right),P\left(a+2\right),\mathrm{...},P\left(b\right)$ .

2. For any integer $k\ge b$ , if P(i) is true for each integer i from a through k, then $P\left(k+1\right)$ is true. The principle of strong mathematical induction would allow us to conclude immediately that P(n) is true for every integer $n\ge a$ . Can we reach the same conclusion using the principle of ordinary mathematical induction? Yes! To see this, let Q(n) be the property P(j) is true for each integer j with $a\le j\le n$ .

Then use ordinary mathematical induction to show that Q(n) is true for every integer $n\ge b$ . That is, prove:

1. Q(b)is true.
2. For each integer $k\ge b$ , if Q(k) is true then $Q\left(k+1\right)$ is true.