Sigma Notation and Finite Sums

Part 17, Chapter 17: Mathematical Induction and Summation

Learning objectives

Evaluate sums using standard summation formulas
Apply linearity of summation
Recognize and evaluate telescoping sums
Manipulate summation indices

Adding up a hundred numbers by hand is a punishment; adding up a billion is impossible. Mathematics needs closed-form expressions for sums, formulas that take the upper index $n$ and produce the total in one calculation. This section assembles the standard ones, shows where they come from, and introduces a magic-trick technique called telescoping that collapses huge sums to two terms.

Sigma notation, briefly

The expression $\sum_{k=1}^{n} a_k$ , a summation, means $a_1 + a_2 + \cdots + a_n$ . The letter $k$ is the dummy index, you can rename it without changing the value. The bottom and top of the sigma fix the range; $n$ is the only variable that escapes.

The four standard formulas

These are the building blocks. Memorise the first three. The fourth is striking enough that you will remember it after one look.

$\sum_{k=1}^{n} 1 = n, \qquad \sum_{k=1}^{n} k = \frac{n(n+1)}{2}, \qquad \sum_{k=1}^{n} k^2 = \frac{n(n+1)(2n+1)}{6}, \qquad \sum_{k=1}^{n} k^3 = \left(\frac{n(n+1)}{2}\right)^2.$ fracn(n+1)2,qquadsumk=1nk2=fracn(n+1)(2n+1)6,qquadsumk=1nk3=left(fracn(n+1)2right)2.

The last identity is one of the most beautiful in elementary mathematics: the sum of the first $n$ cubes equals the square of the sum of the first $n$ integers. Each formula can be proved by induction; the previous section showed exactly how.

Where this shows up

Statistics: The sample mean $\bar{x} = \tfrac{1}{n}\sum x_i$ i and sample variance $s^2 = \tfrac{1}{n-1}\sum (x_i - \bar{x})^2$ i−barx)2 are both sums you will evaluate every day if you do any data work.
Numerical Integration: Trapezoidal and Simpson's rule approximate $\int f(x)\,dx$ by $\sum w_i f(x_i)$ ; telescoping sums (Euler-Maclaurin formula) give the error bound for these schemes.
Algorithms: Loop runtime is a sum: a for i in 1..n doing $O(i)$ work per iteration runs in $\sum_{i=1}^n O(i) = O(n^2)$ i=1nO(i)=O(n2) time, the closed-form summation formula is the analysis.

(Set the mode to Arithmetic (an arithmetic sequence), leave $a = 1$ and $d = 1$ , and slide $N$ . The partial-sum line tracks the formula $\frac{n(n+1)}{2}$ exactly. Change $d$ to $2$ and the bars become odd numbers; the partial sums become $1, 4, 9, 16, \ldots$ , perfect squares. That is $\sum (2k-1) = n^2$ shown geometrically.)

Linearity

Summation distributes over addition and pulls out constants:

$\sum_{k=1}^{n} \bigl( a f(k) + b g(k) \bigr) = a \sum_{k=1}^{n} f(k) + b \sum_{k=1}^{n} g(k).$ k=1nbigl(af(k)+bg(k)bigr)=asumk=1nf(k)+bsumk=1ng(k).

So a complicated sum like $\sum_{k=1}^{n} (3k^2 - 2k + 1)$ k=1n(3k2−2k+1) collapses into three known pieces, just apply linearity, then plug into the standard formulas. The arithmetic is mechanical; the work is choosing how to decompose.

Telescoping, when the middle vanishes

A telescoping sum is one where adjacent terms cancel. The cleanest example is $\sum_{k=1}^{n}\bigl(\tfrac{1}{k} - \tfrac{1}{k+1}\bigr)$ k=1nbigl(tfrac1k−tfrac1k+1bigr). Write it out:

$\Bigl(1 - \tfrac{1}{2}\Bigr) + \Bigl(\tfrac{1}{2} - \tfrac{1}{3}\Bigr) + \Bigl(\tfrac{1}{3} - \tfrac{1}{4}\Bigr) + \cdots + \Bigl(\tfrac{1}{n} - \tfrac{1}{n+1}\Bigr).$

