## Wednesday, February 5, 2014

### Telescoping Sums

Consider generalizations to the closed form formula for arithmetic sums:
$\sum_{k=1}^n k = 1+2+\ldots + n = \frac{n(n+1)}{2}$
Here's the formula for the square sums:
$\sum_{k=1}^n k^2 = 1^2+2^2+\ldots + n^2 = \frac{n(n+1)(2n+1)}{6}$
And cube sums: $\sum_{k=1}^n k^3 = 1^3+2^3+\ldots + n^3 = \left( \frac{n(n+1)}{2} \right)^2 = \left(\sum_{k=1}^n k \right)^2$
These formulas, among many other closed forms (e.g. for recurrence relations and binomial/hyperbolic sums) can be obtained using a deceptively simple technique: telescope sums. In its general form, it amounts to the following observation. For any function $f$:
$\sum_{k=1}^n f(k)-f(k-1) = f(n) - f(0)$
since all intermediate terms cancel out.

Applying this simple principle to the function $f(k)=k^2$, we get:
$\sum_{k=1}^n (k^2-(k-1)^2) = n^2$
But we can also expand the square inside the sum:
$\sum_{k=1}^n (k^2-(k-1)^2) = \sum_{k=1}^n (2k - 1) = 2 \sum_{k=1}^n k - n$
Equating these two results, we obtain the closed form formula for arithmetic sums:
$n^2 = 2 \sum_{k=1}^n k - n \iff \sum_{k=1}^n k = \frac{n(n+1)}{2}$

We can take the same approach to obtain sums of exponents. For example, the square sum is obtained using the telescoping principle on $f(k) = k^3$:
$\sum_{k=1}^n (k^3-(k-1)^3) = n^3$
Expanding the cube inside the sum:
$\sum_{k=1}^n (k^3-(k-1)^3) = \sum_{k=1}^n (3k^2-3k+1) = 3 \sum_{k=1}^n k^2 - 3\frac{n(n+1)}{2} + n$
Equating these two results, we obtain the desired closed form formula:
$n^3 = 3 \sum_{k=1}^n k^2 - 3\frac{n(n+1)}{2} + n \iff 6 \sum_{k=1}^n k^2 = 2n^3 + 3n(n+1) - 2n = n(n+1)(2n+1)$

This gives a recursive method of computing $\sum_{k=1}^n k^p$ for any positive integer $p$.

To obtain a non-recursive method (that doesn't require computing all sums with lower exponents), note that in general, the sum with exponent $p$ will be a polynomial of degree $p+1$, so another way to solve the sums is to performs an ansatz and compute the polynomial coefficients from particular values.

Let's try the non-recursive algorithm to find the sum with $p=4$:
$\sum_{k=1}^n k^4 = 1^4+2^4+\ldots + n^4$
without first solving the sum for $p=3$.
For $p=4$, we know the closed form is a polynomial of degree $p+1=5$. So we set:
$\sum_{k=1}^n k^4 = 1^4+2^4+\ldots + n^4 = a_5 n^5 + a_4 n^4 + a_3 n^3 + a_2 n^2 + a_1 n + a_0$
We have 6 unknown coefficients, so we need (at least) 6 equations. These can be obtained by computing the quartic sum for $n=1,2,\ldots,6$:
$n=1 \implies a_5 + a_4 + a_3 + a_2 + a_1 + a_0 = 1$
$n=2 \implies 2^5 a_5 + 2^4 a_4 + 2^3 a_3 + 2^2 a_2 + 2 a_1 + a_0 = 17$
$n=3 \implies 3^5 a_5 + 3^4 a_4 + 3^3 a_3 + 3^2 a_2 + 3^1 a_1 + a_0 = 98$
and so on.

Solving the linear system, we obtain: $a_5=1/5, a_4=1/2, a_3=1/3,a_2=a_1=0, a_0=-1/30$. You can either do this by hand (time consuming), or using a computer algebra system, or using this online calculator by copy-pasting the following:
a + b + c + d + t + f = 1
32*a + 16*b + 8*c + 4*d + 2*t + f = 17
243*a + 81*b + 27*c + 9*d + 3*t + f = 98
1024*a + 256*b + 64*c + 16*d + 4*t + f = 354
3125*a + 625*b + 125*c + 25*d + 5*t + f = 979
7776*a + 1296*b + 216*c + 36*d + 6*t + f = 2275

The identity is thus:
$\sum_{k=1}^n k^4 = 1^4+2^4+\ldots + n^4 = \frac{n^5}{5} + \frac{n^4}{2} + \frac{n^3}{3} - \frac{1}{30}$

This approach is taken far beyond sums of powers in the computer algebra development of Wilf-Zeilberger pairs.