Summation

Revision as of 18:29, 23 November 2007 by Azjps (talk | contribs) (expand + revise)

A summation is the sum of a number of terms (addends). Summations are often written using sigma notation $\left(\sum \right)$.

Definition

For $b\ge a$, and a set $c$ (or any other algebraic structure), $\sum_{i=a}^{b}c_i=c_a+c_{a+1}+c_{a+2}...+c_{b-1}+c_{b}$. Here $i$ refers to the index of summation, $a$ is the lower bound, and $b$ is the upper bound.

As an example, $\sum_{i=3}^6 i^3 = 3^3 + 4^3 + 5^3 + 6^3$. Note that if $a>b$, then the sum is $0$.

Quite often, sigma notation is used slightly different format to denote certain sums. For example, $\sum_{cyc}$ refers to a cyclic sum, and $\sum_{a,b \in S}$ refers to all subsets $a, b$ which are in $S$. Usually, the bottom of the sigma contains a logical condition, as in $\sum_{i|n}^{n} i$, where the sum only includes the terms $i$ which divide into $n$.

Identities

  • $\sum_{i=a}^{b}f(i)+g(i)=\sum_{i=a}^{b}f(i)+\sum_{i=a}^{b}g(i)$
  • $\sum_{i=a}^{b}c\cdot f(i)=c\cdot \sum_{i=a}^{b}f(i)$
  • $\sum_{i=1}^{n} i= \frac{n(n+1)}{2}$, and in general $\sum_{i=a}^{b} i= \frac{(b-a+1)(a+b)}{2}$
  • $\sum_{i=1}^{n} i^2 = \frac{n(n+1)(2n+1)}{6}$
  • $\sum_{i=1}^{n} i^3 = \left(\sum_{i=1}^{n} i\right)^2 = \left(\frac{n(n+1)}{2}\right)^2$
  • $\sum_{i=0}^{n} x^n = \frac{x^{n+1}-1}{x-1}$, and in general $\sum_{i=a}^{b} c^i = \frac{c^{b+1}-c^a}{c-1}$
  • $\sum_{i=0}^{n} {n\choose i} = 2^n$
  • $\sum_{i,j}^{n} = \sum_i^n \sum_j^n$

Problems

Introductory

  • Evaluate the following sums:
    • $\sum_{i=1}^{20} i$
    • $\sum_{i=5}^{15} i + 1$
    • $\sum_{i=1}^{9} {10\choose i}$

Intermediate

  • The nine horizontal and nine vertical lines on an $8\times8$ checkerboard form $r$ rectangles, of which $s$ are squares. The number $s/r$ can be written in the form $m/n,$ where $m$ and $n$ are relatively prime positive integers. Find $m + n.$ (1997 AIME, #2)

Olympiad

See Also