Massachusetts Institute of Technology Handout 19 6.042J/18.062J: Mathematics for Computer Science October 17, 2000 Professors Nancy Lynch and Srinivas Devadas

Problem Set 5

Due: 2:35pm in lecture, Tuesday, October 24, 2000.

Be sure to indicate your TA’s name clearly on the solutions your turn in.

—————————————————————————–

Self-study Read: Rosen Section 1.7, 1.8 Self-study problems (not to be handed in): Section 1.7: 5, 8, 9 Section 1.8: 7, 13, 14, 21

—————————————————————————–

Reading: Lecture notes; Rosen 1.7, 1.8 (skim)

Policy on collaboration If you collaborated with someone on the problem sets, you should mention their names on top of the problem set. If you did not collaborate with anyone, you should explicitly say so. As a reminder, the write-up of your solutions should be entirely your own.

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 (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.

Problem 4 Find a closed-form expression for the summation ∑_{i=1}^{n} i^{2}x^{i}.

Problem 5 Show that ∑_{k=1}^{∞} 1/k^{3/2} is bounded above by a constant.

Problem 6 Asymptotic notation

For each pair of functions (f(n), g(n)) in the table below, indicate whether the statement at the top of the column is true (e.g., whether f(n) = O(g(n))). Assume k ≥ 1, ϵ > 0, and c > 1 are constants. Your answer should be in the form of a table with “yes” or “no” in each box.

f(n)  g(n) f(n) = O(g(n)) g(n) = O(f(n)) f(n) = Θ(g(n))
log^{k} n  n^{ϵ}
n^{k}  c^{n}
\sqrt{n}  n^{sin n}
2^{n}  2^{n/2}
log(n!) log(n^{n})