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.

No comments:

Post a Comment