# Summation Theorem how to get formula for exponent greater than 3

I'm studying in the summer for calculus 2 in the fall and I'm reading about summation. I'm given these formulas: \begin{align*} \sum_{i=1}^n 1 &= n, \\ \sum_{i=1}^n i &= \frac{n(n+1)}{2},\\ \sum_{i=1}^n i^2 &= \frac{n(n+1)(2n+1)}{6},\\ \sum_{i=1}^n i^3 &=\left[ \frac{n(n+1)}{2}\right]^2. \end{align*}

But how do I come up with the right formula for exponents greater than 3?

• Consider examining Faulhaber's Theorem: theoremoftheday.org/Binomial/Faulhaber/TotDFaulhaber.pdf – pMarkov Jul 8 '15 at 0:30
• I think is a bad idea to see Faulhaber formula by itself... you will not improve any knowledge or understanding, you only will see a recipe. The key point is understand Bernoulli polynomials that are the solution for the equation $\Delta f_n (k)=nk^{n-1}$ where $f_n(k)$ are polynomials of degree n (the Bernoulli polynomials) and after see the relation with this question. You can try the first pages of this text by example. – Masacroso Jul 8 '15 at 2:08
• Perhaps one should also ask, does one even want to (in Calculus 2). In calculating a Riemann sum, we only need to know the coefficient on the leading term of the formula (since the other terms go to zero as $n$ becomes arbitrarily large). For example $$\sum^{n}_{i=1}i^2 = \frac{1}{3}n^3+an^2+bn+c$$ is sufficient for calculating the area under a parabola. – John Joy Jul 8 '15 at 14:48

You can obtain these formulae recursively. Look at this

$$n^5 = \sum_{k=1}^n \left( k^5 - (k-1)^5\right)$$

Expand the second term. Cancel the $k^5$ terms. Then apply the identities above. You can solve for $\sum_{k=1}^n k^4$. Continue in this fashion to get sums for higher powers.

General method for indefinite summation $\def\nn{\mathbb{N}}$ $\def\zz{\mathbb{Z}}$

Define the forward difference operator:

$D = ( \text{function$f$on$\zz$} \mapsto ( \text{int$n$} \mapsto f(n+1) - f(n) ) )$

Namely for any function $f$ on $\zz$ and $n \in \zz$, $D(f)(n) = f(n+1) - f(n)$.

If you think of the functions as sequences (infinite in both directions), then taking the forward difference means replacing each term with the value of the next term minus itself. For example the following shows what happens when you repeatedly take the forward difference of the sequence of cubes:

...,-27,-8,-1, 0, 1, 8,27,...
..., 19, 7, 1, 1, 7,19,37,...
...,-12,-6, 0, 6,12,18,24,...
...,  6, 6, 6, 6, 6, 6, 6,...
...,  0, 0, 0, 0, 0, 0, 0,...
...,  0, 0, 0, 0, 0, 0, 0,...


Then we have:

$D\left( \text{int$n$} \mapsto \binom{n}{k+1} \right) = \left( \text{int$n$} \mapsto \binom{n}{k} \right)$ for any $k \in \zz$.

This is to be expected because it follows directly from Pascal's triangle, especially if we define $\binom{n}{k}$ using the triangle.

This means that if we have any function $f$ on $\zz$ such that $f(n) = \sum_{k=0}^\infty a_k \binom{n}{k}$ for any $n \in \zz$, then we get:

$D(f)(n) = \sum_{k=0}^\infty a_{k+1} \binom{n}{k}$ for any $n \in \zz$.

From a high-level perspective, this is the discrete version of the Taylor series, and indeed for such a function we easily see that $f(n) = \sum_{k=0}^\infty D^k(f)(0) \binom{n}{k}$ for any $n \in \zz$, because $\binom{0}{0} = 1$ while $\binom{0}{k} = 0$ for any $k \in \nn^+$.

