General Methods for Solving Sums

In this post we work through seven different methods for finding a closed form — a single, compact formula with no summation sign — for the sum of the first $n$ perfect squares. Each method is a general technique that applies far beyond this one example.

A closed form means an exact formula you can evaluate directly. For example, instead of adding up $1 + 4 + 9 + \cdots + n^2$ term by term, we want a formula like $\frac{n(n+1)(2n+1)}{6}$ that gives the answer immediately for any $n$.

We define $\square_n$ as the sum of the squares of all whole numbers from 0 up to $n$:

$$\square_n = \sum_{0 \le k \le n} k^2, \quad \text{for } n \ge 0$$

Table of Small Cases

Before searching for a formula, it helps to compute the first several values by hand. This gives us something to check our formula against.

$n$	1	2	3	4	5	6	7	8	9	10	11	12
$n^2$	1	4	9	16	25	36	49	64	81	100	121	144
$\square_n$	1	5	14	30	55	91	140	204	285	385	506	650

Method 0: Look It Up

The fastest method is simply to look the answer up in a reference. The closed form is:

$$\square_n = \frac{n(n+1)(2n+1)}{6}, \quad \text{for } n \ge 0$$

You can verify this against the table: for $n = 4$, the formula gives $\frac{4 \cdot 5 \cdot 9}{6} = 30$. ✓

Useful references include the CRC Standard Mathematical Tables, Handbook of Mathematical Functions by Abramowitz and Stegun, and the Handbook of Integer Sequences by Sloane. If you have computed enough terms of a sequence and suspect it appears in the literature, Sloane's handbook (now available online as the OEIS) is an excellent place to search.

Method 1: Guess the Answer, Then Prove It by Induction

Mathematical induction is a proof technique where you show: (1) the formula works for the starting case $n = 0$, and (2) if the formula works for $n - 1$, then it also works for $n$. Together, these two steps guarantee the formula works for every whole number.

The closed form $\frac{n(n+1)(2n+1)}{6}$ can be rewritten in an equivalent but slightly more convenient form for the algebra ahead:

$$\square_n = \frac{n\!\left(n+\tfrac{1}{2}\right)\!(n+1)}{3}, \quad \text{for } n \ge 0$$

Base case ($n = 0$):

$$\square_0 = 0 = \frac{0 \cdot \tfrac{1}{2} \cdot 1}{3} = 0 \checkmark$$

Inductive step: We assume the formula holds for $n - 1$, meaning $\square_{n-1} = \frac{(n-1)(n - \frac{1}{2})(n)}{3}$. We need to show it holds for $n$. Using the recurrence $\square_n = \square_{n-1} + n^2$:

$$ \begin{aligned} 3\square_n &= 3\square_{n-1} + 3n^2 \\ &= (n-1)\!\left(n-\tfrac{1}{2}\right)\!n + 3n^2 \\ &= n^3 - \tfrac{3}{2}n^2 + \tfrac{1}{2}n + 3n^2 \\ &= n^3 + \tfrac{3}{2}n^2 + \tfrac{1}{2}n \\ &= n\!\left(n+\tfrac{1}{2}\right)\!(n+1) \end{aligned} $$

Dividing both sides by 3 gives $\square_n = \frac{n(n+\frac{1}{2})(n+1)}{3}$. ✓

Method 2: Perturb the Sum

Perturbation means shifting the sum slightly — replacing every $k$ with $k + 1$ — and then comparing the shifted version to the original. The idea is that the difference between the two reveals information about $\square_n$.

Step 1: Find the sum of the first $n$ integers as a warmup

Let $T_n = \sum_{0 \le k \le n} k = 0 + 1 + 2 + \cdots + n$. Shifting every $k$ to $k+1$:

$$ T_n + (n+1) = \sum_{0 \le k \le n} (k+1) = \sum_{0 \le k \le n} k + \sum_{0 \le k \le n} 1 = T_n + (n+1) $$

That's circular. Instead, compare $\square_n$ shifted to get $T_n$. After cancellation, we find:

$$2T_n = (n+1)^2 - (n+1) = n(n+1) \implies T_n = \frac{n(n+1)}{2}$$

Step 2: Perturb using cubes to find $\square_n$

Let $\blacksquare_n = \sum_{0 \le k \le n} k^3$. Shifting every $k$ to $k+1$ and expanding $(k+1)^3 = k^3 + 3k^2 + 3k + 1$:

$$ \blacksquare_n + (n+1)^3 = \sum_{0 \le k \le n}(k+1)^3 = \blacksquare_n + 3\square_n + 3\cdot\frac{n(n+1)}{2} + (n+1) $$

The $\blacksquare_n$ terms cancel, leaving:

$$ (n+1)^3 = 3\square_n + \frac{3n(n+1)}{2} + (n+1) $$

Solving for $3\square_n$:

$$ \begin{aligned} 3\square_n &= (n+1)^3 - \frac{3(n+1)n}{2} - (n+1) \\ &= (n+1)\!\left(n^2 + 2n + 1 - \tfrac{3}{2}n - 1\right) \\ &= (n+1)\!\left(n+\tfrac{1}{2}\right)\!n \end{aligned} $$

Therefore:

$$\square_n = \frac{n\!\left(n+\tfrac{1}{2}\right)\!(n+1)}{3} \checkmark$$

Method 3: Build a Repertoire

The repertoire method solves a recurrence by finding a family of solutions and combining them. We set up a general recurrence with unknown constants, solve it for simple cases, and read off the answer.

We define a general sequence $R_n$ satisfying:

$$ R_0 = \alpha, \qquad R_n = R_{n-1} + \beta + \gamma n + \delta n^2 \quad \text{for } n > 0 $$

