Solution: Prove each statement i using mathematical

Chapter 5, Problem 8E

(choose chapter or problem)

Problem 8E

Prove each statement i using mathematical induction. Do not derive them from Theorem 1 or Theorem 2.

Theorem 1

Sum of the First n Integers

For all integers n ≥ 1,

Proof (by mathematical induction):

Let the property P(n) be the equation

Show that P(1) is true:

To establish P(1), we must show that

But the left-hand side of this equation is 1 and the right-hand side is

also. Hence P(1) is true.

Show that for all integers k≥ 1, 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 ≥ 1.

That is:] Suppose that k is any integer with k ≥ 1 such 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 and the right-hand side of P(k + 1) are equal to the same quantity and thus are equal to each other.]

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

And the right-hand side of P(k + 1) is

Thus the two sides of P(k + 1) are equal to the same quantity and so they are equal to each other. Therefore the equation P(k + 1) is true [as was to be shown].

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

theorem is true.]

Theorem 2

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 mathematical induction 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.]

Exercise

For all integers n ≥ 0, 1 + 2 + 22 + … + 2n = 2n+1 –1.