\( \newcommand{\NOT}{\neg} \newcommand{\AND}{\wedge} \newcommand{\OR}{\vee} \newcommand{\XOR}{\oplus} \newcommand{\IMP}{\Rightarrow} \newcommand{\IFF}{\Leftrightarrow} \newcommand{\TRUE}{\text{True}\xspace} \newcommand{\FALSE}{\text{False}\xspace} \newcommand{\IN}{\,{\in}\,} \newcommand{\NOTIN}{\,{\notin}\,} \newcommand{\TO}{\rightarrow} \newcommand{\DIV}{\mid} \newcommand{\NDIV}{\nmid} \newcommand{\MOD}[1]{\pmod{#1}} \newcommand{\MODS}[1]{\ (\text{mod}\ #1)} \newcommand{\N}{\mathbb N} \newcommand{\Z}{\mathbb Z} \newcommand{\Q}{\mathbb Q} \newcommand{\R}{\mathbb R} \newcommand{\C}{\mathbb C} \newcommand{\cA}{\mathcal A} \newcommand{\cB}{\mathcal B} \newcommand{\cC}{\mathcal C} \newcommand{\cD}{\mathcal D} \newcommand{\cE}{\mathcal E} \newcommand{\cF}{\mathcal F} \newcommand{\cG}{\mathcal G} \newcommand{\cH}{\mathcal H} \newcommand{\cI}{\mathcal I} \newcommand{\cJ}{\mathcal J} \newcommand{\cL}{\mathcal L} \newcommand{\cK}{\mathcal K} \newcommand{\cN}{\mathcal N} \newcommand{\cO}{\mathcal O} \newcommand{\cP}{\mathcal P} \newcommand{\cQ}{\mathcal Q} \newcommand{\cS}{\mathcal S} \newcommand{\cT}{\mathcal T} \newcommand{\cV}{\mathcal V} \newcommand{\cW}{\mathcal W} \newcommand{\cZ}{\mathcal Z} \newcommand{\emp}{\emptyset} \newcommand{\bs}{\backslash} \newcommand{\floor}[1]{\left \lfloor #1 \right \rfloor} \newcommand{\ceil}[1]{\left \lceil #1 \right \rceil} \newcommand{\abs}[1]{\left | #1 \right |} \newcommand{\xspace}{} \newcommand{\proofheader}[1]{\underline{\textbf{#1}}} \)

C.1 Summations and Products

When performing calculations, we’ll often end up writing sums of terms, where each term follows a pattern. For example: \[\frac{1 + 1^2}{3 + 1} + \frac{2 + 2^2}{3 + 2} + \frac{3 + 3^2}{3 + 3} + \cdots + \frac{100 + 100^2}{3 + 100}\]

We will often use summation notation to express such sums concisely. We could rewrite the previous example simply as: \[\sum_{i=1}^{100} \frac{i + i^2}{3 + i}.\]

In this example, \(i\) is called the index of summation, and \(1\) and \(100\) are the lower and upper bounds of the summation, respectively. A bit more generally, for any pair of integers \(j\) and \(k\), and any function \(f : \Z \to \R\), we can use summation notation in the following way: \[\sum_{i=j}^k f(i) = f(j) + f(j+1) + f(j+2) + \dots + f(k).\]

We can similarly use product notation to abbreviate multiplication:Fun fact: the Greek letter \(\Sigma\) (sigma) corresponds to the first letter of “sum,” and the Greek letter \(\Pi\) (pi) corresponds to the first letter of “product.” \[\prod_{i=j}^k f(i) = f(j) \times f(j+1) \times f(j+2) \times \dots \times f(k).\]

It is sometimes useful (e.g., in certain formulas) to allow a summation or product’s lower bound to be greater than its upper bound. In this case, we say the summation or product is empty, and define their values as follows:These particular values are chosen so that adding an empty summation and multiplying by an empty product do not change the value of an expression.

Finally, we’ll end off this section with a few formulas for common summation formulas, and a few laws governing how expressions using summation and product notation can be simplified.

For all \(n \in \N\), the following formulas hold:

  1. For all \(c \in \R\), \(\sum_{i=1}^{n} c = c \cdot n\) (sum with constant terms).
  2. \(\sum_{i=0}^{n} i = \frac{n(n+1)}{2}\) (sum of consecutive numbers).
  3. \(\sum_{i=0}^{n} i^2 = \frac{n(n+1)(2n+1)}{6}\) (sum of consecutive squares).
  4. For all \(r \in \R\), if \(r \neq 1\) then \(\sum_{i=0}^{n-1} r^i = \frac{r^n - 1}{r - 1}\) (sum of powers).
  5. For all \(r \in \R\), if \(r \neq 1\) then \(\sum_{i=0}^{n-1} i \cdot r^i = \frac{n \cdot r^n}{r - 1} - \frac{r(r^n - 1)}{(r - 1)^2}\) (arithmetico-geometric series).

For all \(m, n \in \Z\), the following formulas hold:

  1. \(\sum_{i=m}^{n} (a_i + b_i) = \left( \sum_{i=m}^{n} a_i \right) + \left(\sum_{i=m}^{n} b_i \right)\) (separating sums)

  2. \(\prod_{i=m}^{n} (a_i \cdot b_i) = \left( \prod_{i=m}^{n} a_i \right) \cdot \left (\prod_{i=m}^{n} b_i \right)\) (separating products)

  3. \(\sum_{i=m}^{n} c \cdot a_i = c \cdot \left( \sum_{i=m}^{n} a_i \right)\) (factoring out constants, sums)

  4. \(\prod_{i=m}^{n} c \cdot a_i = c^{n - m + 1} \cdot \left( \prod_{i=m}^{n} a_i \right)\) (factoring out constants, products)

  5. \(\sum_{i=m}^{n} a_i = \sum_{i'=0}^{n-m} a_{i'+m}\) (change of index \(i' = i - m\))

  6. \(\prod_{i=m}^{n} a_i = \prod_{i'=0}^{n-m} a_{i'+m}\) (change of index \(i' = i - m\))