The key insight is that the solution $R_n$ must be a linear combination of four coefficient functions $A(n)$, $B(n)$, $C(n)$, $D(n)$ — one for each free constant:

$$R_n = A(n)\alpha + B(n)\beta + C(n)\gamma + D(n)\delta$$

We find $B(n)$, $C(n)$, and $D(n)$ by plugging in simple known sequences. We already know $B(n) = n$ (constant recurrence) and $C(n) = \frac{n(n+1)}{2}$ (from $T_n$). To find $D(n)$, we plug in $R_n = n^3$, which satisfies the recurrence with $\alpha = 0$, $\beta = 1$, $\gamma = -3$, $\delta = 3$:

$$3D(n) - 3C(n) + B(n) = n^3$$

Now we connect this to $\square_n$. Since $\square_n$ satisfies $\square_n = \square_{n-1} + n^2$, it corresponds to $\alpha = \beta = \gamma = 0$ and $\delta = 1$, so $\square_n = D(n)$. Solving:

$$ 3\square_n = 3D(n) = n^3 + 3C(n) - B(n) = n^3 + \frac{3n(n+1)}{2} - n = n\!\left(n+\tfrac{1}{2}\right)\!(n+1) $$ $$\square_n = \frac{n\!\left(n+\tfrac{1}{2}\right)\!(n+1)}{3} \checkmark$$

Method 4: Replace Sums by Integrals

This method uses geometry to get an approximation first, then corrects the error precisely.

The approximation

$\square_n$ is the total area of $n$ rectangles, each 1 unit wide, with heights $0^2, 1^2, 2^2, \ldots, n^2$. These rectangles sit under the smooth curve $f(x) = x^2$, so $\square_n$ is approximately equal to the area under that curve from 0 to $n$:

$$\int_{0}^{n} x^2\, dx = \frac{n^3}{3}$$

So $\square_n \approx \frac{1}{3}n^3$.

Measuring the error exactly

Let $E_n = \square_n - \frac{1}{3}n^3$ be the difference between the sum and the approximation. Using the recurrence $\square_n = \square_{n-1} + n^2$:

$$ \begin{aligned} E_n &= \square_n - \tfrac{1}{3}n^3 \\ &= \square_{n-1} + n^2 - \tfrac{1}{3}n^3 \\ &= E_{n-1} + \tfrac{1}{3}(n-1)^3 + n^2 - \tfrac{1}{3}n^3 \\ &= E_{n-1} + n - \tfrac{1}{3} \end{aligned} $$

We can also express this geometrically. Each rectangle overshoots the curve by a sliver. The total overshoot is:

$$ \square_n - \int_{0}^{n} x^2\, dx = \sum_{k=1}^{n}\left(k^2 - \int_{k-1}^{k} x^2\, dx\right) = \sum_{k=1}^{n}\left(k^2 - \frac{k^3 - (k-1)^3}{3}\right) = \sum_{k=1}^{n}\left(k - \frac{1}{3}\right) $$

This error sum $\sum_{k=1}^{n}(k - \frac{1}{3})$ can be evaluated using $T_n = \frac{n(n+1)}{2}$:

$$E_n = \frac{n(n+1)}{2} - \frac{n}{3} = \frac{n^2}{2} + \frac{n}{6}$$

Adding back the approximation gives the exact answer:

$$\square_n = \frac{n^3}{3} + \frac{n^2}{2} + \frac{n}{6} = \frac{2n^3 + 3n^2 + n}{6} = \frac{n(n+1)(2n+1)}{6} \checkmark$$

Method 5: Expand and Contract

This method replaces the original single sum with a double sum that is easier to manipulate, then collapses it back down.

The key observation is that $k^2 = k \cdot k$, and we can write $k$ as a sum of $k$ ones: $k = \sum_{1 \le j \le k} 1$. Multiplying gives $k^2 = \sum_{1 \le j \le k} k$. Substituting into $\square_n$:

$$ \square_n = \sum_{1 \le k \le n} k^2 = \sum_{1 \le j \le k \le n} k $$

Now swap the order of summation — sum on $j$ last instead of first:

$$ = \sum_{1 \le j \le n} \sum_{j \le k \le n} k $$

The inner sum $\sum_{j \le k \le n} k = j + (j+1) + \cdots + n$ is an arithmetic series with first term $j$, last term $n$, and $(n - j + 1)$ terms. Its value is $\frac{j + n}{2}(n - j + 1)$:

$$ = \sum_{1 \le j \le n} \frac{j+n}{2}(n-j+1) $$

Expanding the product $(j+n)(n-j+1) = n(n+1) - j^2 + j$:

$$ = \frac{1}{2} \sum_{1 \le j \le n} \left(n(n+1) + j - j^2\right) $$

Splitting and evaluating each piece using $T_n = \frac{n(n+1)}{2}$ and $\square_n$:

$$ = \frac{1}{2}\left(n^2(n+1) + \frac{n(n+1)}{2} - \square_n\right) $$

This gives an equation with $\square_n$ on both sides. Moving the $\square_n$ term to the left:

$$ \square_n + \frac{1}{2}\square_n = \frac{1}{2}n^2(n+1) + \frac{1}{4}n(n+1) $$ $$ \frac{3}{2}\square_n = \frac{1}{2}n\!\left(n+\tfrac{1}{2}\right)\!(n+1) $$ $$\square_n = \frac{n\!\left(n+\tfrac{1}{2}\right)\!(n+1)}{3} \checkmark$$

Method 6: Use Finite Calculus

Coming soon.

Method 7: Use Generating Functions

Coming soon.

Raell Dottin's Technical Blog

Search This Blog