Manuel Kauers Hagenberg, October 13, 2003 RISC-Linz

Analytic Combinatorics

Homework 1

Exercise 1 Adapt the way how Gauß obtained ∑_{k=1}^{n} k = n(n+1)/2 to find closed form solutions for the following sums

a) ∑_{k=0}^{n}(2k + 1)  b) ∑_{k=1}^{n} k^{2}  c) ∑_{k=1}^{n} k^{3}

Ad a) We write add the summands twice, in inverse direction and group corresponding terms.

\begin{matrix}1 + & 3 + & 5 + & … + & 2k+1 + & … + & 2n+1 \\ 2n+1 + & 2n−1 + & 2n−3 + & … + & 2n+1−2k + & … + & 1 \\ 2n+2 + & 2n+2 + & 2n+2 + & … + & 2n+2 + & … + & 2n+2 \end{matrix}

The last line sums up to (n + 1)(2n + 2) = 2(n + 1)^{2}, and we conclude

∑_{k=0}^{n}(2k + 1) = \frac{1}{2}2(n + 1)^{2} = (n + 1)^{2}.

Ad b) If Gauß’ method is to determine ∑_{k=1}^{n} a_{k} through a linear combination of a_{k} and a_{n−k}, then I did not find a way to apply this method to a_{k} = k^{2}. It is, however, no problem at all to find a closed form of ∑_{k} k^{2} by elementary manipulations. Graham, Knuth, Patashnik provide seven ways to do it in Section 2.5, and here is a way which is not mentioned there.

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

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

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

Ad c) Once closed forms for ∑_{k} k^{r} are known for r < r_{0} and r_{0} is odd, then Gauß’ method applies again in a straightforward way. (We present it for r_{0} = 3.)

\begin{matrix}1 + & 2^{3} + & … + & (k + 1)^{3} + & … + & n^{3} \\ n^{3} + & (n − 1)^{3} + & … + & (n − k)^{3} + & … + & 1 \\ p(n, 0) + & p(n, 1) + & … + & p(n, k) + & … + & p(n, n − 1) \end{matrix}

where

p(n, k) = (k + 1)^{3} + (n − k)^{3} = 3(n + 1)k^{2} + 3(1 − n^{2})k + (n^{3} + 1).

It follows that

2 ∑_{k=1}^{n} k^{3} = ∑_{k=0}^{n−1} p(n, k)

= 3(n + 1) ∑_{k=0}^{n−1} k^{2} + 3(1 − n^{2}) ∑_{k=0}^{n−1} k + (n^{3} + 1)

= \frac{1}{2}(n + 1)n(2n − 1)(n − 1) + \frac{3}{2}(1 − n^{2})n(n − 1) + n(n^{3} + 1)

= \frac{1}{2}n^{2}(n + 1)^{2}, i.e.

∑_{k=1}^{n} k^{3} = \frac{1}{4}n^{2}(n + 1)^{2}.

Note that only the closed forms of ∑_{k} k^{r} with r < 3 have been used. Note further that the method happens to fail for even exponent because

(n − k)^{even} = k^{even} + lower terms,

whereas in

(n − k)^{odd} = −k^{odd} + lower terms

the −k^{odd} cancels with the k^{odd} from the first row.

Exercise 2 Let F (n) = 2(n + 1)H_{n} − 4n. Given H_{n} ∼ log n, prove that F (n) ∼ 2n log n.

By definition of ∼, we have lim_{n→∞} \frac{H_{n}}{log n} = 1. We have to show lim_{n→∞} \frac{F (n)}{2n log n} = 1. Plugging in the definition of F, and using elementary calculus, we get

lim_{n→∞} \frac{F (n)}{2n log n} = \underbrace{lim_{n→∞} \frac{n + 1}{n}}_{=1} \underbrace{lim_{n→∞} \frac{H_{n}}{log n}}_{=1} − 2 \underbrace{lim_{n→∞} \frac{1}{log n}}_{=0} = 1.

The claim follows. (I am not quite sure if this was really meant to be the exercise. Sorry if not.)