Math 750 — Review of Summation Notation


As its name suggests, Summatation Notation is designed as a quick way to describe sums. For example, if we want to write the sum of the first 5 squares, \[ 1^2+2^2+3^2+4^2+5^2, \] summation notation allows us to write it as \[ \sum_{k=1}^5 k^2. \] More generally, \[ \sum_{k=a}^b (\text{some function of $k$}) \] means that we evaluate the function at $k=a$, and then at $k=a+1$, etc., until we reach $k=b$, and then we add all the values together. Formally, \[ \sum_{k=a}^b F(k) = F(a)+F(a+1)+\cdots+F(b-1)+F(b). \] For example, \[ \sum_{k=2}^8 3^k = 3^2+3^3+3^4+3^5+3^6+3^7+3^8 = 9837. \]

Side Note How did I compute this sum? The hard way would be to multiply out the powers and add them. Much easier is to use the geometric sum formula \[ \sum_{k=0}^n x^k = 1+x+x^2+\cdots+x^n = \frac{x^{n+1}-1}{x-1}, \quad\text{which lets us compute}\quad \sum_{k=2}^8 3^k = 3^2\cdot (1+3+3^2+3^3+3^4+3^5+3^6) = 9\cdot\frac{3^7-1}{3-1} = 9837. \] And if you don't think that this is easier, try the same problem (without using a calculator), but with $k$ running from $2$ to $80$.

As another example, consider the following interesting formula from Corollary 1.13 involving a sum of binomial coefficients $\binom{n}{k}=\frac{n!}{k!(n-k)!}$: \[ 2^n = \binom{n}{0}+\binom{n}{1}+\cdots+\binom{n}{n-1}+\binom{n}{n}. \] This formula can be succinctly written using summation notation as \[ 2^n = \sum_{k=0}^n \binom{n}{k}. \]

We can use summation notation to describe more complicated sums. For example, suppose that we want to write down the sum of the squares of the numbers 2, 3, 5, 7, and 11. This can be written as \[ \sum_{n\in\{2,3,5,7,11\}} n^2 = 2^2 + 3^2 + 5^2 + 7^2 + 11^2 = 208. \] Or we could write it as \[ \sum_{\text{$p$ prime, $p\le 11$}} p^2. \] As another example, the sum of the cubes of the primes less than 100 is \[ \sum_{\text{$p$ prime, $p\le 100$}} p^3 = 2^3+3^3+\cdots+97^3=4696450. \] How did I compute this last sum? I used a computer!

We can use summation notation to compute sums over even more complicated collections of objects. An important example is summing over all of the subsets of a given set $S$. For example, let $S$ be a set with $3$ elements, say $S=\{A,B,C\}$. Then $S$ has eight subsets, and we can compute things such as the sum of the sizes of all of its subsets: \[ \begin{aligned} \smash[b]{ \sum_{T\subseteq S} |T| } &= \bigl|\{\}\bigr| + \bigl|\{A\}\bigr| + \bigl|\{B\}\bigr| + \bigl|\{C\}\bigr| + \bigl|\{A,B\}\bigr| + \bigl|\{A,C\}\bigr| + \bigl|\{B,C\}\bigr| + \bigl|\{A,B,C\}\bigr| \\ &= 0+1+1+1+2+2+2+3 \\ &= 12. \end{aligned} \] More generally, suppose that the set $S$ has $n$ elements. Then the following formula is true: \[ \sum_{T\subseteq S} |T| = \sum_{k=0}^n k\binom{n}{k}. \] Do you see why? (Challenge Problem Show that the above sum is equal to $n2^{n-1}$.)

Practice Problems: Here are some exercises that you can use to test your knowledge. You can check your answers against the solutions, which are given at the bottom of the page.

  1. Expand the following sums and compute their values:
    (a) $\displaystyle\sum_{k=1}^3 \frac{1}{k}$
    (b) $\displaystyle\sum_{j=2}^5 \frac{j}{2^j}$
    (c) $\displaystyle\sum_{x\in\{-2,3,7\}} x^2$
    (d) $\displaystyle 4! \sum_{j=0}^4 \frac{(-1)^j}{j!}$ (This is the number of derangements of a set of 4 elements; see Section 1.5.)
  2. Expand the following sums and compute their values:
    (a) $\displaystyle\sum_{i=1}^3 \sum_{j=1}^3 ij$
    (b) $\displaystyle\sum_{i=1}^3 \sum_{j=1}^i ij$
  3. Expand the following sum and compute its value: $\displaystyle\sum_{T\subseteq\{2,3,4\}} (-1)^{|T|}$
  4. Expand the following sum and compute its value: $\displaystyle\sum_{T\subseteq\{2,3,4\}} \sum_{n\in T} n$
  5. Express the following formulas using summation notation:
    (a) $1+2+3+\cdots+n=\dfrac{n^2+n}{2}$
    (b) $1^2+2^2+3^2+\cdots+n^2=\dfrac{2n^3+3n^2+n}{6}$
    (c) $\displaystyle 1+\frac12+\frac13+\cdots+\frac{1}{n}\approx\ln(n)$

