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

Tutorial 7 Problems

Problem 1 Riemann’s Zeta Function ζ(k) is defined to be the infinite summation:

1 + \frac{1}{2^{k}} + \frac{1}{3^{k}} ⋯ = ∑_{j≥1} \frac{1}{j^{k}}

Prove that

∑_{k≥2}(ζ(k) − 1) = 1

Solution:

First, we prove that ∑_{k=2}^{n} \frac{1}{k(k−1)} = 1 − \frac{1}{n}

By using partial fractions, we find that \frac{1}{k(k−1)} = \frac{1}{k−1} − \frac{1}{k}. So we have:

∑_{k=2}^{n} \frac{1}{k(k − 1)} = ∑_{k=2}^{n} (\frac{1}{k − 1} − \frac{1}{k} )

= ∑_{k=2}^{n} \frac{1}{k − 1} − ∑_{k=2}^{n} \frac{1}{k}
= \frac{1}{1} + \frac{1}{2} + … + \frac{1}{n − 2} + \frac{1}{n − 1} −

[\frac{1}{2} + \frac{1}{3} + … + \frac{1}{n − 1} + \frac{1}{n}]

So all that does not cancel out is 1 − \frac{1}{n}.

We now prove that ∑_{k≥2}(ζ(k) − 1) = 1

∑_{k≥2}(ζ(k) − 1) = ∑_{k≥2} [(∑_{j≥1} \frac{1}{j^{k}} ) − 1]

= ∑_{k≥2} ∑_{j≥2} \frac{1}{j^{k}}

= ∑_{j≥2} ∑_{k≥2} \frac{1}{j^{k}}

= ∑_{j≥2} \frac{1}{j^{2}} ∑_{k≥0} \frac{1}{j^{k}}

= ∑_{j≥2} \frac{1}{j^{2}} · \frac{1}{1 − 1/j}

= ∑_{j≥2} \frac{1}{j(j − 1)}

= lim_{n→∞} ∑_{j=2}^{n} \frac{1}{j(j − 1)}

= lim_{n→∞}(1 − \frac{1}{n})
= 1

Problem 2 By manipulating summations, without recourse to induction, prove that

∑_{k=1}^{n} H_{k} = (n + 1)H_{n} − n

Solution:

∑_{k=1}^{n} H_{k} = ∑_{k=1}^{n} ∑_{j=1}^{k} \frac{1}{j}

= ∑_{1≤j≤k≤n} \frac{1}{j}

= ∑_{j=1}^{n} ∑_{k=j}^{n} \frac{1}{j}

= ∑_{k=1}^{n} \frac{n − j + 1}{j}

= ∑_{k=1}^{n} (\frac{n + 1}{j} − 1)

= (n + 1) ∑_{j=1}^{n} \frac{1}{j} − n
= (n + 1)H_{n} − n

Problem 3 Asymptotic notation

Given that f(x) = O(g(x)), prove or disprove the following:

(a) 2^{f(x)} = O(2^{g(x)})

Solution: The above does not hold. Let f(x) = 2x and g(x) = x. Then f(x) = O(g(x)). Now 2^{f(x)} = 2^{2x} = 4^{x}, and 2^{g(x)} = 2^{x}, and 4^{x} ≠ O(2^{x}). Indeed, \frac{4^{x}}{2^{x}} = 2^{x}, so the ratio grows without bound as x grows — it is not bounded by a constant.

(b) f(x)^{2} = O(g(x)^{2})

Solution: The above does hold. Since f(x) = O(g(x)), ∃x_{0}, c such that ∀x ≥ x_{0}, |f(x)| ≤ cg(x). So, ∀x ≥ x_{0}, f(x)^{2} ≤ c^{2}g(x)^{2}. Therefore, there exist x′_{0} = x_{0} and c′ = c^{2} such that ∀x ≥ x′_{0}, f(x)^{2} ≤ c′g(x)^{2}. So f(x)^{2} = O(g(x)^{2}).

Problem 4 We begin with two large glasses. The first glass contains a pint of water, and the second contains a pint of wine. We pour 1/3 of a pint from the first glass into the second, stir up the wine/water mixture in the second glass, and then pour 1/3 of a pint of the mix back into the first glass. We now repeat this pouring back-and-forth process a total of n times.

(a) Describe a closed form formula for the amount of wine in the first glass after n back-and-forth pourings.

(b) What is the limit of the amount of wine in each glass as n approaches infinity?

Solution: The state of the system of glasses/wine/water at the beginning of a round of pouring and pouring back is determined by the total amount of wine in the first glass. Initially, the first glass contains one pint of water and no wine. Suppose the first glass contains w pints of wine, 0 ≤ w ≤ 1. Since we’re at the beginning of a round, it contains one pint of liquid, and therefore contains 1 − w pints of water. The second glass contains the rest of the wine and water.

Pouring 1/3 pint from first glass to second leaves 2/3 pint of liquid and (2/3)w wine in the first glass, and 4/3 pints liquid and 1 − (2/3)w wine in the second glass. Pouring 1/3 pint back from second into first transfers a proportion of (1/3)/(4/3) of the wine in the second glass into the first. So the round completes with both glasses containing a pint of liquid, and the first glass containing

(2/3)w + (1/4)(1 − (2/3)w) = 1/4 + w/2

pints of wine. After the second round, the first glass contains

1/4 + (1/4 + w/2)/2 = 1/4 + 1/8 + w/2^{2}

pints of wine, and after the nth round

w/2^{n} + Σ_{i=1}^{n}(1/2)^{i+1} = w/2^{n} + (1/2)Σ_{i=1}^{n}(1/2)^{i}
= w/2^{n} + (1/2)(−1 + Σ_{i=0}^{n}(1/2)^{i})
= w/2^{n} + (1/2)(−1 + (1 − (1/2)^{n+1})/(1 − 1/2))
= w/2^{n} − 1/2 + 1 − (1/2)^{n+1}
= w/2^{n} + 1/2 − (1/2)^{n+1}.

So when w = 0 initially, the pints of wine in the first glass is

1/2 − (1/2)^{n+1}.

You would expect after a thorough mixing that the glasses would contain the same amount of wine, viz. 1/2 pint. Indeed, the limiting amount of wine in the first glass approaches 1/2 from below as n approaches infinity. In fact, it approaches 1/2 no matter how the wine was initially distributed.

Problem 5

(a) Give an example of functions f, g : ℕ → ℕ such that neither f = O(g) nor g = O(f). Prove it.

Solution: f(n) = 1 + n(n mod 2), g(n) = 1 + n((1 + n) mod 2). So f(n) is n times the size of g(n) on odd n, vice-versa on even n.

(b) Prove or give a counterexample: If f_{1}, f_{2}, … is a sequence of functions from ℕ to ℕ such that f_{i}(n) = O(1) for all i ≥ 1, then

∑_{i=1}^{n} f_{i}(n) = O(2^{n}).

Handout ??: Tutorial 7 Problems 5 Solution: False, let f_{i} be a constant function with f(n) = b(i) for all n, where b(i) is nonnegative and not O(2^{i}), for example, b(i) = i2^{i}. So f_{i} = O(1) for each i. Now

∑_{i=1}^{n} f_{i}(n) ≥ f_{n}(n) = b(n) ≠ O(2^{n}).