Mathematics for Computer Science

13.7. Asymptotic Notation 535

You’ve seen this neat trick for evaluating a geometric sum:

SD 1 CzCz^2 C:::Czn

zSDzCz^2 C:::CznCznC^1

SzSD 1 znC^1

SD

1 znC^1

1 z

(wherez¤1/

Use the same approach to find a closed-form expression for this sum:

TD1zC2z^2 C3z^3 C:::Cnzn

Problem 13.3.
Sammy the Shark is a financial service provider who offers loans on the following
terms.

 Sammy loans a clientmdollars in the morning. This puts the clientmdollars

in debt to Sammy.

 Each evening, Sammy first charges a service fee which increases the client’s

debt byf dollars, and then Sammy charges interest, which multiplies the

debt by a factor ofp. For example, Sammy might charge a “modest” ten

cent service fee and 1% interest rate per day, and thenfwould be0:1andp

would be1:01.

(a)What is the client’s debt at the end of the first day?

(b)What is the client’s debt at the end of the second day?

(c)Write a formula for the client’s debt afterddays and find an equivalent closed
form.

(d)If you borrowed $10 from Sammy for a year, how much would you owe him?

Homework Problems

Problem 13.4.
Is a Harvard degree really worth more than an MIT degree? Let us say that a person
with a Harvard degree starts with $40,000 and gets a $20,000 raise every year after
graduation, whereas a person with an MIT degree starts with $30,000, but gets a
20% raise every year. Assume inflation is a fixed 8 % every year. That is, $1.08 a
year from now is worth $1.00 today.