Return to the Math 750 Unit 2 (Combinatorics/Graph Theory) Home Page

Solutions to Practice Problems:

  1. (a) $\displaystyle\sum_{k=1}^3 \frac{1}{k} = \frac{1}{1}+\frac{1}{2}+\frac{1}{3} = \frac{11}{6}$
    (b) $\displaystyle\sum_{j=2}^5 \frac{j}{2^j} = \frac{2}{2^2} + \frac{3}{2^3} + \frac{4}{2^4} + \frac{5}{2^5} = \frac{2}{4} + \frac{3}{8} + \frac{4}{16} + \frac{5}{32} = \frac{41}{32}$
    (c) $\displaystyle\sum_{x\in\{-2,3,7\}} x^2 = (-2)^2+3^2+7^2 = 4+9+49 = 62$
    (d) $\displaystyle 4! \sum_{j=0}^4 \frac{(-1)^j}{j!} = 4!\left(\frac{1}{0!}-\frac{1}{1!}+\frac{1}{2!}-\frac{1}{3!}+\frac{1}{4!}\right) = 24\left(1-1+\frac{1}{2}-\frac{1}{6}+\frac{1}{24}\right) = 24 - 24 + 12 - 4 + 1 = 9$
  2. First we expand the outer sum, and then we expand the inner sums.
    (a) $\displaystyle\sum_{i=1}^3 \sum_{j=1}^3 ij = \sum_{j=1}^3 j + \sum_{j=1}^3 2j + \sum_{j=1}^3 3j = (1+2+3) + (2+4+6) + (3+6+9) = 36 $
    (b) $\displaystyle\sum_{i=1}^3 \sum_{j=1}^i ij = \sum_{j=1}^1 j + \sum_{j=1}^2 2j + \sum_{j=1}^3 3j = 1 + (2+4) + (3+6+9) = 25 $
  3. The set $\{2,3,4\}$ has 8 subsets.
    $\displaystyle\begin{aligned} \smash[b]{\sum_{T\subseteq\{2,3,4\}} (-1)^{|T|} } &= (-1)^{|\{\}|} + (-1)^{|\{2\}|} + (-1)^{|\{3\}|} + (-1)^{|\{4\}|} + (-1)^{|\{2,3\}|} + (-1)^{|\{2,4\}|} + (-1)^{|\{3,4\}|} + (-1)^{|\{2,3,4\}|} \\ &= (-1)^0 + (-1)^1 + (-1)^1 + (-1)^1 + (-1)^2 + (-1)^2 + (-1)^2 + (-1)^3 \\ &= 1 - 1 -1 -1 + 1+ 1+1-1\\ &=0 \end{aligned}$
  4. First we expand the outer sum, and then we expand the 8 inner sums.
    $\displaystyle\begin{aligned} \sum_{T\subseteq\{2,3,4\}} \sum_{n\in T} n &= \sum_{n\in \{\}} n + \sum_{n\in \{2\}} n + \sum_{n\in \{3\}} n + \sum_{n\in \{4\}} n + \sum_{n\in \{2,3\}} n + \sum_{n\in \{2,4\}} n + \sum_{n\in \{3,4\}} n + \sum_{n\in \{2,3,4\}} n \\ &= 0 + 2 + 3 + 4 + (2+3) + (2+4) + (3+4) + (2+3+4) \\ &= 36 \end{aligned}$
  5. (a) $\displaystyle\sum_{i=1}^n i = \frac{n^2+n}{2}$
    (b) $\displaystyle\sum_{j=1}^n j^2 = \frac{2n^3+3n^2+n}{6}$
    (c) $\displaystyle\sum_{k=1}^n \frac{1}{k}\approx\ln(n)$