This works for any polynomial function $f$ on $\zz$, since $D^k(f)$ is the zero function once $k$ is larger than the degree of $f$, so we can use it to immediately find the series for $(\text{int n} \mapsto n^3)$, and then just take the anti-difference by shifting the coefficients of the series the other way. The undetermined constant that appears will drop out once we perform a definite sum like if we want the sum of the first $m$ cubes.

Sum of $p$ powers

For example if we want $\sum_{k=1}^{n-1} k^2$ we first find the iterated forward differences of the sequence of squares $( n^2 )_{n \in \zz}$:

...,0,1,4,9,...
...,1,3,5,...
...,2,2,...
...,0,...


So we immediately get $n^2 = 0 \binom{n}{0} + 1 \binom{n}{1} + 2 \binom{n}{2}$ and hence $\sum_{k=0}^{n-1} = 0 \binom{n}{1} + 1 \binom{n}{2} + 2 \binom{n}{3}$. It is trivial to simplify it to $\sum_{k=0}^{n-1} = \frac{1}{6}(n-1)n(2n-1)$.

Computation efficiency

This is far more efficient than the method given by ncmathsadist because the series using binomial coefficients is easy to manipulate and easy to compute. For sum of $p$-powers we only need $O(p^2)$ arithmetic operations to find the forward-differences and then $O(p^2)$ more to simplify the series form into a standard polynomial form. In contrast, the other method requires $O(p^3)$ arithmetic operations.

Indefinite summation of non-polynomials

Also, for a wide class of non-polynomial functions, we can still compute the indefinite sum without using the series, by using the discrete analogue to integration by parts, here called summation by parts.

To derive it, simply check that $D(f \times g)(n) = f(n+1) g(n+1) - f(n) g(n) = f(n+1) D(g)(n) - D(f)(n) g(n)$ and so we get the product rule:

$D(f \times g) = R(f) \times D(g) + D(f) \times g$

where $R$ is the right-shift operator defined as:

$R = ( \text{function$f$on$\zz$} \mapsto ( \text{int$n$} \mapsto f(n+1) ) )$

Namely for any function $f$ on $\zz$ and $n \in Z$, $R(f)(n) = f(n+1)$.

For convenience we also define the summation operator:

$S = ( \text{function$f$on$\zz$} \mapsto ( \text{int$n$} \mapsto \sum_{k=0}^{n-1} f(k) ) )$

Then we have the important property that $DS(f) = f$ for any function $f$ on $\zz$, analogous to the fundamental theorem of calculus.

Now by substituting $f$ with $S(f)$ into the product rule and taking summation on both sides we get summation by parts:

$S( f \times g ) = S(f) \times g - S( R(S(f)) \times D(g) ) + c$ for some constant function $c$ on $\zz$.

Example indefinite sum

Using this we can easily compute things like $\sum_{k=1}^n k^3 3^k$ by applying it three times, each time reducing the degree of the polynomial part. There are other ways to achieve this using differentiation, but this method is purely discrete.

• I'm aware of corresponding approaches, but didn't see this notation. Any helpful reference? (+1) – Markus Scheuer Jul 8 '15 at 14:32
• @MarkusScheuer: Unfortunately I do not know of a comprehensive reference, because I developed all this on my own. I found that they are called Newton series and Summation by Parts on Wikipedia. The notation I used to define the operators comes from computer science where functions are first-class objects. If you learn Javascript it would be similar. – user21820 Jul 8 '15 at 15:45
• @MarkusScheuer : The above material, and a bit more, is section 2.6 in Graham, Knuth, Patashnik, "Concrete Mathematics, 2nd ed.". A more "theoretical" treatment is section 2.1 (and its exercises) in Elaydi, "An Introduction to Difference Equations, 3rd. ed.". – Eric Towers Jul 8 '15 at 21:13

You can find the formulas here (they get progressively messier), however for Calculus 2 you won't need anything past what you've already got.

