Exercises from Section 1.2.1

1. [05] Explain how to modify the idea of a proof by mathematical induction, in case we want to prove some statement

P (n)

for all nonnegative integers—that is, for

n = 0, 1, 2, \dots

instead of for

n = 1, 2, 3, \dots

We may modify the idea of a proof by mathematical induction in the case we want to prove some statement for all nonnegative integers as follows:

Let $P (n)$ be some statement about the integer $n$ . In order to prove that $P (n)$ is true for all nonnegative integers $n$ :

a.: Give a proof that $P (0)$ is true.
b.: Give a proof that “if all of $P (0), P (1), \dots, P (n)$ are true, then $P (n + 1)$ is also true”; this proof should be valid for any nonnegative integer $n$ .

▸

2. [15] There must be something wrong with the following proof. What is it? “Theorem. Let

a

be any positive number. For all positive integers

n

we have

a^{n - 1} = 1

. Proof. If

n = 1

a^{n - 1} = a^{1 - 1} = a^{0} = 1

. And by induction, assuming that the theorem is true for

1, 2, \dots, n

, we have

The proof, in particular during the induction step, makes an assumption about $a^{(n - 1) - 1}$ , instead of $a^{n - 1}$ , requiring the case for both $n = 1$ and $n = 2$ to be proved, which has not been done. Otherwise, if $a^{(n - 1) - 1} = a^{(1 - 1) - 1} = a^{- 1} = 1$ , the theorem would indeed be true.

3. [18] The following proof by induction seems correct, but for some reason the equation for

n = 6

gives

\frac{1}{2} + \frac{1}{6} + \frac{1}{12} + \frac{1}{20} + \frac{1}{30} = \frac{5}{6}

on the left-hand side, and

\frac{3}{2} - \frac{1}{6} = \frac{4}{3}

on the right-hand side. Can you ﬁnd a mistake? “Theorem.

Proof. We use induction on

n

. For

n = 1

, clearly

3 ∕ 2 - 1 ∕ n = 1 ∕ (1 \times 2)

; and, assuming that the theorem is true for

n

The proof, in particular during the base step for $n = 1$ , fails to prove that $\frac{3}{2} - \frac{1}{1} = \frac{1}{(1 - 1) \times 1}$ or that $\frac{3}{2} - \frac{1}{1} = 0$ , the former which is in fact undeﬁned.

4. [20] Prove that, in addition to Eq. (3), Fibonacci numbers satisfy

F_{n} \geq ϕ^{n - 2}

Proposition. For $ϕ = \frac{1 + \sqrt{5}}{2}$ and all positive integers $n$ , Fibonacci numbers satisify $F_{n} \geq ϕ^{n - 2}$ .

Proof. If $n = 1$ , $F_{n} = 1 \geq \frac{2}{3} = \frac{2}{1 + 2} > \frac{2}{1 + \sqrt{5}} = \frac{1}{ϕ} = ϕ^{- 1} = ϕ^{1 - 2} = ϕ^{n - 2}$ .

Then, assuming $F_{n} \geq ϕ^{n - 2}$ for all positive integers $n$ , we must show that $F_{n + 1} \geq ϕ^{(n + 1) - 2} = ϕ^{n - 1}$ . If $n = 2$ , $F_{n} = 1 \geq ϕ^{0} = ϕ^{2 - 2} = ϕ^{n - 2}$ . Otherwise, if $n > 2$ :

\begin{array}{l} F_{n + 1} & = F_{n} + F_{n - 1} \\ \geq ϕ^{n - 2} + ϕ^{n - 3} \\ = \frac{ϕ^{n + 1} + ϕ^{n}}{ϕ^{3}} \\ = ϕ^{n - 1} (\frac{ϕ + 1}{ϕ^{2}}) \\ = ϕ^{n - 1} (\frac{1}{ϕ} + \frac{1}{ϕ^{2}}) \\ > ϕ^{n - 1} (2) & since 1 ∕ ϕ < 1 \\ > ϕ^{n - 1} \end{array}

which we needed to show. □

5. [21] A prime number is an integer

> 1

that has no exact divisors other than

1

and itself. Using this deﬁnition and mathematical induction, prove that every integer

> 1

may be written as a product of one or more prime numbers. (A prime number is considered to be the “product” of a single prime, namely itself.)

Proposition. Every integer $n > 1$ may be written as a product of one or more prime numbers.

Proof. If $n = 2$ , then $n$ is prime.

Then, assuming every integer $n > 1$ may be written as a product of one or more prime numbers, we must show that $n + 1$ may be as well. In the case that $n + 1$ is prime, this is trivially true. Otherwise, in the case that $n + 1$ is composite, there must exist two factors $p$ and $q$ such that $n + 1 = p q$ where $1 < p, q < n + 1$ ; but by hypothesis, $p$ and $q$ are the products of one or more prime numbers, and so their product is such, as we needed to show. □

6. [20] Prove that if Eqs. (6) hold just before step E4, they hold afterwards also.

Proposition. In Algorithm E, given $a m + b n = d \land a^{'} m + b^{'} n = c = q d + r$ prior to step E4, afterwards we have $a m + b n = d \land a^{'} m + b^{'} n = c$ .

Proof.

Assume $a m + b n = d \land a^{'} m + b^{'} n = c = q d + r$ .

But:

\begin{array}{l} a m + b n = d \land a^{'} m + b^{'} n = c = q d + r iﬀ & a m + b n = d \land a^{'} m + b^{'} n = q d + r \\ iﬀ & a m + b n = d \land a^{'} m + b^{'} n = q (a m + b n) + r \\ iﬀ & a m + b n = d \land a^{'} m + b^{'} n = q a m + q b n + r \\ iﬀ & a m + b n = d \land a^{'} m + b^{'} n - q a m - q b n = r \\ iﬀ & a m + b n = d \land (a^{'} - q a) m + (b^{'} - q b) n = r \\ iﬀ & (a^{'} - q a) m + (b^{'} - q b) n = r \land a m + b n = d \end{array}

Then, given $(a^{'} - q a) m + (b^{'} - q b) n = r \land a m + b n = d$ , in executing step E4:

\begin{array}{l} c & \leftarrow d & (a^{'} - q a) m + (b^{'} - q b) n = r \land a m + b n = c \\ d & \leftarrow r & (a^{'} - q a) m + (b^{'} - q b) n = d \land a m + b n = c \\ t & \leftarrow a^{'} & (t - q a) m + (b^{'} - q b) n = d \land a m + b n = c \\ a^{'} & \leftarrow a & (t - q a) m + (b^{'} - q b) n = d \land a^{'} m + b n = c \\ a & \leftarrow t - q a & a m + (b^{'} - q b) n = d \land a^{'} m + b n = c \\ t & \leftarrow b^{'} & a m + (t - q b) n = d \land a^{'} m + b n = c \\ b^{'} & \leftarrow b & a m + (t - q b) n = d \land a^{'} m + b^{'} n = c \\ b & \leftarrow t - q b & a m + b n = d \land a^{'} m + b^{'} n = c \end{array}

as we needed to show. □

7. [23] Formulate and prove by induction a rule for the sums

1^{2}

2^{2} - 1^{2}

3^{2} - 2^{2} + 1^{2}

4^{2} - 3^{2} + 2^{2} - 1^{2}

5^{2} - 4^{2} + 3^{2} - 2^{2} + 1^{2}

, etc.

Proposition. Let $S_{n}$ = $1^{2}$ if $n = 1$ or $n^{2} + (- 1) S_{n - 1}$ if $n > 1$ otherwise, for all positive integers $n$ . That is, let $S_{n}$ be a sum in the sequence $1^{2}$ , $2^{2} - 1^{2}$ , $3^{2} - 2^{2} + 1^{2}$ , $4^{2} - 3^{2} + 2^{2} - 1^{2}$ , $5^{2} - 4^{2} + 3^{2} - 2^{2} + 1^{2}$ , etc. For all positive integers $n$ , $S_{n} = \sum_{1 \leq k \leq n} {(- 1)}^{n - k} k^{2}$ .

Proof. For $n = 1$ , we have $S_{n} = 1^{2} = {(- 1)}^{0} 1^{2} = \sum_{1 \leq k \leq 1} {(- 1)}^{1 - k} k^{2} = \sum_{1 \leq k \leq n} {(- 1)}^{n - k} k^{2}$ .

Then, assuming for all positive integers $n \geq 1$ if $S_{n} = \sum_{1 \leq k \leq n} {(- 1)}^{n - k} k^{2}$ , we must prove that $S_{n + 1} = \sum_{1 \leq k \leq n + 1} {(- 1)}^{(n + 1) - k} k^{2}$ .

But:

\begin{array}{l} S_{n + 1} = & {(n + 1)}^{2} + (- 1) S_{n} \\ = & {(n + 1)}^{2} + (- 1) \sum_{1 \leq k \leq n} {(- 1)}^{n - k} k^{2} \\ = & {(n + 1)}^{2} + \sum_{1 \leq k \leq n} {(- 1)}^{(n + 1) - k} k^{2} \\ = & {(- 1)}^{(n + 1) - (n + 1)} {(n + 1)}^{2} + \sum_{1 \leq k \leq n} {(- 1)}^{(n + 1) - k} k^{2} \\ = & \sum_{1 \leq k \leq n + 1} {(- 1)}^{(n + 1) - k} k^{2} \end{array}

as was to be shown.

□

▸

8. [25] (a) Prove the following theorem of Nicomachus (A.D. c. 100) by induction:

1^{3} = 1

2^{3} = 3 + 5

3^{3} = 7 + 9 + 11

4^{3} = 13 + 15 + 17 + 19

, etc. (b) Use this result to prove the remarkable formula

1^{3} + 2^{3} + \dots + n^{3} = {(1 + 2 + \dots + n)}^{2}

[Note: An attractive geometric interpretation of this forumula, suggested by Warren Lushbaugh, is shown in Fig. 5; see Math. Gagzette 49 (1965), 200. The idea is related to Nicomachus’s theorem and Fig. 3. Other “look-see” proofs can be found in books by Martin Gardner, Knotted Doughnuts (New York: Freeman, 1986), Chapter 16; J. H. Conway and R. K. Guy, The Book of Numbers (New York: Copernicus, 1996), Chapter 2.]

a.: We shall prove a theorem of Nicomachus.

Proposition. For all positive integers $n$ , $n^{3} = \sum_{1 \leq k \leq n} n^{2} - n + 2 k - 1$ .

Proof. If $n = 1$ , $n^{3} = 1^{3} = 1 = 1^{2} - 1 + 2 - 1 = \sum_{1 \leq k \leq n} n^{2} - n + 2 k - 1$ .

Then, assuming $n^{3} = \sum_{1 \leq k \leq n} n^{2} - n + 2 k - 1$ for all positive integers $n$ , we must show that ${(n + 1)}^{3} = \sum_{1 \leq k \leq n + 1} {(n + 1)}^{2} - (n + 1) + 2 k - 1$ . But:
$\begin{array}{l} {(n + 1)}^{3} & = n^{3} + 3 n^{2} + 3 n + 1 \\ = 3 n^{2} + 3 n + 1 + n^{3} \\ = 3 n^{2} + 3 n + 1 + \sum_{1 \leq k \leq n} n^{2} - n + 2 k - 1 \\ = 3 n^{2} + 3 n + 1 + n (n^{2} - n) + \sum_{1 \leq k \leq n} 2 k - 1 \\ = 3 n^{2} + 3 n + 1 + n^{3} - n^{2} + \sum_{1 \leq k \leq n} 2 k - 1 \\ = 2 n^{2} + 3 n + 1 + n^{3} + \sum_{1 \leq k \leq n} 2 k - 1 \\ = n^{3} + 2 n^{2} + 3 n + 1 + \sum_{1 \leq k \leq n} 2 k - 1 \\ = n^{3} + 2 n^{2} + n + 2 n + 1 + \sum_{1 \leq k \leq n} 2 k - 1 \\ = (n + 1) (n^{2} + n) + 2 n + 1 + \sum_{1 \leq k \leq n} 2 k - 1 \\ = (n + 1) (n^{2} + 2 n + 1 - n - 1) + 2 n + 1 + \sum_{1 \leq k \leq n} 2 k - 1 \\ = (n + 1) ({(n + 1)}^{2} - (n + 1)) + 2 (n + 1) - 1 + \sum_{1 \leq k \leq n} 2 k - 1 \\ = (n + 1) ({(n + 1)}^{2} - (n + 1)) + \sum_{1 \leq k \leq n + 1} 2 k - 1 \\ = \sum_{1 \leq k \leq n + 1} {(n + 1)}^{2} - (n + 1) + 2 k - 1 \end{array}$

