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
S zSD 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.