The way I like to do this is to consider that we're looking for a polynomial $P(x)$ of degree $n+1$ satisfying: $$P(x)=x^n+P(x-1).$$ $$P(0)=0$$ Notice that when we expand, we get: $$P(x)=x^n+P(x-1)=x^n + (x-1)^n + P(x-2) = \ldots = x^n + (x-1)^n + \ldots + 2^n + 1^n + 0$$ which is what we desire. It's not too hard to show that such a polynomial always exists*, but once we know it does, this gives a way to find it. So, for $n=1$ we want a polynomial of degree $2$ - so $P(x)=ax^2+bx$ (noting that the constant term is obviously $0$) - satisfying $$[ax^2 + bx] = x + [a(x-1)^2 + b(x-1)]$$ which expands as: $$ax^2 + bx = ax^2 + (1+b-2a)x + (a-b)$$ and noting that the coefficient of $x$ and the constant term must be equal on both sides, we get: $$b=1+b-2a$$ $$0=a-b$$ yielding $a=b=\frac{1}2$ so $$P(x)=\frac{1}2\left(x^2+x\right)$$ is the polynomial giving the sum of $1+2+3+\ldots + x$. We can repeat this procedure for all degrees of polynomials - and may indeed replace the $x^n$ term by any polynomial of degree $n$ (which is often helpful). It takes some work to do things this way, but it always works without too much cleverness.

(*My way to do this would be to consider the linear map on polynomials of degree at most $n+1$ taking $P$ to a pair $(Q,c)$ where $Q(x)=P(x)-P(x-1)$ and $c=P(0)$. It turns out that this is map is invertible. Notice that for $Q$ to be zero, $P$ must be constant - and for $c$ to be zero too, $P$ must be the zero polynomial, meaning that the kernel of the map is trivial. Additionally, the degree of $Q$ is at most $n$, so the space of pairs $(Q,c)$ is $n+1$ dimensional too, so we may conclude that any system of equations of similar form to the one presented has a unique solution - which by the same methods as used in the post, can be shown to mean that summing over a polynomial yields another polynomial, of degree one higher)

For any polynomial of $p$th powers $S_p(n) = \sum_{k=1}^n k^p$ $(p \in \Bbb N)$ there is a formula of higher degree $S_p(n)=\sum_{k=1}^{p+1} a_kn^k$

The question is how to find the unknown $a_k$ coefficients which are real numbers. So use the following formulas to find them:

$a_k= \frac{1}{k!} \cdot \sum_{j=1}^{p+1-k} (-1)^{j+1} \frac {a_{k+j} \cdot (k+j)!}{(j+1)!}$ for $(0 \lt k \lt p+1)$

$a_k=\frac {1}{p+1}$ for $(k=p+1)$

Example:

$S_3(n) = \sum_{k=1}^n k^3$

Solution:

$p=3$

$S_3(n)=\sum_{k=1}^{4} a_kn^3 = a_1n+a_2n^2+a_3n^3+a_4n^4$

Now using the above two formulas to find the unknown coefficients $a_1,a_2,a_3,a_4$

$a_4 = \frac{1}{3+1}=\frac{1}{4}$

$a_3=\frac {1}{3!} \cdot \sum_{j=1}^{1} (-1)^{j+1} \frac {a_{3+j} \cdot (3+j)!}{(j+1)!} =\frac {1}{3!} \cdot \frac {a_4 \cdot 4!}{2!} = \frac {\frac{1}{4} \cdot 4!}{3! \cdot 2!}=\frac {1}{2}$

$a_2=\frac {1}{2!} \cdot \sum_{j=1}^{2} (-1)^{j+1} \frac {a_{2+j} \cdot (2+j)!}{(j+1)!} = \frac {1}{2!} \cdot (\frac {a_3 \cdot 3!}{2!} - \frac {a_4 \cdot 4!}{3!}) = \frac {1}{2} \cdot (3a_3-4a_4)= \frac {1}{2} \cdot (3 \cdot \frac {1}{2}-4 \cdot \frac {1}{4})= \frac {1}{4}$