as we needed to show. □
b.: We shall use the proof above to prove another formula.

Proposition. For all positive integers $n$ , $\sum_{1 \leq k \leq n} k^{3} = {(\sum_{1 \leq k \leq n} k)}^{2}$ .

Proof. We have that for all positive integers $n$ , $n^{3} = \sum_{1 \leq k \leq n} n^{2} - n + 2 k - 1$ .

First, we will show that $\sum_{1 \leq j \leq n} \sum_{1 \leq k \leq j} j^{2} - j + 2 k - 1 = \sum_{1 \leq k \leq \frac{n^{2} + n}{2}} 2 k - 1$ .
In the case that $n = 1$ :
$\begin{array}{l} \sum_{1 \leq j \leq n} \sum_{1 \leq k \leq j} j^{2} - j + 2 k - 1 & = \sum_{1 \leq j \leq 1} \sum_{1 \leq k \leq j} j^{2} - j + 2 k - 1 \\ = \sum_{1 \leq k \leq 1} 1^{2} - 1 + 2 k - 1 \\ = 1 \\ = \sum_{1 \leq k \leq 1} 2 k - 1 \\ = \sum_{1 \leq k \leq \frac{1^{2} + 1}{2}} 2 k - 1 \\ = \sum_{1 \leq k \leq \frac{n^{2} + n}{2}} 2 k - 1 \end{array}$

Then, assuming that $\sum_{1 \leq j \leq n} \sum_{1 \leq k \leq j} j^{2} - j + 2 k - 1 = \sum_{1 \leq k \leq \frac{n^{2} + n}{2}} 2 k - 1$ for all positive integers $n$ , we must ﬁrst show that $\sum_{1 \leq j \leq n + 1} \sum_{1 \leq k \leq j} j^{2} - j + 2 k - 1 = \sum_{1 \leq k \leq \frac{{(n + 1)}^{2} + n + 1}{2}} 2 k - 1$ . But:
$\begin{array}{l} \sum_{1 \leq j \leq n + 1} \sum_{1 \leq k \leq j} j^{2} - j + 2 k - 1 & = (\sum_{1 \leq j \leq n} \sum_{1 \leq k \leq j} j^{2} - j + 2 k - 1) + \sum_{1 \leq k \leq n + 1} {(n + 1)}^{2} - (n + 1) + 2 k - 1 \\ = (\sum_{1 \leq k \leq \frac{n^{2} + n}{2}} 2 k - 1) + \sum_{1 \leq k \leq n + 1} {(n + 1)}^{2} - (n + 1) + 2 k - 1 \\ = (\sum_{1 \leq k \leq \frac{n^{2} + n}{2}} 2 k - 1) + \sum_{1 \leq \frac{k + 1 - {(n + 1)}^{2} + (n + 1)}{2} \leq n + 1} k \\ = (\sum_{1 \leq k \leq \frac{n^{2} + n}{2}} 2 k - 1) + \sum_{\frac{n^{2} + n}{2} + 1 \leq \frac{k + 1}{2} \leq \frac{{(n + 1)}^{2} + (n + 1)}{2}} k \\ = (\sum_{1 \leq k \leq \frac{n^{2} + n}{2}} 2 k - 1) + \sum_{\frac{n^{2} + n}{2} + 1 \leq k \leq \frac{{(n + 1)}^{2} + (n + 1)}{2}} 2 k - 1 \\ = (\sum_{1 \leq k \leq \frac{{(n + 1)}^{2} + (n + 1)}{2}} 2 k - 1) \end{array}$

as was to be shown.
Second, and ﬁnally, we note that:
$\begin{array}{l} \sum_{1 \leq k \leq n} k^{3} & = \sum_{1 \leq j \leq n} \sum_{1 \leq k \leq j} j^{2} - j + 2 k - 1 \\ = \sum_{1 \leq k \leq \frac{n^{2} + n}{2}} 2 k - 1 \\ = {(\frac{n^{2} + n}{2})}^{2} & the sum of \frac{n^{2} + n}{2} odd integers \\ = {(\frac{n (n + 1)}{2})}^{2} \\ = {(\sum_{1 \leq k \leq n} k)}^{2} \end{array}$

as we needed to show. □

9. [20] Prove by induction that if

0 < a < 1

, then

{(1 - a)}^{n} \geq 1 - n a

Proposition. For all positive integers $n$ , if $0 < a < 1$ , then ${(1 - a)}^{n} \geq 1 - n a$ .

Proof. If $n = 1$ , then ${(1 - a)}^{n} = {(1 - a)}^{1} = 1 - a = 1 - (1) a = 1 - n a$ .

Then, assuming that ${(1 - a)}^{n} \geq 1 - n a$ for all positive integers $n$ , we must show that ${(1 - a)}^{n + 1} \geq 1 - (n + 1) a$ . But:

\begin{array}{l} {(1 - a)}^{n + 1} & = (1 - a) {(1 - a)}^{n} \\ \geq (1 - a) (a - n a) \\ = 1 - n a - a + n a^{2} \\ \geq 1 - n a - a \\ = 1 - (n + 1) a \end{array}

as we needed to show. □

Proposition. For all integers $n \geq 10$ , $2^{n} > n^{3}$ .

Proof. If $n = 10$ , then $2^{n} = 2^{10} = 1024 > 1000 = 1 0^{3} = n^{3}$ .

Also note that if $n \geq 10$ , then ${(1 + \frac{1}{n})}^{3} \leq {(1 + \frac{1}{10})}^{3} < 2$ .

Then, assuming $2^{n} > n^{3}$ for all integers $n \geq 10$ , we must show that $2^{n + 1} > {(n + 1)}^{3}$ . But:

\begin{array}{l} 2^{n + 1} & = (2) 2^{n} \\ > (2) n^{3} \\ > {(1 + \frac{1}{n})}^{3} n^{3} \\ = {(n + 1)}^{3} \end{array}

as we needed to show. □

When we enumerate the ﬁrst ﬁve terms and cumulative sums of the sequence $S_{n} = \frac{{(- 1)}^{n - 1} {(2 n - 1)}^{3}}{{(2 n - 1)}^{4} + 4}$ :

$n$	$S_{n}$	$\sum_{1 \leq k \leq n} S_{k}$

1	1/5	1/5
2	-27/85	-2/17
3	125/629	3/37
4	-343/2405	-4/65
5	729/6565	5/101

