Closed-Form Expessions for Summations

Some mathematical concepts are most intuitively described using summations. To efficiently calculate and work with the results of such summations, it may be necessary to represent them as a closed-form expression.

The following describes a method for finding closed-form expressions for summations of polynomials \(P_k(x)\) of order \(k\):

\[ \sum_{x=1}^n \mathrm{P}_k(x) = \sum_{x=1}^n \sum_{i=0}^k \alpha_i x^i \quad k,n \in \mathbb{N}, \alpha_i \in \mathbb{R} \]

Method

The first thing to note is that a summation over a polynomial may be decomposed into a summation over the sum of polynomial components:

\[ \sum_{x=1}^n \sum_{i=0}^k \alpha_i x^i = \sum_{i=0}^k \alpha_i \sum_{x=1}^n x^i = \sum_{i=0}^k \alpha_i \mathrm{K}_i(n) \]

To discover a closed-form expression for \(\mathrm{K}_k(n)\) we represent \(n^{k+1}\) as a summation. This summation must consist of \(\mathrm{K}_i(n)\) with \(i \le k\). By iteratively calculating and subtracting \(\mathrm{K}_i(n)\) for \(i < k\), we are left with a closed-form expression for \(\mathrm{K}_k(n)\).

Example

Let's have a look at how a closed-form expression for \(\mathrm{K}_2(n)\) may be derived without prior knowledge of \(\mathrm{K}_i(n)\) for \(i \leq 1\).

We begin by representing \(n\) as a summation. We can represent any power \(n^k\) by "integrating" over the differences in consecutive values:

\[ n^k = \sum_{x=1}^n (x^k - (x-1)^k) \]

For \(k = 1\):

\[ n = \sum_{x=1}^n (x^1-(x-1)^1) = \sum_{x=1}^n 1 = \sum_{x=1}^n x^0 = \mathrm{K}_0(n) \]

For \(k = 2\):

\[ n^2 = \sum_{x=1}^n (x^2-(x-1)^2) = \sum_{x=1}^n 2x-1 = 2 \mathrm{K}_1(n) - \mathrm{K}_0(n) \]

\[ \mathrm{K}_1(n) = \frac{1}{2}(n^2 + \mathrm{K}_0(n)) = \frac{n^2+n}{2} \]

For \(k = 3\):

\[ n^3 = \sum_{x=1}^n (x^3-(x-1)^3) = \sum_{x=1}^n 3x^2+3x-1 = 3 \mathrm{K}_2(n) + 3 \mathrm{K}_1(n) - \mathrm{K}_0(n) \]

\[ \mathrm{K}_2(n) = \frac{1}{3}(n^3 - 3 \mathrm{K}_1(n) + \mathrm{K}_0(n)) = \frac{n^2 + n}{2} + \frac{n^3 - n}{3} \]

Generalization

We can use binomial coefficients to represent the difference in powers \(x^k - (x-1)^k\) in terms of a summation over the polynomial components:

\[ n^{k+1} = \sum_{x=1}^n (x^{k+1} - (x-1)^{k+1}) = \sum_{x=1}^n -\sum_{i=0}^{k} {k+1 \choose i} x^i (-1)^{k+1-i} \]

\[ = \sum_{i=0}^{k} {k+1 \choose i} \sum_{x=1}^n x^i (-1)^{k-i} = \sum_{i=0}^{k} {k+1 \choose i} \mathrm{K}_i(n) (-1)^{k-i} \]

Solving for \(\mathrm{K}_k(n)\):

\[ \mathrm{K}_k(n) = {k+1 \choose k}^{-1}(n^{k+1} - \sum_{i=0}^{k-1} {k+1 \choose i} \mathrm{K}_i(n)(-1)^{k-i}) \]

\[ \mathrm{K}_k(n) = \frac{1}{k+1}(n^{k+1} - \sum_{i=0}^{k-1} {k+1 \choose i} \mathrm{K}_i(n)(-1)^{k-i}) \]

Table

Using a small program¹ we can compute the closed-form expressions for \(\mathrm{K}_k(n)\) for \(k \in [0,9]\):

k	\(\mathrm{K}_k(n)\)
1	\(\frac{1}{2} n \left(n + 1\right)\)
2	\(\frac{1}{6} n \left(n + 1\right) \left(2 n + 1\right)\)
3	\(\frac{1}{4} n^{2} \left(n + 1\right)^{2}\)
4	\(\frac{1}{30} n \left(n + 1\right) \left(2 n + 1\right) \left(3 n^{2} + 3 n - 1\right)\)
5	\(\frac{1}{12} n^{2} \left(n + 1\right)^{2} \left(2 n^{2} + 2 n - 1\right)\)
6	\(\frac{1}{42} n \left(n + 1\right) \left(2 n + 1\right) \left(3 n^{4} + 6 n^{3} - 3 n + 1\right)\)
7	\(\frac{1}{24} n^{2} \left(n + 1\right)^{2} \left(3 n^{4} + 6 n^{3} - n^{2} - 4 n + 2\right)\)
8	\(\frac{1}{90} n \left(n + 1\right) \left(2 n + 1\right) \left(5 n^{6} + 15 n^{5} + 5 n^{4} - 15 n^{3} - n^{2} + 9 n - 3\right)\)
9	\(\frac{1}{20} n^{2} \left(n + 1\right)^{2} \left(n^{2} + n - 1\right) \left(2 n^{4} + 4 n^{3} - n^{2} - 3 n + 3\right)\)