$a_1=\frac {1}{1!} \cdot \sum_{j=1}^{3} (-1)^{j+1} \frac {a_{1+j} \cdot (1+j)!}{(j+1)!} = \sum_{j=1}^{3} (-1)^{j+1} a_{1+j}=a_2-a_3+a_4 =\frac {1}{4}-\frac {1}{2}+\frac {1}{4}=0$

Finally

$S_3(n)=0*n+\frac {1}{4}*n^2+\frac {1}{2}*n^3+\frac {1}{4}*n^4 =\frac {n^2+2n^3+n^4}{4}=\left[ \frac{n(n+1)}{2}\right]^2.$

An other way, not mention there I do the example for power two but you can do the same for all. You just need to know the summation of all powers before.

$$\int_{k}^{k+1} x^2 \mathrm{d}x=k^2+k+\frac{1}{3}$$

Then using summation we have

$$\frac{(n+1)^3}{3}=\int_0^{n+1} x^2 \mathrm{d}x=\sum_{k=0}^n\left(k^2+k+\frac{1}{3}\right)$$

Then use factorisation to find $$\sum_{k=0}^nk^2=\frac{n(n+1)(2n+1)}{6}$$

The sum of the $k$-th powers of numbers $1$ to $n$ can also be derived by means of formal power series. \begin{align*} S_k(n):=\sum_{j=1}^n j^k\qquad\qquad n,k\geq 1 \end{align*} In order to do so we encode for fixed $k$ the sequence $\left(S_k(n)\right)_{n\geq 0}$ by generating functions $$A(z)=\sum_{n=0}^\infty S_k(n)z^n$$

It's convenient to use the coefficient of operator $[z^n]$ to denote the coefficient of $z^n$ of a series. We also use $D_z:=\frac{d}{dz}$ to denote the differential operator. The following is valid:

The sum of the $k$-th powers of numbers $1$ to $n$ is given by \begin{align*} S_k(n)=\sum_{j=1}^nj^k=[z^n]\frac{1}{1-z}(zD_z)^k\frac{1}{1-z}\tag{1} \end{align*}

A detailed derivation of (1) together with some examples can be found in this answer.

Here is an example with $k=4$

Example $S_4(n)$

\begin{align*} S_4(n)=\sum_{j=0}^n j^4&=[z^n]\frac{1}{1-z}(zD_z)^4\frac{1}{1-z}\tag{2}\\ &=[z^n]\frac{z(1+11z+11z^2+z^3)}{(1-z)^6}\\ &=[z^n](z+11z^2+11z^3+z^4)\sum_{j=0}^{\infty}\binom{-6}{j}(-z)^{j}\tag{3}\\ &=\left([z^{n-1}]+11[z^{n-2}]+11[z^{n-3}]+[z^{n-4}]\right)\sum_{j=0}^{\infty}\binom{j+5}{5}z^j\tag{4}\\ &=\binom{n+4}{5}+11\binom{n+3}{5}+11\binom{n+2}{5}+\binom{n+1}{5}\\ &=\frac{1}{30}n(6n^4+15n^3+10n^2-1) \end{align*}

Comment:

• In (2) we apply the operator $\frac{1}{1-z}(zD_z)^4$ to $\frac{1}{1-z}$

• In (3) we use the binomial series expansion

• In (4) we use the linearity of the coefficient of operator, apply the formula \begin{align*} [z^{p-q}]A(z)=[z^p]z^qA(z) \end{align*} and use the binomial identity \begin{align*} \binom{-p}{q}=\binom{p+q-1}{p-1}(-1)^q \end{align*}

• In (5) we select the coefficients of $z^{n-1}$ to $z^{n-4}$.