we conjecture that $\sum_{1 \leq k \leq n} \frac{{(- 1)}^{k - 1} {(2 k - 1)}^{3}}{{(2 k - 1)}^{4} + 4} = \frac{{(- 1)}^{n - 1} n}{4 n^{2} + 1}$ .

Proposition. For all positive integers $n$ , $\sum_{1 \leq k \leq n} \frac{{(- 1)}^{k - 1} {(2 k - 1)}^{3}}{{(2 k - 1)}^{4} + 4} = \frac{{(- 1)}^{n - 1} n}{4 n^{2} + 1}$ .

Proof. If $n = 1$ , $\sum_{1 \leq k \leq n} \frac{{(- 1)}^{k - 1} {(2 k - 1)}^{3}}{{(2 k - 1)}^{4} + 4} = \frac{{(- 1)}^{0} {(2 - 1)}^{3}}{{(2 - 1)}^{4} + 4} = \frac{1}{5} = \frac{{(- 1)}^{0} (1)}{4 {(1)}^{2} + 1} = \frac{{(- 1)}^{n - 1} n}{4 n^{2} + 1}$ .

Then, assuming $\sum_{1 \leq k \leq n} \frac{{(- 1)}^{k - 1} {(2 k - 1)}^{3}}{{(2 k - 1)}^{4} + 4} = \frac{{(- 1)}^{n - 1} n}{4 n^{2} + 1}$ for all positive integers $n$ , we must show that $\sum_{1 \leq k \leq n + 1} \frac{{(- 1)}^{k - 1} {(2 k - 1)}^{3}}{{(2 k - 1)}^{4} + 4} = \frac{{(- 1)}^{n} (n + 1)}{4 {(n + 1)}^{2} + 1}$ . But:

\begin{array}{l} \sum_{1 \leq k \leq n + 1} \frac{{(- 1)}^{k - 1} {(2 k - 1)}^{3}}{{(2 k - 1)}^{4} + 4} & = (\sum_{1 \leq k \leq n} \frac{{(- 1)}^{k - 1} {(2 k - 1)}^{3}}{{(2 k - 1)}^{4} + 4}) + \frac{{(- 1)}^{n} {(2 (n + 1) - 1)}^{3}}{{(2 (n + 1) - 1)}^{4} + 4} \\ = \frac{{(- 1)}^{n - 1} n}{4 n^{2} + 1} + \frac{{(- 1)}^{n} {(2 (n + 1) - 1)}^{3}}{{(2 (n + 1) - 1)}^{4} + 4} \\ = \frac{{(- 1)}^{n - 1} n ({(2 n + 1)}^{4} + 4) + {(- 1)}^{n} {(2 n + 1)}^{3} (4 n^{2} + 1)}{(4 n^{2} + 1) ({(2 n + 1)}^{4} + 4)} \\ = \frac{{(- 1)}^{n - 1} n ({(2 n + 1)}^{4} + 4) + {(- 1)}^{n} {(2 n + 1)}^{3} (4 n^{2} + 1)}{(4 {(n + 1)}^{2} + 1) {(4 n^{2} + 1)}^{2}} \\ = \frac{{(- 1)}^{n} - n ({(2 n + 1)}^{4} + 4) + {(- 1)}^{n} {(2 n + 1)}^{3} (4 n^{2} + 1)}{(4 {(n + 1)}^{2} + 1) {(4 n^{2} + 1)}^{2}} \\ = \frac{{(- 1)}^{n} (- n ({(2 n + 1)}^{4} + 4) + {(2 n + 1)}^{3} (4 n^{2} + 1))}{(4 {(n + 1)}^{2} + 1) {(4 n^{2} + 1)}^{2}} \\ = \frac{{(- 1)}^{n} (n + 1) {(4 n^{2} + 1)}^{2}}{(4 {(n + 1)}^{2} + 1) {(4 n^{2} + 1)}^{2}} \\ = \frac{{(- 1)}^{n} (n + 1)}{4 {(n + 1)}^{2} + 1} \end{array}

as we needed to show. □

12. [M25] Show how Algorithm E can be generalized as stated in the text so that it will accept input values of the form

u + v \sqrt{2}

, where

u

and

v

are integers, and the computations can still be done in an elementary way (that is, without using the inﬁnite decimal expansion of

\sqrt{2}

). Prove that the computation will not terminate, however, if

m = 1

and

n = \sqrt{2}

Algorithm E can be generalized to accept input values of the form $u + v \sqrt{2}$ for integers $u$ and $v$ , using repeated subtraction instead of division. The algorithm relies on the fact that $u + v \sqrt{2} = u^{'} + v^{'} \sqrt{2} \Leftrightarrow u^{'} - u = 0 \land v^{'} - v = 0$ , our test for a zero remainder; and on the fact that $(u - u^{'}) + (v - v^{'}) \sqrt{2} < 0 \Leftrightarrow (u - u^{'}) + ⌊ (v -^{'}) \sqrt{2} ⌋ < 0$ .

Algorithm F (Generalized Euclid’s algorithm). Given two numbers $m = m_{r} + m_{i} \sqrt{2}$ and $n = n_{r} + n_{i} \sqrt{2}$ with integers $m_{r}, m_{i}, n_{r}, n_{i}$ , we compute their greatest common divisor $d = d_{r} + d_{i} \sqrt{2}$ with integers $d_{r}, d_{i}$ , and we also compute two integers $a$ and $b$ such that $a m + b n = d$ .