Every interior term appears once with a plus sign and once with a minus sign, they cancel. Only the very first $(1)$ and the very last $(-\tfrac{1}{n+1})$ survive, so the whole sum collapses to $1 - \tfrac{1}{n+1} = \tfrac{n}{n+1}$ .

The trick to recognising a telescope: rewrite the summand as a difference $T_k - T_{k+1}$ . Often partial fractions do this work for you, for example, $\tfrac{1}{k(k+1)} = \tfrac{1}{k} - \tfrac{1}{k+1}$ .

Shifting the index

You can rename or shift the dummy variable, just as you can with the variable of integration. Substituting $j = k-1$ gives $\sum_{k=1}^{n} f(k) = \sum_{j=0}^{n-1} f(j+1)$ 1). The result is the same number; only the labels move. This is exactly how you align two sums whose ranges look different but whose contents overlap.

Try it

Predict first: what does the geometric series $1 + 1/2 + 1/4 + \cdots$ sum to? Switch to Geometric mode with $a = 1$ and $r = 0.5$ , and watch the partial sum climb toward your prediction as $N$ grows.
Use linearity to compute $\sum_{k=1}^{8} (4k^3 - k^2)$ k=18(4k3−k2) on paper. Compare against direct summation in the widget by setting the right side modes.
Verify $\sum_{k=1}^{10}\tfrac{1}{k(k+1)} = \tfrac{10}{11}$ k=110tfrac1k(k+1)=tfrac1011 by partial-fractioning the summand and telescoping.
Show that $\sum_{k=1}^{n}(2k-1) = n^2$ k=1n(2k−1)=n2 in two ways: (i) by induction, (ii) using $\sum k$ and linearity.

Pause: linearity tells you $\sum (a f(k)) = a \sum f(k)$ . Can you also pull a function of $k$ , say $k$ itself, out of the sigma? Why not?

Try it in code

A trap to watch for

The most common error: writing $\sum_{k=1}^{n} f(k) \cdot g(k) = \bigl(\sum f(k)\bigr)\bigl(\sum g(k)\bigr)$ k=1nf(k)cdotg(k)=bigl(sumf(k)bigr)bigl(sumg(k)bigr). Summation does not distribute over multiplication. Try the smallest test: $\sum_{k=1}^{2} k \cdot k = 1 + 4 = 5$ k=12kcdotk=1+4=5, whereas $(1 + 2)(1 + 2) = 9$ . The two are not equal, sigma is linear, not multiplicative.

A second trap: telescoping looks like it leaves nothing behind, but it always leaves two leftover terms, the first and the last. Beginners write the answer as just $1$ , missing the $-\tfrac{1}{n+1}$ . Always write out three or four terms before collapsing.

What you now know

You can evaluate the four standard sums in closed form, use linearity to split mixed expressions, recognise a telescoping pattern, and shift indices to align ranges. The next section turns to geometric series, sums of the form $a + ar + ar^2 + \cdots$ , where the same techniques deliver the most useful formula in all of elementary analysis: $\sum_{k=0}^{\infty} r^k = \tfrac{1}{1-r}$ k=0inftyrk=tfrac11−r for $|r| < 1$ .

Quick check

Mark section complete →

References

Lang, S. (1971). Basic Mathematics. Springer. Chapter 16, §2, the four standard formulas with inductive derivations.
Spivak, M. (1994). Calculus (3rd ed.). Publish or Perish. Chapter 2: sigma notation and the first taste of summation by induction.
Knuth, D. E.; Graham, R. L.; Patashnik, O. (1994). Concrete Mathematics (2nd ed.). Addison-Wesley. Chapter 2: the definitive treatment of finite sums, with telescoping as a recurring theme.
Velleman, D. J. (2006). How to Prove It (2nd ed.). Cambridge University Press. §6.3, how to prove a summation identity by induction.