# Sum of n, n², or n³

Let \(a\) and \(n\) be positive integers. The sum \(\sum\limits_{k=1}^n k^a\) comes up quite often in various mathematical contexts. In particular, the case \(a=1,n=100\) is famously said to have been solved by Gauss as a young schoolboy: the sum of the first \(100\) positive integers is \(5050.\)

In fact, there is a closed-form formula for each of these series; the first few are as follows:

\[\begin{align} \sum_{k=1}^n k &= \frac{n(n+1)}2 \\ \sum_{k=1}^n k^2 &= \frac{n(n+1)(2n+1)}6 \\ \sum_{k=1}^n k^3 &= \frac{n^2(n+1)^2}4. \end{align}\]

While these particular sums are quite useful, the natural question is how this collection of results generalizes to any exponent \(a.\) This question is answered quite neatly by a formula called *Faulhaber's formula,* which gives an explicit computation for the sum for any \(a.\)

More generally, manipulations of these sums yield useful results in areas including string theory, quantum mechanics, and complex numbers.

#### Contents

## Sum of First \(n\) Positive Integers

Let \(S_n = 1+2+3+4+\cdots +n = \displaystyle \sum_{k=1}^n k.\) The elementary trick for solving this equation (which Gauss is supposed to have used as a child) is a rearrangement of the sum as follows:

\[\begin{eqnarray} S_n & = & 1 & + & 2 & + & 3 & + \cdots + & n \\ S_n & = & n & + & n-1 & + & n-2 & + \cdots + & 1 .\\ \end{eqnarray}\]

Grouping and adding the above two sums gives

\[\begin{eqnarray} 2S_n & = & (1+n)+(2+n-1)+(3+n-2) + \cdots + (n+1) \\ & = & \underbrace{(n+1)+(n+1)+(n+1)+\cdots+(n+1)}_{n\ \text{times}} \\ & = & n(n+1). \end{eqnarray}\]

Therefore,

\[S_n = \dfrac{n(n+1)}{2}.\]

Find the sum of the first \(100\) positive integers.

Plugging \(n=100\) in our equation, \[1+2+3+4+\dots + 100 = \frac{100(101)}{2} = \frac{10100}{2},\] which implies our final answer is 5050. \( _\square \)

Show that the sum of the first \(n\) positive odd integers is \(n^2.\)

There are several ways to solve this problem. One way is to view the sum as the sum of the first \(2n\) integers minus the sum of the first \(n\) even integers. The sum of the first \(n\) even integers is \(2\) times the sum of the first \(n\) integers, so putting this all together gives

\[\frac{2n(2n+1)}2 - 2\left( \frac{n(n+1)}2 \right) = n(2n+1)-n(n+1) = n^2.\]

Even more succinctly, the sum can be written as

\[\sum_{k=1}^n (2k-1) = 2\sum_{k=1}^n k - \sum_{k=1}^n 1 = 2\frac{n(n+1)}2 - n = n^2.\ _\square\]

In a similar vein as the previous exercise, here is another way of deriving the formula for the sum of the first \(n\) positive integers. Start with the identity

\[k^2-(k-1)^2 = 2k-1.\]

Now sum both sides:

\[\sum_{k=1}^n \big(k^2-(k-1)^2\big) = 2 \sum_{k=1}^n k - \sum_{k=1}^n 1.\]

The left sum telescopes: it equals \(n^2.\) The right side equals \(2S_n - n,\) which gives \(2S_n - n = n^2,\) so \(S_n = \frac{n(n+1)}2.\)

This technique generalizes to a computation of any particular power sum one might wish to compute.

## Sum of the Squares of First \(n\) Positive Integers

Continuing the idea from the previous section, start with the identity

\[k^3-(k-1)^3=3k^2-3k+1.\]

As before, summing the left side from \(k=1\) to \(n\) yields \(n^3.\) This gives

\[\begin{align} n^3 &= 3 \left( \sum_{k=1}^n k^2 \right) - 3 \sum_{k=1}^n k + \sum_{k=1}^n 1 \\ n^3 &= 3 \left( \sum_{k=1}^n k^2 \right) - 3 \frac{n(n+1)}2 + n \\ 3 \left( \sum_{k=1}^n k^2 \right) &= n^3 + 3 \frac{n(n+1)}2 - n \\ \Rightarrow \sum_{k=1}^n k^2 &= \frac13 n^3 + \frac12 n^2 + \frac16 n \\&= \frac{n(n+1)(2n+1)}6. \end{align}\]

Find the sum of the squares of the first \(100\) positive integers.

Plugging in \(n=100,\)

\[1^2+2^2+3^2+4^2+\dots + 100^2 = \frac{100(101)(201)}{6} = \frac{2030100}{6} = 338350.\ _\square\]

## Sum of the Cubes of First \(n\) Positive Integers

Again, start with the identity

\[k^4-(k-1)^4=4k^3-6k^2+4k-1.\]

Sum from \(1\) to \(n\) to get

\[n^4 = 4 s_{3,n} - 6 s_{2,n} + 4 s_{1,n} - n.\]

Here \(s_{a,n}\) is the sum of the first \(n\) \(a^\text{th}\) powers. So

