Mathematics for Computer Science

Chapter 13 Sums and Asymptotics506

The result of the subtraction is

SxSD 1 xnC^1 :

Solving forSgives the desired closed-form expression in equation 13.2, namely,

SD

1 xnC^1

1 x

:

We’ll see more examples of this method when we introducegenerating functions
in Chapter 15.

13.1.3 A Closed Form for the Annuity Value

Using equation 13.2, we can derive a simple formula forV, the value of an annuity
that paysmdollars at the start of each year fornyears.

V Dm



1 xn

1 x



(by equations 13.3 and 13.2) (13.4)

Dm

1 Cp.1=.1Cp//n^1

p

!

(substitutingxD1=.1Cp/): (13.5)

Equation 13.5 is much easier to use than a summation with dozens of terms. For
example, what is the real value of a winning lottery ticket that pays $50,000 per
year for 20 years? Plugging inmD $50,000,n D 20 , andp D 0:08gives
V $530,180. So because payments are deferred, the million dollar lottery is
really only worth about a half million dollars! This is a good trick for the lottery
advertisers.

13.1.4 Infinite Geometric Series

We began this chapter by asking whether you would prefer a million dollars today
or $50,000 a year for the rest of your life. Of course, this depends on how long
you live, so optimistically assume that the second option is to receive $50,000 a
yearforever. This sounds like infinite money! But we can compute the value of an
annuity with an infinite number of payments by taking the limit of our geometric
sum in equation 13.2 asntends to infinity.

Theorem 13.1.1.Ifjxj< 1, then

X^1

iD 0

xiD

1

1 x

: