Give examples to illustrate the proof of Theorem 1.Theorem

Chapter 5, Problem 28E

(choose chapter or problem)

Problem 28E

Give examples to illustrate the proof of Theorem 1.

Theorem 1

Existence and Uniqueness of Binary Integer Representations

Given any positive integer n, n has a unique representation in the form

where r is a nonnegative integer, cr =1, and cj =1 or 0 for all j =0, 1, 2, …,r –1.

Proof:

We give separate proofs by strong mathematical induction to show first the existence and second the uniqueness of the binary representation.

Existence (proof by strong mathematical induction): Let the property P(n) be the equation

where r is a nonnegative integer, cr =1, and cj =1 or 0 for all j =0, 1, 2,…, r –1.

Show that P(1) is true:

Let r = 0 and c0 = 1. Then 1 = cr•2r , and so n = 1 can be written in the required form.

Show that for all integers k≥ 1, if P(i) is true for all integers i from 1 through k,

then P(k+1) is also true:

Let k be an integer with k ≥ 1. Suppose that for all integers i from 1 through k,

where r is a nonnegative integer, cr =1, and cj =1 or 0 for all j =0, 1, 2,…, r –1. We must show that k + 1 can be written as a sum of powers of 2 in the required form.

Case 1 (k + 1 is even): In this case (k + 1)/2 is an integer, and by inductive hypothesis,

since 1 ≤ (k + 1)/2 ≤ k, then,

where r is a nonnegative integer, cr =1, and cj =1 or 0 for all j =0, 1, 2,…, r –1. Multiplying both sides of the equation by 2 gives

which is a sum of powers of 2 of the required form.

Case 2 (k + 1 is odd): In this case k/2 is an integer, and by inductive hypothesis,

since 1 ≤ k/2 ≤ k, then

where r is a nonnegative integer,cr =1, and cj =1 or 0 for all j =0, 1, 2,…, r–1.

Multiplying both sides of the equation by 2 and adding 1 gives

which is also a sum of powers of 2 of the required form.

The preceding arguments show that regardless of whether k + 1 is even or odd, k + 1 has a representation of the required form. [Or, in other words, P(k + 1) is true as was

to be shown.]

[Since we have proved the basis step and the inductive step of the strong mathematical

induction, the existence half of the theorem is true.]

Uniqueness: To prove uniqueness, suppose that there is an integer n with two different representations as a sum of nonnegative integer powers of 2. Equating the two representations and canceling all identical terms gives

where r and s are nonnegative integers, and each ci and each di equal 0 or 1.Without loss of generality, we may assume that r < s. But by the formula for the sum of a geometric sequence (Theorem 2) and because r<s,

Thus

which contradicts equation (5.4.1). Hence the supposition is false, so any integer n has only one representation as a sum of nonnegative integer powers of 2.

Theorem

Sum of a Geometric Sequence

For any real number r except 1, and any integer n ≥ 0,

Proof (by mathematical induction):

Suppose r is a particular but arbitrarily chosen real number that is not equal to 1, and let the property P(n) be the equation

We must show that P(n) is true for all integers n ≥ 0. We do this by mathematicalinduction on n.

Show that P(0) is true:

To establish P(0), we must show that

The left-hand side of this equation is r0 = 1 and the right-hand side is

also because r1 = r and r = 1. Hence P(0) is true.

Show that for all integers k≥ 0, if P(k) is true then P(k+1) is also true:

[Suppose that P(k) is true for a particular but arbitrarily chosen integer k ≥ 0. That is:]

Let k be any integer with k ≥ 0, and suppose that

[We must show that P(k + 1) is true. That is:] We must show that

or, equivalently, that

[We will show that the left-hand side of P(k + 1) equals the right-hand side.]

The left-hand side of P(k + 1) is

which is the right-hand side of P(k + 1) [as was to be shown.]

[Since we have proved the basis step and the inductive step, we conclude that the theorem

is true.]