\[\begin{align} 4s_{3,n} &= n^4 + 6 \frac{n(n+1)(2n+1)}6 - 4 \frac{n(n+1)}2 + n \\\\ s_{3,n} &= \frac14 n^4 + \frac12 n^3 + \frac34 n^2 + \frac14 n - \frac12 n^2 - \frac12 n + \frac14 n \\\\ s_{3,n} &= \frac14 n^4 + \frac12 n^3 + \frac14 n^2 \\\\ &= \frac{n^2(n+1)^2}4. \end{align}\]

Find the sum of the cubes of the first \(100\) positive integers.

Plugging \(n=100\) in our equation, \[1^3+2^3+3^3+4^3+\dots + 100^3 = \frac{100^2\big(101^2\big)}{4} = \frac{102010000}{4} = 25502500.\ _\square\]

## Generalizations

As in the previous section, let \(s_{a,n} = \sum\limits_{k=1}^n k^a.\) Then the relevant identity, derived in the same way as for sums of squares and cubes, is

\[n^{a+1} = \binom{a+1}1 s_{a,n} - \binom{a+1}2 s_{a-1,n} + \binom{a+1}3 s_{a-2,n} - \cdots + (-1)^{a-1} \binom{a+1}{a} s_{1,n} + (-1)^a n.\]

This recursive identity gives a formula for \(s_{a,n}\) in terms of \(s_{b,n}\) for \(b < a.\) It is the basis of many inductive arguments. In particular, the first pattern that one notices after deriving \(s_{a,n}\) for \(a=1,2,3\) is the leading terms \(\frac12 n^2, \frac13 n^3, \frac14 n^4.\) Here is an easy argument that the pattern continues:

For a positive integer \(a,\) \(s_{a,n}\) is a polynomial of degree \(a+1\) in \(n.\) Its leading term is \(\frac1{a+1} n^{a+1}.\)

Induction. The statement is true for \(a=1,\) and now suppose it is true for all positive integers less than \(a.\) Then solve the above recurrence for \(s_{a,n}\) to get

\[s_{a,n} = \frac1{a+1} n^{a+1} + c_{a-1} s_{a-1,n} + c_{a-2} s_{a-2,n} + \cdots + c_1 s_{1,n} + c_0 n,\]

where the \(c_i\) are some rational numbers.

Now by the inductive hypothesis, all of the terms except for the first term are polynomials of degree \(\le a\) in \(n,\) so the statement follows. \(_\square\)

Note the analogy to the continuous version of the sum: the integral \(\int_0^n x^a \, dx = \frac1{a+1}n^{a+1}.\) The lower-degree terms can be viewed as error terms in the approximation of the area under the curve \(y=x^a\) by the rectangles of width \(1\) and height \(k^a.\)

## Faulhaber's Formula

Having established that \(s_{a,n} = \frac1{a+1} n^{a+1} +\text{(lower terms)},\) the obvious question is whether there is an explicit expression for the lower terms. It turns out that the terms can be expressed quite concisely in terms of the Bernoulli numbers, as follows:

Faulhaber's Formula:\[ \sum_{k=1}^n k^a = \frac1{a+1} \sum_{j=0}^{a} (-1)^j \binom{a+1}{j} B_j n^{a+1-j}. \]

That is, if \(i=a+1-j\) is a positive integer, the coefficient of \(n^i\) in the polynomial expression for the sum is \(\dfrac{(-1)^{a+1-i}}{a+1} \binom{a+1}{i} B_{a+1-i}.\)

Show that \(\sum\limits_{k=1}^n k^a = \frac1{a+1} n^{a+1} + \frac12 n^a + (\text{lower terms}).\)

This can be read off directly from Faulhaber's formula: the \(j=0\) term is \(\frac1{a+1}n^{a+1},\) and the \(j=1\) term is

\[\frac1{a+1} (-1)^1 \binom{a+1}1 B_1 n^a,\]

and since \(B_1 = -\frac12,\) this simplifies to \(\frac12 n^a.\) \(_\square\)

To compute \(\sum\limits_{k=1}^n k^4\) using Faulhaber's formula, write

\[ \sum_{k=1}^n k^4 = \frac15 \sum_{j=0}^4 (-1)^j \binom{5}{j} B_j n^{5-j} \]

and use \(B_0 = 1, B_1 = -\frac12, B_2 = \frac16, B_3 = 0, B_4 = -\frac1{30}\) to get

\[ \sum_{k=1}^n k^4 = \frac15 \left( n^5 + \frac52 n^4 + \frac{10}6 n^3 + 0 n^2 - \frac16 n\right) = \frac15 n^5 + \frac12 n^4 + \frac13 n^3 - \frac16 n. \]

This happens to factor as

\[ \sum_{k=1}^n k^4 = \frac{n(n+1)(2n+1)(3n^2+3n-1)}{30}. \]

Note that the \((-1)^j\) sign only affects the term when \(j=1,\) because the odd Bernoulli numbers are zero except for \(B_1 = -\frac12.\)

The proof of the theorem is straighforward (and is omitted here); it can be done inductively via standard recurrences involving the Bernoulli numbers, or more elegantly via the generating function for the Bernoulli numbers.

## See Also

**Cite as:**Sum of n, n², or n³.

*Brilliant.org*. Retrieved from https://brilliant.org/wiki/sum-of-n-n2-or-n3/