If you accept that the summation of $p$th powers $\sum_{j=1}^n j^p$ ($p \in {\mathbb N}$) is a polynomial in $n$ of degree $p+1$, then similar to another answer, there is a very easy way to remember how to get the coefficients for the polynomial, especially if you use a computer program like MATLAB, if you are familiar with a little linear algebra (basically, just matrix and vector operations). If your answer polynomial is $\sum_{k=0}^{p+1} c_k n^k$, then you can just plug in $n=0,1,2,\ldots,p+1$ into the original summation formula, and for each value you plug in you will get an equation for a linear combination of the $c_k$. It turns out these linear equations are linearly independent, and in matrix notation what you get is a linear system $Ac = b$ where $c$ is the vector of $p+2$ coefficients $c_k$ you are solving for, and $A$ is the matrix of coefficients you get for your linear equations when plugging in $n$ in between $0$ and $p+1$, and $b$ is the vector of $p+2$ summation values you get when you plug in $n$ between $0$ and $p+1$. Here $Ac$ is standard matrix-vector multiplication. Then provided you know matrix operations, the solution is $c = A^{-1}b$ where $A^{-1}$ is the inverse matrix of $A$ (easy to compute especially with a matrix-friendly computing tool like MATLAB).

Although this is not quite within the traditional scope of pre-calculus material, it might be worthwhile to think about it from a different perspective. Below is the Faulhaber formula: $$\displaystyle \sum_{j=1}^{n}j^{k} = \sum_{i=1}^{k}S(k, i)\binom{n+1}{i+1}i!$$ where $$S(k, i)$$ is the Stirling number of the second kind, which counts the number of ways to partition a set of $$k$$ elements into $$i$$ disjoint, non-empty subsets.

Here's a combinatorial proof of the formula when $$k < n:$$

We will establish this identity by double-counting the number of $$(k+1)$$-tuples $$(x_1, \ldots , x_{k+1})$$ where $$x_{1}, \ldots , x_{k+1} \in [n]= \{1,2, \ldots , n\}$$ and $$x_{k+1}> \max\{x_{i}: 1\leq i \leq k\}.$$ The proof uses only elementary combinatorics.

LHS: divide into cases on the basis of the value of last variable

A natural way to count these $$(k+1)-$$tuples would be to set $$x_{k+1}= j+1$$ for $$1\leq j \leq n$$, which leaves $$j$$ choices for each of $$x_{1}, \ldots x_{k}$$ and hence $$j^{k}$$ such tuples with $$x_{k+1}$$ specified. Summing over the range of $$j$$ covers all possibles values of $$x_{k+1}$$ and hence we end up with the LHS of the above equation.

RHS: divide into cases on the basis of the range of the function x

On the other hand, think of the $$x_{m}$$ as the output of the function $$x: [k+1] \to [n+1].$$ Suppose there are $$i+1$$ distinct values in $$[n+1]$$ taken by the function $$x$$, where $$1\leq i \leq k.$$ This can be fixed in $$\binom{n+1}{i+1}$$ ways. In this scheme, the actual value of $$x_{k+1}$$ is irrelevant, all that we want to fix is the fact that it is the largest value. This forces us to surjectively allocate the remaining $$i$$ values to $$x_{1}, \ldots , x_{k}$$ or in other words count the number of surjective functions from a set of $$k$$ distinguishable objects to a set of $$i$$ distinguishable objects, which is simply $$S(k, i)i!.$$ (This is because each function is uniquely defined by the pre-image of each of the $$i$$ values and the set of pre-images partitions the set $$[k]$$ into $$i$$ disjoint, non-empty subsets of which there are $$S(k, i)$$ many, by definition. Since there are $$i!$$ ways to order these partitions (because the $$i$$-set is distinguishable), we get $$S(k, i)i!.$$

Thus for a fixed value of $$1\leq i \leq k$$, there are $$\displaystyle \binom{n+1}{i+1}S(k, i)i!$$ $$(k+1)-$$tuples $$(x_{1}, \ldots , x_{k+1})$$ such that $$x_{k+1}$$ is the largest of $$i+1$$ values. Summing over the range of $$i$$, we cover all possible sizes of the range, thereby obtaining the RHS.

If you want to see special cases of this formula worked out for small values of $$k$$, take a look at the Enumerative Combinatorics chapter of Arthur Engel's Problem-Solving Strategies.