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

Problem Set 6

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)}

Solution: Apply the formula for the sum of a geometric series three times.

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

= ∑_{i=0}^{∞} 2^{−i} · (∑_{j=0}^{∞} 2^{−2j} · \frac{8}{7})

= ∑_{i=0}^{∞} 2^{−i} · \frac{4}{3} · \frac{8}{7}
= \frac{2}{1} · \frac{4}{3} · \frac{8}{7}
= \frac{64}{21}

(b)

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

Solution: This fearsome-looking sum is a paper tiger; we just apply the formula for the sum of a geometric series followed by the formula for the sum of an arithmetic series.

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

= ∑_{j=1}^{n} 2j
= j(j + 1)

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}

Solution: Though substituting in Stirling’s formula initially gives a complicated expression, most of the square roots and the exponentials cancel.

\binom{n}{αn} = \frac{n!}{(αn)! ((1 − α)n)!}
∼ \frac{\sqrt{2πn} (\frac{n}{e})^{n}}{\sqrt{2παn} (\frac{αn}{e})^{αn} · \sqrt{2π(1 − α)n} (\frac{(1−α)n}{e})^{(1−α)n}}

= \frac{1}{\sqrt{2πnα(1 − α)}} · \frac{1}{α^{αn} · (1 − α)^{(1−α)n}}

Letting α = 1/2,

\binom{n}{αn} ∼ \frac{1}{\sqrt{2πnα(1 − α)}} · \frac{1}{α^{αn} · (1 − α)^{(1−α)n}}
= \frac{1}{\sqrt{2πnα(1 − α)}} · 2^{n}
= Θ (\frac{2^{n}}{\sqrt{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.)

Solution: After k months, I owe

L(1 + i)^{k} − P · (1 + i)^{k−1} − P · (1 + i)^{k−2} − … − P
= L(1 + i)^{k} − P · \frac{(1 + i)^{k} − 1}{i}.

The loan is paid when the amount that I owe equals zero; that is, when

L(1 + i)^{k} − P · \frac{(1 + i)^{k} − 1}{i} = 0.

Solving for k, the number of months until the loan is repaid, gives

k = \frac{ln (\frac{P}{P −iL})}{ln(1 + i)}.

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

Solution: After k months, where k is even, I owe

L(1 + i)^{k} − 2P · (1 + i)^{k−2} − 2P · (1 + i)^{k−4} − … − 2P
= L(1 + i)^{k} − 2P · \frac{(1 + i)^{k} − 1}{(1 + i)^{2} − 1}.

As before, the loan is repaid when the amount I owe equals zero. This happens when

k = \frac{ln (\frac{2P}{2P −((1+i)^{2}−1)L})}{ln(1 + i)}.

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

Solution: After k months, where k is odd, I owe

L(1 + i)^{k} − 2P · (1 + i)^{k−1} − 2P · (1 + i)^{k−3} − … − 2P
= L(1 + i)^{k} − 2P · \frac{(1 + i)^{k+1} − 1}{(1 + i)^{2} − 1}.

The loan is repaid when

k = \frac{ln (\frac{2P}{2P (1+i)−((1+i)^{2}−1)L})}{ln(1 + i)}.

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

Solution: Substitution gives the following results:

frequent payment  360 months
infrequent payment, late start  362 months
infrequent payment, early start  356 months

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

Solution: Getting money to the bank early is more important than the frequency of payments.

Handout 28: Problem Set 6 5 Problem 4 Find a closed-form expression for the summation ∑_{i=1}^{n} i^{2}x^{i}. Solution: We first come up with a formula for ∑_{i=1}^{n} i^{2}x^{i} and then prove it using induction. From class notes we know that:

∑_{i=1}^{n} ix^{i} = \frac{x − (n + 1)x^{n+1} + nx^{n+2}}{(1 − x)^{2}} .

Differentiating (with respect to x) the above expression and multiplying with x we find that

∑_{i=1}^{n} i^{2}x^{i} = \frac{x + x^{2} − (n + 1)^{2}x^{n+1} + (2n^{2} + 2n − 1)x^{n+2} − n^{2}x^{n+3}}{(1 − x)^{3}}

We prove that the above closed-form expression for the summation is correct by induction on the upper bound n of the summation. In particular, let P (n) be the predicate that:

∑_{i=1}^{n} i^{2}x^{i} = \frac{x + x^{2} − (n + 1)^{2}x^{n+1} + (2n^{2} + 2n − 1)x^{n+2} − n^{2}x^{n+3}}{(1 − x)^{3}} .

Base Case. P (1) is true since

∑_{i=1}^{1} i^{2}x^{i} = x = \frac{x + x^{2} − 4x^{2} + 3x^{3} − x^{4}}{(1 − x)^{3}} .

Inductive Step. Assume P (n) is true. Then

∑_{i=1}^{n} i^{2}x^{i} + (n + 1)^{2}x^{n+1} =
∑_{i=1}^{n+1} i^{2}x^{i} = \frac{x + x^{2} − (n + 1)^{2}x^{n+1} + (2n^{2} + 2n − 1)x^{n+2} − n^{2}x^{n+3}}{(1 − x)^{3}} + (n + 1)^{2}x^{n+1}
= \frac{x + x^{2} − (n + 2)^{2}x^{n+2} + (2(n + 1)^{2} + 2(n + 1) − 1)x^{n+3} − (n + 1)^{2}x^{n+4}}{(1 − x)^{3}}

Thus P (n + 1) is true. Hence, P (n) is true for all n. Problem 5 Show that ∑_{k=1}^{∞} 1/k^{3/2} is bounded above by a constant.

Solution: We use the integral method for bounding the infinite sum. Since f(k) = \frac{1}{k^{3/2}} is monotonically decreasing for k > 1, we have:

∑_{k=1}^{∞} 1/k^{3/2} = 1 + ∑_{k=2}^{∞} 1/k^{3/2}
≤ 1 + ∫_{1}^{∞} \frac{1}{x^{3/2}} dx
= 1 + [\frac{−2}{\sqrt{x}}]_{1}^{∞}
= 1 + (0 + 2)
= 3

Hence, ∑_{k=1}^{∞} 1/k^{3/2} ≤ 3.

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})

Solution:

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

Following are some hints on deriving the table above:

(a) See notes on O-notation. (to appear)

(b) Polynomial growth versus exponential growth. (See Theorem 3.6, Lecture 9, Fall97.)

(c) When n is a multiple of π, n^{sin n} = 1, so no constant times 1 will bound \sqrt{n} as n ranges over multiples of π. When n is of the form 2k′π + π/2, for some integer k′, then n^{sin n} = n and \frac{n}{\sqrt{n}} = \sqrt{n} grows without bound as k′ increases.

(d) \frac{2^{n}}{2^{n/2}} = 2^{n/2} grows without bound as n grows – it is not bounded by a constant.

(e) See Rosen §1.8 Ex. 61,62