F1a.: [Initialize.] Set $a^{'} \leftarrow b \leftarrow 1$ , $a \leftarrow b^{'} \leftarrow 0$ , $(c_{r}, c_{i}) \leftarrow (m_{r}, m_{i})$ , $(d_{r}, d_{i}) \leftarrow (n_{r}, n_{i})$ , $y \leftarrow z \leftarrow 1$ .
F1b1.: [Initialize $c = | m |$ .] Set $v \leftarrow 0$ .
F1b2.: If ${(v + 1)}^{2} \leq 2 c_{i}^{2}$ , $v \leftarrow v + 1$ , and go to step F1b2. Otherwise, if $c_{i} < 0$ , $v \leftarrow - (v + 1)$ . (Afterwards, we have $v = ⌊ c_{i} \sqrt{2} ⌋$ .)
F1b3.: If $c_{r} + v < 0$ , $y \leftarrow - 1$ , $(c_{r}, c_{i}) \leftarrow (- c_{r}, - c_{i})$ .
F1c1.: [Initialize $d = | n |$ .] Set $v \leftarrow 0$ .
F1c2.: If ${(v + 1)}^{2} \leq 2 d_{i}^{2}$ , $v \leftarrow v + 1$ , and go to step F1c2. Otherwise, if $d_{i} < 0$ , $v \leftarrow - (v + 1)$ . (Afterwards, we have $v = ⌊ d_{i} \sqrt{2} ⌋$ .)
F1c3.: If $d_{r} + v < 0$ , $z \leftarrow - 1$ , $(d_{r}, d_{i}) \leftarrow (- d_{r}, - d_{i})$ .
F2a.: [Divide.] Let $q \leftarrow 0$ , $(e_{r}, e_{i}) \leftarrow (c_{r}, c_{i})$ .
F2b1.: Let $(e_{r}, e_{i}) \leftarrow (e_{r} - d_{r}, e_{i} - d_{i})$ and $v \leftarrow 0$ .
F2b2.: If ${(v + 1)}^{2} \leq 2 e_{i}^{2}$ , $v \leftarrow v + 1$ and go to step F2b2. Otherwise, if $e_{i} < 0$ , $v \leftarrow - (v + 1)$ . (Afterwards, we have $v = ⌊ e_{i} \sqrt{2} ⌋$ .)
F2c.: If $e_{r} + v \geq$ , $q \leftarrow q + 1$ and go to step F2b1.
F2d.: Let $(r_{r}, r_{i}) \leftarrow (c_{r} - q d_{r}, c_{i} - q d_{i})$ . (We have $c_{r} + c_{i} \sqrt{2} = q d + r_{r} + r_{i} \sqrt{2}$ and $0 \leq r_{r} + r_{i} \sqrt{2} < d$ .)
F3.: [Remainder zero?] If $(r_{r}, r_{i}) = (0, 0)$ , let $a \leftarrow y a$ , $b \leftarrow z b$ and the algorithm terminates; we have in this case $a m + b n = d$ as desired.
F4.: [Recycle.] Set $(c_{r}, c_{i}) \leftarrow (d_{r}, d_{i})$ , $(d_{r}, d_{i}) \leftarrow (r_{r}, r_{i})$ , $t \leftarrow a^{'}, a^{'} \leftarrow a, a \leftarrow t - q a$ , $t \leftarrow b^{'}, b^{'} \leftarrow b, b \leftarrow t - q b$ , and go back to F2a. $■$

Unfortunately, Algorithm F will not terminate given inputs $m = 1, n = \sqrt{2}$ . If it did terminate, we would have $r_{r} + r_{i} \sqrt{2} = 0 = c_{r} + c_{i} \sqrt{2} - q (d_{r} + d_{i} \sqrt{2}) = (c_{r} - q d_{r}) + (c_{i} - q d_{i} \sqrt{2})$ , or equivalently, $\sqrt{2} = \frac{q d_{r} - c_{r}}{c_{i} - q d_{i}}$ ; that is, we would ﬁnd $\sqrt{2}$ to be rational, which cannot be. We can be assured that $c_{i} \neq q d_{i}$ in this case, since $1 \neq q \sqrt{2}$ for any rational $q$ . Hence, the algorithm will not terminate.

________________________________________________________________________________

Note: ... For further information, see “quadratic Euclidean domains” in number theory textbooks.

▸

13. [M23] Extend Algorithm E by adding a new variable

T

and adding the operation “

T \leftarrow T + 1

” at the beginning of each step. (Thus,

T

is like a clock, counting the number of steps executed.) Assume that

T

is initially zero, so that assertion

A 1

in Fig. 4 becomes “

m > 0

n > 0

T = 0

.” The additional condition “

T = 1

” should similarly be appended to

A 2

. Show how to append additional conditions to the assertions in such a way that any one of

A 1, A 2, \dots, A 6

implies

T \leq 3 n

, and such that the inductive proof can still be carried out. (Hence the computation must terminate in at most

3 n

steps.)

Initially, we are given the following algorithm with various assertions.

Algorithm E (Extended Euclid’s algorithm). Given two positive integers $m$ and $n$ , we compute their greatest common divisor $d$ , and we also compute two not-necessarily-positive integers $a$ and $b$ such that $a m + b n = d$ .

A1.: [Precondition.] $m > 0$ , $n > 0$ .
E1.: [Initialize.] Set $a^{'} \leftarrow b \leftarrow 1$ , $a \leftarrow b^{'} \leftarrow 0$ , $c \leftarrow m$ , $d \leftarrow n$ .
A2.: [E1 postcondition.] $c = m > 0$ , $d = n > 0$ , $a = b^{'} = 0$ , $a^{'} = b = 1$ .
A6.: [E4 postcondition.] $a m + b n = d$ , $a^{'} m + b^{'} n = c$ , $d > 0$ , $\gcd (c, d) = \gcd (m, n)$ .
E2.: [Divide.] Let $q$ and $r$ be the quotient and remainder, respectively, of $c$ divided by $d$ . (We have $c = q d + r$ and $0 \leq r < d$ .)
A3.: [E2 postcondition.] $a m + b n = d$ , $a^{'} m + b^{'} n = c = q d + r$ , $0 \leq r < d$ , $\gcd (c, d) = \gcd (m, n)$ .
E3.: [Remainder zero?] If $r = 0$ , the algorithm terminates; we have in this case $a m + b n = d$ as desired.
A4.: [E3 postcondition, $r = 0$ .] $a m + b n = d = \gcd (m, n)$ .
A5.: [E3 postcondition, $r \neq 0$ .] $a m + b n = d$ , $a^{'} m + b^{'} n = c = q d + r$ , $0 < r < d$ , $\gcd (c, d) = \gcd (m, n)$ .
E4.: [Recycle.] Set $c \leftarrow d$ , $d \leftarrow r$ , $t \leftarrow a^{'}$ , $a^{'} \leftarrow a$ , $a \leftarrow t - q a$ , $t \leftarrow b^{'}$ , $b^{'} \leftarrow b$ , $b \leftarrow t - q b$ , and go back to E2. $■$

We can augment this with a step variable $T$ to show that $T \leq 3 n$ .

Algorithm G (Extended Euclid’s algorithm with steps). Given two positive integers $m$ and $n$ , we compute their greatest common divisor $d$ , and we also compute two not-necessarily-positive integers $a$ and $b$ such that $a m + b n = d$ , as well as steps $T$ to show that $T \leq 3 n$ .

