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:

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

\]

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

\[

\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) = 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}

\]

\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) = 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)

\]

\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

\]

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}

\]

\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}

\]

## No comments:

## Post a Comment