6.042/18.062J Mathematics for Computer Science March 11,2005
Srini Devadas and Eric Lehman
Notes for Recitation 10
n
1 + z + z
2
+,.,+ z
n?1
=
1? z
(z = 1)
1? z
1
1 + z + x
2
+,.,=
1? z
(|z| < 1)
n(n + 1)
1 + 2 + 3 +,.,+ n =
2
2
1
1
2
+ 2
2
+ 3
2
+,.,+ n =
n(n +
2
)(n + 1)
3
2
n (n + 1)
2
3
1
3
+ 2
3
+ 3
3
+,.,+ n =
4
Theorem (Taylor’s theorem),Suppose that f, R R is n + 1 times differentiable on the
interval [0,x],Then
→
2 n
f
(n+1)
(z)x
n+1
f

(0)x f
(n)
(0)x
f(x) = f(0) + f
(0)x + +,.,+ +
for some z ∈ [0,x],
2! n! (n + 1)!

Recitation 10 2
1 Sums and Approximations
Problem 1,Evaluate the following sums,
(a)
1 1 1
1 + + + +,.,
2
2
2
3
2
Solution,The formula for the sum of an in?nite geometric series with ratio 1/2
gives,
1
= 2
1
1?
2
(b)
1 1 1
+,.,1?
2
+
2
2
2
3
Solution,The formula for the sum of an in?nite geometric series with ratio?1/2
gives,
1
= 2/3
1
1?
2
(c)
1 + 2 + 4 + 8 +,.,+ 2
n?1
Solution,The formula for the sum of a (?nite) geometric series with ratio 2 gives,
n
1? 2
= 2
n
1
1? 2
(d)
2n
k
2
k=n
Solution,
2n 2n n
k
2
= k
2
k
2
k=n+1 k=1 k=1
1 1
2n(2n +
2
)(2n + 1) n(n +
2
)(n + 1)
=
3
3
(e)
n m
3
i+j
i=0 j=0
Recitation 10 3
Solution,

n
m
n
m
3
i+j
= 3
i
· 3
j
i=0 j=0 i=0
j=0

m
n
= 3
j
· 3
i
j=0 i=0
=
3
m+1
1
2
·
3
n+1
1
2
4 Recitation 10
Problem 2,You’ve seen this neat trick for evaluating a geometric sum,
n
S = 1 + z + z
2
+,.,+ z
n n+1
zS = z + z
2
+,.,+ z + z
S? zS = 1? z
n+1
1? z
n+1
S =
1? z
Use the same approach to?nd a closed-form expression for this sum,
3
T = 1z + 2z
2
+ 3z +,.,+ nz
n
Solution,
4 n+1
zT = 1z
2
+ 2z
3
+ 3z +,.,+ nz
3
T? zT = z + z
2
+ z +,.,+ z
n
nz
n+1
1? z
n+1
1? nz
n+1
=
1? z
1? z
n+1
1 + nz
n+1
T =
(1? z)
2
1? z
Recitation 10 5
Problem 3,Here is a nasty product,

1 2 3 n
1 + 1 + 1 + 1 +
2 2 2 2
n n n
···
n
Remarkably,an expression similar to this one comes up in analyzing the distribution of
birthdays,Let’s make sense of it,
(a) Give a two-term Taylor approximation for e
x
,(Forget about the error term.)
Solution,
x
e ≈ 1 + x
(b) This is probably the most wide-used approximation in computer science,The
x
fact that x appears at,ground level” in the approximation and in the exponent of e
lets us translate sums into products and vice-versa,Rewrite the product using this
approximation,
Solution,
n/n
2
1+2+...+n
1/n
2
2/n
2
3/n
2
n
e e e e = e
2
· · ····
(c) Now use a standard summation formula to simplify the exponent.
Solution,The formula 1 + 2 + 3 +,.,+ n = n(n + 1)/2 gives:
n(n+1)/(2n
2
) 1/2+1/2n
e = e
(d) What constant does this approach for large n?
Solution,
√
e

6 Recitation 10
Problem 4,Let’s use Taylor’s Theorem to?nd some approximations for the function
√
1 + x,
(a) Give a three-term Taylor approximation for
√
1 + x,
Solution,First,we compute two derivatives,
1
f
(x) =
2
√
1 + x
1
f

(x) =?
4(1 + x)
3/2
Now we plug into Taylor’s theorem,
f (x) ≈ f (0) + xf
(0)
2
x x
1 +
2
8
(b) Sketch the function
√
1 + x and your approximation,How good is the approxi-
mation when x = 8?
Solution,The approximation is pretty bad when x = 8,The actual value is 3,but
the approximation is -3,
(c) Using this approximation and the fact that
√
1 + x =
√
x
1 + 1/x,give an ap-
proximation for
√
1 + x that is accurate for large x
Solution,
√
1 + x =
√
x
1 + 1/x
1 1
x 1 + +≈
√
2x 8x
2
(d) Estimate,
1,000,001
to a dozen places beyond the decimal point,You can try to check your answer with
a calculator,but you’d better use a good one!
Solution,
1 1
1,000,001 ≈ 1000 · 1 + +
10
6
10
12
2 · 8 ·
= 1000.000500000125