G0.: [Initialze steps.] $T \leftarrow 0$ .
B1.: [Precondition, G0 postcondition.] $m > 0$ , $n > 0$ , $T = 0$ .
G1.: [Initialize.] Set $a^{'} \leftarrow b \leftarrow 1$ , $a \leftarrow b^{'} \leftarrow 0$ , $c \leftarrow m$ , $d \leftarrow n$ , $T \leftarrow T + 1$ .
B2.: [G1 postcondition.] $c = m > 0$ , $d = n > 0$ , $a = b^{'} = 0$ , $a^{'} = b = 1$ , $T = 1$ .
B6.: [G4 postcondition.] $a m + b n = d$ , $a^{'} m + b^{'} n = c$ , $d > 0$ , $\gcd (c, d) = \gcd (m, n)$ , $T \leq 3 (n - d) + 1$ .
G2.: [Divide.] Let $q$ and $r$ be the quotient and remainder, respectively, of $c$ divided by $d$ . Also set $T \leftarrow T + 1$ . (We have $c = q d + r$ and $0 \leq r < d$ .)
B3.: [G2 postcondition.] $a m + b n = d$ , $a^{'} m + b^{'} n = c = q d + r$ , $0 \leq r < d$ , $\gcd (c, d) = \gcd (m, n)$ , $T \leq 3 (n - d) + 2$ .
G3.: [Remainder zero?] Set $T \leftarrow T + 1$ . If $r = 0$ , the algorithm terminates; we have in this case $a m + b n = d$ and $T \leq 3 n$ as desired.
B4.: [G3 postcondition, $r = 0$ .] $a m + b n = d = \gcd (m, n)$ , $d > 0$ , $T \leq 3 (n - d) + 3$ .
B5.: [G3 postcondition, $r \neq 0$ .] $a m + b n = d$ , $a^{'} m + b^{'} n = c = q d + r$ , $0 < r < d$ , $\gcd (c, d) = \gcd (m, n)$ , $d > 0$ , $T \leq 3 (n - d) + 3$ .
G4.: [Recycle.] Set $c \leftarrow d$ , $d \leftarrow r$ , $t \leftarrow a^{'}$ , $a^{'} \leftarrow a$ , $a \leftarrow t - q a$ , $t \leftarrow b^{'}$ , $b^{'} \leftarrow b$ , $b \leftarrow t - q b$ , $T \leftarrow T + 1$ , and go back to G2. $■$

The new assertions may be derived as shown below, given $n > 0$ .

Summary		Precondition	Step		Postcondition

{}G0 {B1}		{}	$T \leftarrow 0$		{ $T = 0$ }
{B1}G1 {B2}		{ $T = 0$ }
	$\Rightarrow$	{ $T + 1 = 1}$	$T \leftarrow T + 1$		{ $T = 1$ }
{B2}G2 {B3}		{ $n = d \land T = 1$ }
	$\Rightarrow$	{ $T \leq 3 (n - d) + 1$ }
	$\Rightarrow$	{ $T + 1 \leq 3 (n - d) + 2$ }	$T \leftarrow T + 1$		{ $T \leq 3 (n - d) + 2$ }
{B3}G3 {B4}		{ $d > 0 \land T \leq 3 (n - d) + 2$ }
	$\Rightarrow$	{ $d > 0 \land T + 1 \leq 3 (n - d) + 3$ }	$T \leftarrow T + 1$		{ $d > 0 \land T \leq 3 (n - d) + 3$ }
				$\Rightarrow$	{ $T \leq 3 n$ }
{B3}G3 {B5}		{ $d > 0 \land T \leq 3 (n - d) + 2$ }
	$\Rightarrow$	{ $d > 0 \land T + 1 \leq 3 (n - d) + 3$ }	$T \leftarrow T + 1$		{ $d > 0 \land T \leq 3 (n - d) + 3$ }
{B5}G4 {B6}		{ $d > 0 \land T \leq 3 (n - d) + 3$ }
	$\Rightarrow$	{ $T \leq 3 (n - d)$ }
	$\Rightarrow$	{ $T + 1 \leq 3 (n - d) + 1$ }	$T \leftarrow T + 1$		{ $T \leq 3 (n - d) + 1$ }
{B6}G2 {B3}		{ $T \leq 3 (n - d) + 1$ }
	$\Rightarrow$	{ $T + 1 \leq 3 (n - d) + 2$ }	$T \leftarrow T + 1$		{ $T \leq 3 (n - d) + 2$ }

14. [50] (R. W. Floyd.) Prepare a computer program that accepts, as input, programs in some programming language together with optional assertions, and that attempts to ﬁll in the remaining assertions necessary to make a proof that the computer program is valid. (For example, strive to get a program that is able to prove the validity of Algorithm E, given only assertions

A 1

A 4

, and

A 6

. See the papers by R. W. Floyd and J. C. King in the IFIP Congress proceedings, 1971, for further discussion.)

▸

15. [HM28] (Generalized induction.) The text shows how to prove statements

P (n)

that depend on a single integer

n

, but it does not describe how to prove statements

P (m, n)

depending on two integers. In these circumstances a proof is often given by some sort of “double induction,” which frequently seems confusing. Actually, there is an important principle more general than simple induction that applies not only to this case but also to situations in which statements are to be proved about uncoutnable sets—for example,

P (x)

for all real

x

. This general principle is called well-ordering.

Let “

≺

” be a relation on a set

S

, satisifying the following properties:

This relation is said to be a well-ordering of

S

. For example, it is clear that the positive integers are well-ordered by the ordinary “less than” relation,

<

[Notes: Part (g) is the generalization of simple induction that was promised; in the case

S =

positive integers, it is just the simple case of mathematical induction treated in the text. In that case we are asked to prove that

P (1)

is true if

P (y)

is true for all positive integers

y < 1

; this is the same as saying we should prove

P (1)

, since

P (y)

certainly is (vacuously) true for all such

y

. Consequently, one ﬁnds that in many situations

P (1)

need not be proved using a special argument.

Part (d), in connection with part (g), gives us a powerful method of

n

-tuple induction for proving statements

P (m_{1}, \dots, m_{n})

about

n

positive integers

m_{1}, \dots, m_{n}

Part (f) has further application to computer algorithms: If we can map each state

x

of a computation into an element

f (x)

belonging to a well-ordered set

S

, in such a way that every step of the computation takes a state

x

intoa state

y

with

f (y) ≺ f (x)

, then the algorithm must terminate. This principle generalizes the argument about strictly decreasing values of

n

, by which we proved the termination of Algorithm 1.1E.]

