Three finite sums come up so often in a counting argument that they're worth having memorized as fixed formulas: the sum of the first n integers, the sum of the first n squares, and a finite geometric sum. Section 7's manipulation tools are what turn a messier sum into one of these three shapes.
Formula
Sum of the First n Squares
also known as: 1^2 + 2^2 + ... + n^2
Induct on n. The base case n=1 gives 1 = \frac{1\cdot2\cdot3}{6}, true. Assume the formula holds for n=k. Then \sum_{i=1}^{k+1} i^2 = \frac{k(k+1)(2k+1)}{6} + (k+1)^2 = (k+1)\left[\frac{k(2k+1)}{6}+(k+1)\right] = (k+1)\cdot\frac{2k^2+7k+6}{6} = \frac{(k+1)(k+2)(2k+3)}{6}, which is the formula at n=k+1. By induction the formula holds for every n \geq 1.
Each formula is a shortcut for one repeated pattern. Plain counting numbers, squared counting numbers, or a constant ratio between consecutive terms. Spotting which pattern a sum matches is the real skill. The formula itself is just a lookup once that pattern is found. That lookup costs the same one calculation whether n is 5 or a million. That's the entire reason a closed form beats adding the numbers by hand.
A closed form for a sum is a single formula that evaluates it directly from n, with no term-by-term addition required, no matter how large n gets. \sum_{i=1}^n i = \frac{n(n+1)}{2} and \sum_{i=1}^n i^2 = \frac{n(n+1)(2n+1)}{6} both close a sum whose upper limit is a variable n this way. A finite geometric sum \sum_{i=0}^{n} r^i = \frac{r^{n+1}-1}{r-1} (for r \neq 1) closes the same way for multiplicative growth instead of additive. Recognizing which of these three shapes a manipulated sum has become is exactly the payoff Section 7's splitting and shifting earn — the manipulation is only worth doing once it lands on a shape one of these three formulas already closes. None of the three needs n to be small: evaluating the closed form at n=1{,}000{,}000 costs exactly the same one substitution as evaluating it at n=5, which is the entire point of finding one in the first place.
Formula
Sum of a Finite Arithmetic Series
also known as: the Gauss pairing formula
Recalled from College Algebra · Series and the Binomial Theorem — first taught there.
For an arithmetic sequence with first term a_1, common difference d, and nth term a_n, S_n = \frac{n}{2}\left(a_1 + a_n\right) = \frac{n}{2}\bigl(2a_1 + (n-1)d\bigr).
Formula
Sum of a Finite Geometric Series
also known as: the finite geometric series formula
Recalled from College Algebra · Series and the Binomial Theorem — first taught there.
For a geometric sequence with first term a_1 and common ratio r \neq 1, S_n = \sum_{k=1}^{n} a_1 r^{\,k-1} = a_1\,\frac{1 - r^{\,n}}{1 - r}.
The sum of the first n odd numbers is n squared
Click along the diagonal and compare each row's alternating pattern to the running total of odd numbers.
Loading interactive…
Worked example
Closing a sum of squares
-
1
Evaluate 1^2+2^2+3^2+4^2+5^2 using the closed form rather than adding by hand.
-
2
Apply \sum_{i=1}^{n} i^2 = \frac{n(n+1)(2n+1)}{6} with n=5.
-
3
\frac{5 \cdot 6 \cdot 11}{6} = \frac{330}{6}.
-
4\boxed{55}
Direct addition confirms it: 1+4+9+16+25=55.
Loading interactive…
Worked example
Closing a finite geometric sum
-
1
Evaluate \sum_{i=0}^{5} 2^i using the closed form.
-
2
This is a finite geometric sum with ratio r=2 and 6 terms (i=0 through 5).
-
3
Apply \sum_{i=0}^{n} r^i = \frac{r^{n+1}-1}{r-1} with r=2, n=5: \frac{2^{6}-1}{2-1}.
-
4\boxed{63}
Loading interactive…
Where this goes next
Algorithm analysis
Counting the total number of comparisons a nested loop performs is routinely a sum of the first n integers in disguise — a loop whose inner pass shrinks by one each outer iteration sums to \frac{n(n+1)}{2} comparisons, the exact reason such an algorithm is described as running in "quadratic time": the closed form's leading term is \frac{n^2}{2}.
Check your understanding (counts toward your progress)
Evaluate sum_{i=1}^{5} (i^2 + i).
Right on try — credit. Right — the answer had already been shown, so no credit this time. Next try is worth Answer shown after three tries — this one no longer earns credit. You chose to see the answer — this one earns no credit.
Why
sum(i^2) for n=5 is 55; sum(i) for n=5 is 15; 55+15=70.
Correct answer
Also accepted:
Why
Split the sum into sum(i^2) and sum(i) first, applying each closed form separately with n=5.
Add the two separately-computed closed-form results together for the final total.
Evaluate \sum_{i=1}^{23} i^2 using the closed form.
Right on try — credit. Right — the answer had already been shown, so no credit this time. Next try is worth Answer shown after three tries — this one no longer earns credit. You chose to see the answer — this one earns no credit.
Why
\dfrac{n(n+1)(2n+1)}{6} with n=23: \dfrac{23\cdot24\cdot47}{6} = 4324.
Correct answer
Also accepted:
Why
Evaluate sum_{i=1}^{10} i using the closed form.
Right on try — credit. Right — the answer had already been shown, so no credit this time. Next try is worth Answer shown after three tries — this one no longer earns credit. You chose to see the answer — this one earns no credit.
Why
n(n+1)/2 with n=10: 10*11/2 = 55.
Correct answer
Also accepted:
Why
A student evaluates sum_{i=1}^{n} (i^2 + i) as n(n+1)(2n+1)/6 alone, ignoring the +i piece. What's the fix?
Right on try — credit. Right — the answer had already been shown, so no credit this time. Next try is worth Answer shown after three tries — this one no longer earns credit. You chose to see the answer — this one earns no credit.
Why
sum(i^2+i) = sum(i^2) + sum(i) -- both closed forms are needed and added together, not just the squares piece alone.
Recall that a sum of a two-term expression can be split into two separate sums added together, each with its own closed form.
After splitting sum(i^2+i) into sum(i^2) and sum(i), which named closed form handles each piece?
A loop's comparison count follows sum_{i=1}^{n} i with n=100. How many total comparisons run?
Right on try — credit. Right — the answer had already been shown, so no credit this time. Next try is worth Answer shown after three tries — this one no longer earns credit. You chose to see the answer — this one earns no credit.
Why
n(n+1)/2 with n=100: 100*101/2=5050 -- the classic quadratic-time comparison count.
Correct answer
Also accepted:
Why
Recognize this as the sum of the first n integers, with n=100 -- a shape this chapter already gave a closed form for.
Apply the arithmetic-series closed form n(n+1)/2 directly with n=100.
A finite geometric sum sum_{i=0}^{n} r^i uses the formula (r^{n+1}-1)/(r-1). What restriction applies?
Right on try — credit. Right — the answer had already been shown, so no credit this time. Next try is worth Answer shown after three tries — this one no longer earns credit. You chose to see the answer — this one earns no credit.
Why
The formula's denominator is r-1; when r=1 every term is already 1 and the sum is simply n+1, computed separately.
Check what happens to the formula's denominator r-1 at one specific value of r.
Evaluate sum_{i=0}^{4} 3^i using the finite geometric closed form.
Right on try — credit. Right — the answer had already been shown, so no credit this time. Next try is worth Answer shown after three tries — this one no longer earns credit. You chose to see the answer — this one earns no credit.
Why
(3^5 - 1)/(3 - 1) = 242/2 = 121.
Correct answer
Also accepted:
Why
Which closed form applies to sum_{i=1}^{n} i^2 directly, with no manipulation needed first?
Right on try — credit. Right — the answer had already been shown, so no credit this time. Next try is worth Answer shown after three tries — this one no longer earns credit. You chose to see the answer — this one earns no credit.
Why
The sum of squares has its own closed form; the summand already matches i^2 exactly, no rewriting needed.
Match the summand i^2 directly against the form each named closed form was built for, with no rewriting first.
Practice: Applying finite-sum closed forms (5 problems · doesn’t affect your progress)
A sum's terms increase by a constant amount each step (like 3, 7, 11, 15, ...). Which closed form applies?
Right on try — credit. Right — the answer had already been shown, so no credit this time. Next try is worth Answer shown after three tries — this one no longer earns credit. You chose to see the answer — this one earns no credit.
Sum-of-squares is for terms shaped like i^2, not a constant step between consecutive terms.
Geometric growth is a constant RATIO between terms, not a constant difference.
A constant difference between terms is exactly the arithmetic-sequence signature this closed form is built for -- no term-by-term addition needed.
Why
A constant difference between consecutive terms (here, +4 each time) is the arithmetic-sequence signature; the arithmetic series closed form applies directly.
The arithmetic series formula
Evaluate sum_{i=1}^{10} i using the closed form.
Right on try — credit. Right — the answer had already been shown, so no credit this time. Next try is worth Answer shown after three tries — this one no longer earns credit. You chose to see the answer — this one earns no credit.
Why
n(n+1)/2 with n=10: 10*11/2 = 55.
Correct answer
Also accepted:
Why
Evaluate sum_{i=0}^{4} 3^i using the finite geometric closed form.
Right on try — credit. Right — the answer had already been shown, so no credit this time. Next try is worth Answer shown after three tries — this one no longer earns credit. You chose to see the answer — this one earns no credit.
Why
(3^5 - 1)/(3 - 1) = 242/2 = 121.
Correct answer
Also accepted:
Why
Evaluate sum_{i=1}^{6} i^2 using the sum-of-squares closed form.
Right on try — credit. Right — the answer had already been shown, so no credit this time. Next try is worth Answer shown after three tries — this one no longer earns credit. You chose to see the answer — this one earns no credit.
Why
n(n+1)(2n+1)/6 with n=6: 6713/6 = 91.
Correct answer
Also accepted:
Why
Apply n(n+1)(2n+1)/6 directly with n=6, rather than adding six squares term by term.
Combine the sum-of-squares and arithmetic-series closed forms to evaluate sum_{i=1}^{6} (2i^2 - i).
Right on try — credit. Right — the answer had already been shown, so no credit this time. Next try is worth Answer shown after three tries — this one no longer earns credit. You chose to see the answer — this one earns no credit.
Why
sum(i^2) for n=6 is 91, so sum(2i^2)=182; sum(i) for n=6 is 21. 182 - 21 = 161.
Correct answer
Also accepted:
Why
Split the sum into 2*sum(i^2) and sum(i) first, each with its own closed form at n=6.
Compute each closed-form piece separately, then subtract, keeping track of the coefficient of 2 on the squares piece.