Discrete Mathematics for Computer Science

Mathematical Induction 55

does not look like a geometric series, it is easy to transform this finite geometric series into

a more familiar looking expression:

20

E 3.2i = 3.32+3.64+...+3.220

i=5

= 96.1 +96.2+.-. +96.215

15

= 196.2/

i=O

A very useful feature of a geometric series is that we can find a closed form for its sum.

Here, we focus on the sum of a finite geometric series. The sum of an infinite geometric

series is usually studied in a calculus course, since the limiting process is needed. Although

it seems to be unrelated at first, we will begin by proving that for any n E N, 1 - xn+^1 has

1 - x as a factor. After proving this by induction, we will apply the result to summing the

finite geometric series.

Theorem 3. For any natural number n and for any real number x, prove that

(1 - x) (I + x + X2 +''". + Xn) = I - xn+lI

Solution. This result is just a familiar factoring rule. The ellipses usually suggest that a

proof by induction is needed. Fix an arbitrary x E R. Let no = 0 and

T"={n EN:foranyx ER,(I -x)(±+x+x^2 +x^3 +...+xn)= -xn+^1 I

(Base step) Show that 0 E T. Substituting 0 for n gives (1 - x)(1) = 1 - x as required.

(Inductive step) Let n > 0. Show that if n E T, then n + 1 E T. Since n E T, it is as-

sumed that

(I - x)(1 + x + x2 + x3 +.. + xn) =1-xn+l

We must prove that n + 1 E T or that

(1 -x) (I +x + x2 + x3 +.- +xn+l) = xn+2

Use the following chain of equalities to complete the proof:

(1 -x)(l +x +x^2 +x^3 +... +xn +xn+l)

(1 -x)(1 + x + x^2 + x^3 +... + xn) + (I - x)xn+l (making the formula for n clear)

• xn+1 + (1 - x)xn+l (using the inductive hypothesis)


• xn+1 + xn+l - xn+2 (simplifying the expression)


• -xn+2

Therefore, n + 1 E T.

By the Principle of Mathematical Induction, T = N. U

Corollary 1: For r E R•with r 0 1,

n 1 rn+l

Y- a-ri =a.

i=0

Proof. n oari =a r

_i4= a= a )-=0 , ri = a a " -rn+l1-r •