Massachusetts Institute of Technology Handout 19 6.042J/18.062J: Mathematics for Computer Science 3/2/99 typo corrected 3/7 Professors Nancy Lynch and Srinivas Devadas

Problem Set 5

Due: Tuesday, March 9.

Problem 1 (16 points) Find closed-form expressions for the following sums.

(a)

∑_{i=0}^{∞} ∑_{j=0}^{∞} ∑_{k=0}^{∞} 2^{−(i+2j+3k)}

(b)

∑_{j=1}^{n} ∑_{i=0}^{∞} j^{2/3} · (1 − \frac{1}{2j^{1/3}} )^{i}

Problem 2 (10 points) The expression \binom{n}{k} is read “n choose k” and represents the quantity

\frac{n!}{k! (n − k)!}.

This expression comes up frequently in probability and combinatorics and will be used extensively later in this course. Suppose that n is even. Prove that

\binom{n}{n/2} = Θ(2^{n}/\sqrt{n}).

Use the following form of Stirling’s formula:

n! ∼ \sqrt{2πn} (\frac{n}{e})^{n}

Problem 3 (10 points) Let

S_{n} ::= ∑_{k=1}^{n} 1/(2k − 1).

(a) Find a closed form expression for S_{n} in terms of the harmonic numbers H_{n} and H_{2n}.

(b) Use an approximation for the harmonic numbers to show that

S_{n} = ln(2\sqrt{n}) + O(1).

Problem 4 (10 points) Use the integral method to find a Θ bound on the following sum.

∑_{i=1}^{n} i ln i

Problem 5 (20 points) In analyzing algorithms, one often must determine the asymptotic behavior of nasty functions like those shown below.

n!  (ln n)^{300}  2n^{ln ln n}
n^{n}  n(ln n)^{4}  n^{1.01}/2
7n^{2} + 3  \sqrt{n}^{\sqrt{n}}  4^{n}
(n/e)^{n} (7n^{3} − 17n^{2})/(n + 128) (ln n)^{ln n}

Arrange these functions in a list so that each is Θ or O of the next function in the list. For each pair of consecutive functions in your list, indicate whether the stonger Θ relationship holds or only the weaker O relationship. No proofs are required.

Problem 6 (10 points)

Recently, David Bowie, a British music star, sold a portion of the future profits from his music for $55 million dollars to Prudential Insurance. This deal spawned others.

(a) Billy Joel wants to sell his future profits for $200 million today. Suppose that he can generate a fixed profit at the end of every year for the next 20 years. If the inflation rate is p = 0.03, how large must Billy Joel’s annual profit be for investors to make a 10% return?

(b) The Eagles figure that they can generate at least $25 million from their music at the end of each year for eternity. What should an investor who wants a 15% return pay today for the Eagles contract?

Problem 7 (24 points) Shady finance people often assert that a loan can be paid off more quickly by making half-size payments twice as often. The theory is that frequent payments prevent interest from building up. Suppose that I take out a loan for L dollars, and at the end of every month, the bank charges me interest on the loan at rate i.

(a) First, let’s consider a “frequent payment” repayment strategy. Suppose that I pay P dollars to the bank every month, right after the bank charges me interest. (So, after 1 month I owe L(1 + i) − P dollars, and after 2 months I owe L(1 + i)^{2} − P · (1 + i) − P dollars.) Give a closed-form expression for the number of months until the loan is repaid.

(Assume that interest charges are smaller than my monthly payment; that is, iL < P. Do not worry about rounding to an integral number of months.)

(b) Now let’s consider an “infrequent payment, late start” repayment strategy. Suppose that I pay 2P dollars to the bank every two months, making the first payment two months after I take out the loan. (Thus, after 2 months I owe L(1 + i)^{2} − 2P dollars, and after 4 months I owe L(1 + i)^{4} − 2P · (1 + i)^{2} − 2P dollars.) Give a closed-form expression for the number of months until the loan in repaid.

(c) Finally, let’s consider an “infrequent payment, early start” strategy. As before, I pay 2P dollars to the bank every two months, but now I make the first payment one month after I take out the loan. (Thus, after 1 month I owe L(1 + i) − 2P dollars, and after 3 months I owe L(1 + i)^{3} − 2P · (1 + i)^{2} − 2P dollars.) Give a closed-form expression for the number of months until the loan is repaid.

(d) Suppose that I take a loan of L = $100, 000. The monthly interest rate is i = 0.005. I either pay the bank P = $600 every month or 2P = $1, 200 every two months, depending on the repayment strategy that I choose. How long will repayment take for each of the three strategies?

(e) In 50 words or fewer, explain the merits of frequent and infrequent payment strategies.