PUTNAM PROBLEM SOLVING SEMINAR

WEEK 5: SUMS AND SERIES

ALOK AGGARWAL

The Rules. There are way too many problems here to consider. Just pick a few problems
you like and play around with them. You are not allowed to try a problem that you
already know how to solve. Otherwise, work on the problems you want to work on.

The Hints. Look for symmetry. Interchange summation order. Replicate the sum. Tele-
scope. Manipulate a known series. Generalize. Compare with an integral. Try small and
extreme cases. Look for patterns. Use induction. Eat pizza. Work in groups. Use lots of
paper. Talk it over. Choose effective notation. Don’t give up after five minutes.

The Problems. The problems are APPROXIMATELY ordered from “easiest” to “hardest.”

1. The Riemann zeta function is defined as

1 1 1
ζ(k) = 1 + k + k + k + · · ·
2 3 4
Show that
∞ ∞
X X 3
(i) (ζ(k) − 1) = 1. (ii) (ζ(2k) − 1) = .
k=2 k=1
4

2. Let S be the set of positive integers whose only prime factors are 2, 3, or 5. Evaluate
X1 1 1 1 1 1 1 1 1 1 1
= + + + + + + + + + +···
x∈S
x 2 3 4 5 6 8 9 10 12 15

3. The Fibonacci sequence is defined by f0 = f1 = 1, fn = fn−1 + fn−2 for n ≥ 2. Evaluate

∞ ∞
X fn X 1
(i) . (ii) .
n=1
fn−1 fn+1 n=1
fn−1 fn+1

4. Sum the series

∞ X
∞
X m2 n
.
m=1 n=1
3m (n3m + m3n )

5. Evaluate
r r r
1 1 1 1 1 1
1+ 2 + 2 + 1+ 2 + 2 +···+ 1+ + .
1 2 2 3 2002 2 20032
Date: Monday, November 17, 2003.

1
6. Define {xn } by the recurrence x1 = 1/2, xn+1 = x2n + xn for n ≥ 1. Evaluate
 
1 1 1
+ +···+ ,
x1 + 1 x2 + 1 x2003 + 1
where bxc is the greatest integer less than or equal to x.

7. Sums of powers. For positive integers k, n define

Sk = 1k + 2k + · · · + nk .
Show that
     
k+1 k+1 k+1
S1 + S2 + · · · + Sk = (n + 1)k+1 − (n + 1).
1 2 k
Use this recurrence to find a formula for S2 , S3 , and S4 .

8. Prove that the average of the numbers n sin n◦ , n = 2, 4, 6, . . . , 180, is cot 1◦ .

9. For 0 < x < 1, express

∞
x2
n
X

n=0
1 − x2n+1
as a rational function of x.

10. Evaluate
∞ ∞
X n Y n3 − 1
(i) . (ii) .
n=1
n + n2 + 1
4
n=2
n3 + 1

11. For positive integer n, evaluate

∞ 
n + 2k
X 
,
k=0
2k+1

where bxc is the greatest integer less than or equal to x.

12. For nonnegative integers n and k, define Q(n, k) to be the coefficient of xk in the
expansion of (1 + x + x2 + x3 )n . Prove that
k   
X n n
Q(n, k) = .
j=0
j k − 2j

13. Let f0 (x) = ex and fn+1 (x) = xfn0 (x) for n = 0, 1, 2, . . .. Show that
∞
X fn (1)
= ee .
n=0
n!

2
14. Show that the power series for the function
eax cos(bx), (a, b > 0),
in powers of x has either no zero coefficients, or infinitely many zero coefficients.

15. Define C(α) to be the coefficient of x2003 in the power series about x = 0 of (1 + x)α .
Evaluate !
Z 1 2003
X 1
C(−y − 1) dy.
0 y+k
k=1

16. Evaluate
Z ∞
x3 x5 x7 x2 x4 x6
 
x− + − +··· 1 + 2 + 2 2 + 2 2 2 + · · · dx.
0 2 2·4 2·4·6 2 2 ·4 2 ·4 ·6

17. Evaluate n    
1X 2n n
lim −2 ,
n→∞ n k k
k=1
where bxc is the greatest integer less than or equal to x.

18. Let B(n) be the number of ones in the base two expression for the positive integer n.
For example, B(6) = B(1102 ) = 2 and B(15) = B(11112 ) = 4. Determine whether or not
∞
!
X B(n)
exp
n=1
n(n + 1)
is a rational number.

19. Show that the power series respresentation for the series
∞
X xn (x − 1)2n
n=0
n!
cannot have three consecutive zero coefficients.

20. Find n n
1 XX
5h4 − 18h2 k 2 + 5k 4 .


lim 5
n→∞ n
h=1 k=1

21. Evaluate
2n
1 Y 2
lim (n + i2 )1/n .
n→∞ n4
i=1

3
Appendix.

General binomial theorem for real α:

∞  
α
X α
(1 + x) = xn ,
n=0
n
where the binomial coefficient is defined for integer n ≥ 0 by
 
α . (α)(α − 1) · · · (α − n + 1)
= .
n n!

Useful series:
m  
m
X m
(1 + x) = xn , ∀x.
n=0
n
m−1
1 − xm X
= xn , x 6= 1.
1−x n=0
∞
1 X
= xn , |x| < 1.
1−x n=0
∞
x X
= nxn , |x| < 1.
(1 − x) 2
n=0
∞  
−m−1
X m+n n
(1 − x) = x , |x| < 1.
n=0
n
∞
X xn
− ln(1 − x) = , −1 ≤ x < 1.
n=1
n
∞
X (−1)n x2n+1
arctan(x) = , |x| ≤ 1.
n=0
2n + 1
∞
X xn
ex = , ∀x.
n=0
n!
∞
X (−1)n x2n
cos(x) = Re(eix ) = , ∀x.
n=0
(2n)!
∞
X (−1)n x2n+1
sin(x) = Im(eix ) = , ∀x.
n=0
(2n + 1)!

This handout can (soon) be found at

[Link]
E-mail address: alok@[Link], vakil@[Link]