Answers are enumerated below.

a.

We can show that the set of all integers is not well-ordered by

<

by considering the violation of condition (iii) with the nonempty (improper) subset

ℤ

, which has no least element.

b.

We may deﬁne a well-ordering relation on the set of all integers as

x ≺ y = \{\begin{matrix} | x | = | y | & if - x = y > 0 \\ | x | < | y | & otherwise \end{matrix}

(12)

To see that $≺$ satisifes condition (i), assume $x ≺ y$ and $y ≺ z$ . We must show that $x ≺ z$ . By hypothesis, $- x = y > 0 \lor | x | < | y |$ and $- y = z > 0 \lor | y | < | z |$ .

Case I. [ $- x = y > 0$ and $- y = z > 0$ .] This case is impossible, as it requires both $y > 0$ and $y < 0$ , and so need not be considered.

Case II. [ $- x = y > 0$ and $| y | < | z |$ .] In this case, since $- x = y > 0$ , we have $| y | = y = - x = | x |$ . But $| y | = | x | < | z |$ and so $x ≺ z$ as we needed to show in this case.

Case III. [ $| x | < | y |$ and $- y = z > 0$ .] In this case, since $- y = z > 0$ , we have $| y | = - y = z = | z |$ . But $| x | < | y | = | z |$ and so $x ≺ z$ as we needed to show in this case.

Case IV. [ $| x | < | y |$ and $| y | < | z |$ .] In this case, clearly, as $<$ is transitive, $| x | < | z |$ , and so $x ≺ z$ as we needed to show in this case.

To see that $≺$ satisiﬁes condition (ii) we must show that for arbitrary $x$ and $y$ , $x ≺ y$ , $x = y$ , or $y ≺ x$ . If $x = y$ , $- x \neq y$ , $| x | ≮ | y |$ , and $| y | ≮ | x |$ ; if $- x = y > 0$ , then $| x | = | y |$ and $x ≺ y$ ; if $- y = x > 0$ , then $| y | = | x |$ and $y ≺ x$ ; otherwise, either $| x | < | y |$ or $| y | < | x |$ in which case $x ≺ y$ or $y ≺ x$ , respectively.

To see that $≺$ satisiﬁes condition (iii), we must show that any nonempty subset of $ℤ$ has a least element under $≺$ . Let $S$ be such a subset, so that $S \neq \emptyset$ and let $T = {t \in ℤ | (\forall s \in S) (t ≺ s)}$ . We must show that $S$ has a least element. In the case that $0 \in S$ , clearly $0$ is such an element. Otherwise, in the case that $0 \notin S$ , $T \neq \emptyset$ , and there must exist an element $u \in T$ such that $u + 1 \notin T$ but $u + 1 \in S$ . Clearly, $u + 1$ is the least element under $≺$ in $S$ , as we needed to show.

c.

The set of all nonnegative real numbers is not well-ordered by

<

, as condition (iii) is violated with the nonempty subset of positive reals, which has no least nonnegative real number.

d.

Lexicographic order is a well-ordering of

T_{n}

for

n > 0

To see that $≺$ satisﬁes condition (i), assume $(x_{1}, x_{2}, \dots, x_{n}) ≺ (y_{1}, y_{2}, \dots, y_{n})$ and $(y_{1}, y_{2}, \dots, y_{n}) ≺ (z_{1}, z_{2}, \dots, z_{n})$ . We must show that $(x_{1}, x_{2}, \dots, x_{n}) ≺ (z_{1}, z_{2}, \dots, z_{n})$ . For $n = 1$ , we have $(x_{1}) ≺ (y_{1})$ and $(y_{1}) ≺ (z_{1})$ . Since $S$ is well-ordered by $≺$ , $≺$ is transitive, and so $(x_{1}) ≺ (z_{1})$ . Then, assuming $(x_{1}, x_{2}, \dots, x_{k}) ≺ (y_{1}, y_{2}, \dots, y_{k}) \land (y_{1}, y_{2}, \dots, y_{k}) ≺ (z_{1}, z_{2}, \dots, z_{k}) \Rightarrow (x_{1}, x_{2}, \dots, x_{k}) ≺ (z_{1}, z_{2}, \dots, z_{k})$ for some $k \geq 1$ , we must show that $(x_{1}, x_{2}, \dots, x_{k + 1}) ≺ (y_{1}, y_{2}, \dots, y_{k + 1}) \land (y_{1}, y_{2}, \dots, y_{k + 1}) ≺ (z_{1}, z_{2}, \dots, z_{k + 1}) \Rightarrow (x_{1}, x_{2}, \dots, x_{k + 1}) ≺ (z_{1}, z_{2}, \dots, z_{k + 1})$ . But since $S$ is well-ordered by $≺$ and therefore transitive, $(x_{k + 1}) ≺ (y_{k + 1}) \land (y_{k + 1}) ≺ (z_{k + 1}) \Rightarrow (x_{k + 1}) ≺ (z_{k + 1})$ ; clearly then, with our induction hypothesis, $(x_{1}, x_{2}, \dots, x_{k + 1}) ≺ (z_{1}, z_{2}, \dots, z_{k + 1})$ .

To see that $≺$ satisiﬁes condition (ii) we must show for arbitrary $n$ that $(x_{1}, x_{2}, \dots, x_{n}) ≺ (y_{1}, y_{2}, \dots, y_{n})$ , $(x_{1}, x_{2}, \dots, x_{n}) = (y_{1}, y_{2}, \dots, y_{n})$ , or $(y_{1}, y_{2}, \dots, y_{n}) ≺ (x_{1}, x_{2}, \dots, x_{n})$ . Clearly the condition is satisﬁed for $n = 1$ since $S$ is well-ordered. Then, assuming $(x_{1}, x_{2}, \dots, x_{k}) ≺ (y_{1}, y_{2}, \dots, y_{k})$ , $(x_{1}, x_{2}, \dots, x_{k}) = (y_{1}, y_{2}, \dots, y_{k})$ , or $(y_{1}, y_{2}, \dots, y_{k}) ≺ (x_{1}, x_{2}, \dots, x_{k})$ for some $k \geq 1$ ; we must show that $(x_{1}, x_{2}, \dots, x_{k + 1}) ≺ (y_{1}, y_{2}, \dots, y_{k + 1})$ , $(x_{1}, x_{2}, \dots, x_{k + 1}) = (y_{1}, y_{2}, \dots, y_{k + 1})$ , or $(y_{1}, y_{2}, \dots, y_{k + 1}) ≺ (x_{1}, x_{2}, \dots, x_{k + 1})$ .

Case I. [ $(x_{1}, x_{2}, \dots, x_{k}) ≺ (y_{1}, y_{2}, \dots, y_{k})$ and $(x_{k + 1}) ≺ (y_{k + 1})$ .] Clearly $(x_{1}, x_{2}, \dots, x_{k + 1}) ≺ (y_{1}, y_{2}, \dots, y_{k + 1})$ .

Case II. [ $(x_{1}, x_{2}, \dots, x_{k}) = (y_{1}, y_{2}, \dots, y_{k})$ and $(x_{k + 1}) ≺ (y_{k + 1})$ .] $(x_{1}, x_{2}, \dots, x_{k + 1}) ≺ (y_{1}, y_{2}, \dots, y_{k + 1})$ by deﬁnition.

Case III. [ $(y_{1}, y_{2}, \dots, y_{k}) ≺ (x_{1}, x_{2}, \dots, x_{k})$ and $(x_{k + 1}) ≺ (y_{k + 1})$ .] In this case, we have $(y_{1}, y_{2}, \dots, y_{k + 1}) ≺ (x_{1}, x_{2}, \dots, x_{k + 1})$ .

Case IV. [ $(x_{1}, x_{2}, \dots, x_{k}) ≺ (y_{1}, y_{2}, \dots, y_{k})$ and $(x_{k + 1}) = (y_{k + 1})$ .] In this case, we have $(x_{1}, x_{2}, \dots, x_{k + 1}) ≺ (y_{1}, y_{2}, \dots, y_{k + 1})$ .

Case V. [ $(x_{1}, x_{2}, \dots, x_{k}) = (y_{1}, y_{2}, \dots, y_{k})$ and $(x_{k + 1}) = (y_{k + 1})$ .] In this case, we have $(x_{1}, x_{2}, \dots, x_{k + 1}) = (y_{1}, y_{2}, \dots, y_{k + 1})$ .

Case VI. [ $(y_{1}, y_{2}, \dots, y_{k}) ≺ (x_{1}, x_{2}, \dots, x_{k})$ and $(y_{k + 1}) = (x_{k + 1})$ .] In this case, we have $(y_{1}, y_{2}, \dots, y_{k + 1}) ≺ (x_{1}, x_{2}, \dots, x_{k + 1})$ .

Case VII. [ $(x_{1}, x_{2}, \dots, x_{k}) ≺ (y_{1}, y_{2}, \dots, y_{k})$ and $(y_{k + 1}) ≺ (x_{k + 1})$ .] In this case, we have $(x_{1}, x_{2}, \dots, x_{k + 1}) ≺ (y_{1}, y_{2}, \dots, y_{k + 1})$ .

Case VIII. [ $(x_{1}, x_{2}, \dots, x_{k}) = (y_{1}, y_{2}, \dots, y_{k})$ and $(y_{k + 1}) ≺ (x_{k + 1})$ .] In this case, we have $(y_{1}, y_{2}, \dots, y_{k + 1}) ≺ (x_{1}, x_{2}, \dots, x_{k + 1})$ .

Case IX. [ $(y_{1}, y_{2}, \dots, y_{k}) ≺ (x_{1}, x_{2}, \dots, x_{k})$ and $(y_{k + 1}) ≺ (x_{k + 1})$ .] In this case, we have $(y_{1}, y_{2}, \dots, y_{k + 1}) ≺ (x_{1}, x_{2}, \dots, x_{k + 1})$ .

To see that $≺$ satisﬁes condition (iii) we must show that for arbitrary $n$ , $T_{n}$ has a least element under $≺$ . For $n = 1$ , clearly this is true as $S$ is well-ordered under $≺$ . Then, assuming $T_{k}$ has a least element, we must show that so does $T_{k + 1}$ . But if both $T_{k}$ and $S$ have least elements, $(t_{1}, t_{2}, \dots, t_{k})$ and $(s_{1})$ respectively, then clearly $T_{k + 1}$ does too; namely, $(t_{1}, t_{2}, \dots, t_{k}, s_{1})$ .

e.

Continuing part (d), if we let

T = ⋃_{n \geq 1} T_{n}

and deﬁne

(x_{1}, x_{2}, \dots, x_{m}) ≺ (y_{1}, y_{2}, \dots, y_{n})

x_{j} = y_{j}

for

1 \leq j < k

and

x_{k} ≺ y_{k}

, for some

k \leq \min (m, n)

, or if

m < n

and

x_{j} = y_{j}

for

1 \leq j \leq m

; then

≺

is not a well-ordering of

T

, as condition (ii) can be violated. Consider

{a, b}

with

a ≺ b

. Then,

(b) ⊀ (a, b)

(b) \neq (a, b)

, and

(a, b) ⊀ (b)

f.

We need to show that

≺

is a well-ordering of

S

if and only if it satisiﬁes conditions (i) and (ii) and there is no inﬁnite sequence

x_{1}, x_{2}, x_{3}, \dots

with

x_{j + 1} ≺ x_{j}

for all

j \geq 1

. That is, we must show the equivalence of condition (iii), that

S

has a least element, and the nonexistence of an inﬁnite descending sequence

x_{j}

such that

x_{j + 1} ≺ x_{j}

for all

j \geq 1

. If

S

has a least element, then clearly, there is an

s \in S

such that for any

x \in S

x ⊀ s

unless

s = x

. Conversely, if no such sequence exists, there is some

s

such that

x ⊀ s

for all

x \in S

, and this

s

is precisely the least element of

S

g.

Let

S

be well-ordered by

≺

, and let

P (x)

be a statement about the element

x

S

. We must show that if

P (x)

can be proved under the assumption that

P (y)

is true for all

y ≺ x

, then

P (x)

is true for all

x

S

Suppose not. That is, suppose there is some $p$ such that $P (p)$ does not hold, despite the fact that for all $y ≺ x$ , $P (y) \Rightarrow P (x)$ . If $P (y)$ holds for all $y ≺ p$ , then by hypothesis, $P (p)$ holds. This is a condraction. Hence, $P (x)$ holds for all $x \in S$ .