Summations

Summations #

Summation #

One way to think about a summation is that it is just the discrete form of an integral.

SUMMATION

Given a sequence \(x_a, x_{a+1}, \dotsc, x_b\) its sum \(x_a + x_{a+1} + \dotsb + x_b\) is written as

\( \begin{aligned} \sum_{i=a}^b x_i \end {aligned} \)

where the variable \(i\) is called the index of summation; \(a\) is the lower bound (or lower limit); and \(b\) is the upper bound (or upper limit).

If \(b \lt a\) then the sum is \(0\).

Another way to think about a summation is as a \(\it{for}\) loop: loop through all values of \(i\) from \(a\) to \(b\) inclusive, summing the body of the summation for each iteration \(i\).

Double Summation #

If you think of a sum as a for loop, a double sum is two nested for loops. The effect is to sum the innermost expression over all pairs of values of the two indices.

Constant #

\( \begin{aligned} \sum_{i=m}^{n} \sum_{j=s}^{t} C = C \sum_{i=m}^{n} \sum_{j=s}^{t} 1 = C \times (n - m + 1) \times (t - s + 1) \end {aligned} \)

where \(C\) is a constant (any expression that doesn’t involve index variables) and \(m \le n\) and \(s \le t\).

This is just multiplication of nonnegative integers.

\( \begin{aligned} a \times b \overset{\text{def}}{=} \sum_{i=1}^a \sum_{j=1}^b 1 \\ \end {aligned} \)

\( \begin{aligned} \sum_{i=1}^{m} \sum_{j=1}^{n} a_i + b_j &= \sum_{i=1}^{m} (a_i + b_1 + a_i + b_2 + \dotsb + a_i + b_n) \\ &= \sum_{i=1}^{m} (na_i + b_1 + b_2 + \dotsb + b_n) \\ &= (na_1 + b_1 + b_2 + \dotsb + b_n) + (na_2 + b_1 + b_2 + \dotsb + b_n) + \dotsb + (na_m + b_1 + b_2 + \dotsb + b_n) \\ &= n(a_1 + a_2 + \dotsb + a_m) + m(b_1 + b_2 + \dotsb + b_n) \\ &= n \sum_{i=1}^{m} a_i + m \sum_{j=1}^{n} b_j \\ \end {aligned} \)

Example

\( \begin{aligned} a &= \{ \underset{a_1}{1}, \underset{a_2}{2}, \underset{a_3}{3}, \underset{a_4}{4} \} \\ b &= \{ \underset{b_1}{1}, \underset{b_2}{2}, \underset{b_3}{3} \} \\ \end {aligned} \)

\( \begin{aligned} \sum_{i=1}^{4} \sum_{j=1}^{3} a_i + b_j &= \sum_{i=1}^{4} (a_i + 1 + a_i + 2 + a_i + 3) \\ &= \sum_{i=1}^{m} (3a_i + 1 + 2 + 3) \\ &= (3.1 + 1 + 2 + 3) + (3.2 + 1 + 2 + 3) + (3.3 + 1 + 2 + 3) + (3.4 + 1 + 2 + 3) \\ &= 3(1 + 2 + 3 + 4) + 4(1 + 2 + 3) \\ &= 54 \\ \end {aligned} \)

Example

\( \begin{aligned} \sum_{i=0}^{n} \sum_{j=0}^{i} (i + 1)(j + 1) &= \sum_{i=0}^{n} \left( \sum_{j=0}^{i} (i + 1)(j + 1) \right) \\ &= \sum_{j=0}^{0} (0 + 1)(j + 1) + \sum_{j=0}^{1} (1 + 1)(j + 1) \\ &= (0 + 1)(0 + 1) + (1 + 1)(0 + 1) + (1 + 1)(1 + 1) \\ &= 1 + 2 + 4 = 7 \\ \end {aligned} \)

Product #

\( \begin{aligned} \sum_{i=m}^{n} a_i \sum_{j=s}^{t} b_j = \sum_{i=m}^{n} \sum_{j=s}^{t} a_i b_j \end {aligned} \)

Must the following conditions hold here?

\( \begin{aligned} 0 &\le \phantom{s}m \le n \\ 0 &\le \phantom{m}s \le t \\ \end {aligned} \)

Claim

\( \begin{aligned} f &= \sum_{i=0}^m a_i \\ g &= \sum_{j=0}^n b_j \\ fg &= \boxed{ \sum_{i=0}^{m} \sum_{j=0}^{n} a_i b_j = \sum_{j=0}^{n} \sum_{i=0}^{m} a_i b_j } \end {aligned} \)

\( \begin{aligned} \sum_{i=0}^{m} \sum_{j=0}^{n} a_i b_j &= \sum_{i=0}^{m} \left( \sum_{j=0}^{n} a_i b_j \right) \\ &= \sum_{i=0}^{m} (a_i b_0 + a_i b_1 + \dotsb + a_i b_n) \\ &= (\textcolor{red}{a_0 b_0 + a_0 b_1 + \dotsb + a_0 b_n}) + (\textcolor{orange}{a_1 b_0 + a_1 b_1 + \dotsb + a_1 b_n}) + \dotsb + (\textcolor{yellow}{a_m b_0 + a_m b_1 + \dotsb + a_m b_n}) \\ &= (\textcolor{red}{a_0 b_0} + \textcolor{orange}{a_1 b_0} + \dotsb + \textcolor{yellow}{a_m b_0}) + (\textcolor{red}{a_0 b_1} + \textcolor{orange}{a_1 b_1} + \dotsb + \textcolor{yellow}{a_m b_1}) + \dotsb + (\textcolor{red}{a_0 b_n} + \textcolor{orange}{a_1 b_n} + \dotsb + \textcolor{yellow}{a_m b_n}) \\ &= \sum_{j=0}^{n} (a_0 b_i + a_1 b_i + \dotsb + a_m b_i) \\ &= \sum_{j=0}^{n} \left( \sum_{i=0}^{m} a_i b_j \right) \\ \end {aligned} \)

Claim

\( \begin{aligned} f &= \sum_{i=0}^m a_i \\ g &= \sum_{j=0}^n b_j \\ fg &= \boxed{ \sum_{i=0}^m a_i \sum_{j=0}^n b_i = \sum_{i=0}^{m} \sum_{j=0}^{n} a_i b_j } \end {aligned} \)

\( \begin{aligned} \sum_{i=0}^{m} \sum_{j=0}^{n} a_i b_j &= \sum_{i=0}^{m} \left( \sum_{j=0}^{n} a_i b_j \right) \\ &= \sum_{i=0}^{m} (a_i b_0 + a_i b_1 + \dotsb + a_i b_n) \\ &= (a_0 b_0 + a_0 b_1 + \dotsb + a_0 b_n) + (a_1 b_0 + a_1 b_1 + \dotsb + a_1 b_n) + \dotsb + (a_m b_0 + a_m b_1 + \dotsb + a_m b_n) \\ &= a_0 (b_0 + b_1 + \dotsb + b_n) + a_1 (b_0 + b_1 + \dotsb + b_n) + \dotsb + a_m (b_0 + b_1 + \dotsb + b_n) &&= a_0 \sum_{j=0}^{n} b_j + a_1 \sum_{j=0}^{n} b_j + \dotsb + a_m \sum_{j=0}^{n} b_j \\ &= (a_0 + a_1 + \dotsb + a_m) (b_0 + b_1 + \dotsb + b_n) &&= (a_0 + a_1 + \dotsb + a_m) \sum_{j=0}^{n} b_j \\ &= \sum_{i=0}^{m} a_i \sum_{j=0}^{n} b_j \end {aligned} \)

\( \begin{aligned} \left( \sum_{i=1}^{n} a_i \right)^2 = \sum_{i=1}^{n} a_i^2 + \underset{i \ne j}{\sum_{i=1}^{n} \sum_{j=1}^{n}} a_i a_j \end {aligned} \)

Discrete Convolution #

\( \begin{aligned} \sum_{i=0}^{m} a_i \sum_{j=0}^{n} b_j = \underset{0 \le j \le n}{\underset{0 \le i \le m}{\sum}} a_i b_j = \underset{k=i+j}{\underset{0 \le k \le m + n}{\underset{0 \le j \le n}{\underset{0 \le i \le m}{\sum}}}} a_i b_{k-i} = \sum_{i=0}^{m} \sum_{j=0}^{n} \left( \sum_{k=i+j} a_i b_{k-i} \right) \end {aligned} \)

where in the last expression \(k\) only takes the single value \(i + j\). Thus the third summation symbol does not get expanded; the third summation symbol to the end of the expression is a single term, and so we only have a double summation.

\( \begin{aligned} 0 &\le i \le m \\ 0 &\le j \le n \\ 0 &\le k \le m + n \\ k &= i + j \\ \end {aligned} \iff \begin{aligned} 0 &\le i \le m \\ 0 &\le k - i \le n \\ 0 &\le k \le m + n \\ j &= k - i \\ \end {aligned} \iff \begin{aligned} 0 &\le i \le m \\ k - n &\le i \le k \\ & 0 \le k \le m + n \\ & j = k - i \\ \end {aligned} \)

We start with a set of inequations (inequalities and equations) for the three index variables \(i\), \(j\), and \(k\), and we manipulate them in such a way as to reduce the number of index variables to two. In this case, we are left with \(i\) and \(k\), but we could have easily chosen to keep \(j\) instead of \(i\).

\( \begin{aligned} \sum_{i=0}^{m} \sum_{j=0}^{n} \left( \sum_{k=i+j} a_i b_{k-i} \right) = \sum_{k=0}^{m+n} \sum_{i=\max\{ 0, k-n \}}^{\min\{ m, k \}} \left( \sum_{j=k-i} a_i b_{k-i} \right) = \left( \sum_{k=0}^{m+n} \sum_{i=\max\{ 0, k-n \}}^{\min\{ m, k \}} a_i b_{k-i} \right) \left( \sum_{j=k-i} 1 \right) = \sum_{k=0}^{m+n} \sum_{i=\max\{ 0, k-n \}}^{\min\{ m, k \}} a_i b_{k-i} \end {aligned} \)

One of \(m\) or \(n\) is less than or equal to the other, say \(0 \lt m \le n\). Then we have

\( \begin{aligned} \sum_{k=0}^{m+n} = \sum_{k=0}^{m-1} + \sum_{k=m}^n + \sum_{k=n+1}^{m+n} \end {aligned} \)

and so

\( \begin{aligned} \sum_{k=0}^{m+n} \sum_{i=\max\{ 0, k-n \}}^{\min\{ m, k \}} a_i b_{k-i} &= \left( \sum_{k=0}^{m-1} + \sum_{k=m}^n + \sum_{k=n+1}^{m+n} \right) \left( \sum_{i=\max\{ 0, k-n \}}^{\min\{ m, k \}} a_i b_{k-i} \right) \\ &= \left( \sum_{k=0}^{m-1} \sum_{i=\max\{ 0, k-n \}}^{\min\{ m, k \}} a_i b_{k-i} \right) + \left( \sum_{k=m}^n \sum_{i=\max\{ 0, k-n \}}^{\min\{ m, k \}} a_i b_{k-i} \right) + \left( \sum_{k=n+1}^{m+n} \sum_{i=\max\{ 0, k-n \}}^{\min\{ m, k \}} a_i b_{k-i} \right) \\ \end {aligned} \)

Looking at the first term

\( \begin{aligned} \sum_{k=0}^{m-1} \sum_{i=\max\{ 0, k-n \}}^{\min\{ m, k \}} a_i b_{k-i} \end {aligned} \)

we can see that \(0 \le k \lt m\) and we already know that \(0 \lt m \le n\). Therefore

\( \begin{aligned} 0 \le k \lt m \le n & \implies \min\{ m, k \} = k \\ & \implies k-n \lt m-n \le 0 \implies \max\{ 0, k-n \} = 0 \\ \end {aligned} \)

\( \begin{aligned} \sum_{k=0}^{m-1} \sum_{i=\max\{ 0, k-n \}}^{\min\{ m, k \}} a_i b_{k-i} &= \sum_{k=0}^{m-1} \sum_{i=0}^k a_i b_{k-i} \\ &= \sum_{k=0}^{m-1} \left( \sum_{i=0}^k a_i b_{k-i} \right) \\ &= \sum_{i=0}^0 a_i b_{0-i} + \sum_{i=0}^1 a_i b_{1-i} + \dotsb + \sum_{i=0}^{m-1} a_i b_{m-1-i} \\ &= \underbrace{(a_0 b_0)}_{1 \text{ term}} + \underbrace{(a_0 b_1 + a_1 b_0)}_{2 \text{ terms}} + \dotsb + \underbrace{(a_0 b_{m-1} + \dotsb + a_{m-1} b_0)}_{m \text{ terms}} \\ \end {aligned} \)

There are

\( \begin{aligned} \sum_{x=1}^m x = \frac{m(m + 1)}{2} \\ \end {aligned} \)

terms in this expression, which form the bottom-left triangular section of the coefficient matrix (see below).

Looking at the second term

\( \begin{aligned} \sum_{k=m}^{n} \sum_{i=\max\{ 0, k-n \}}^{\min\{ m, k \}} a_i b_{k-i} \end {aligned} \)

we can see that \(m \le k \le n\) and we already know that \(0 \lt m \le n\). Therefore

\( \begin{aligned} 0 \lt m \le k \le n & \implies \min\{ m, k \} = m \\ & \implies m-n \le k-n \le 0 \implies \max\{ 0, k-n \} = 0 \\ \end {aligned} \)

\( \begin{aligned} \sum_{k=m}^n \sum_{i=\max\{ 0, k-n \}}^{\min\{ m, k \}} a_i b_{k-i} &= \sum_{k=m}^n \sum_{i=0}^m a_i b_{k-i} \\ &= \sum_{k=m}^n \left( \sum_{i=0}^m a_i b_{k-i} \right) \\ &= \sum_{i=0}^m a_i b_{m-i} + \sum_{i=0}^m a_i b_{m+1-i} + \dotsb + \sum_{i=0}^m a_i b_{n-i} \\ &= \underbrace{(a_0 b_m + a_1 b_{m-1} + \dotsb + a_m b_0)}_{m+1 \text{ terms}} + \underbrace{(a_0 b_{m+1} + a_1 b_m + \dotsb + a_m b_1)}_{m+1 \text{ terms}} + \dotsb + \underbrace{(a_0 b_n + a_1 b_{n-1} + \dotsb + a_m b_{n-m})}_{m+1 \text{ terms}} \\ \end {aligned} \)

The number of terms in this last expression is equal to \((n - m + 1)(m + 1)\).

For example, when \(m = n\) this middle term reduces to

\( \begin{aligned} \sum_{k=n}^n \sum_{i=0}^n a_i b_{k-i} \end {aligned} \)

which is just the single top-left to bottom-right diagonal of the coefficient matrix

\( \begin{aligned} \sum_{k=n}^n \sum_{i=0}^n a_i b_{k-i} = \sum_{i=0}^n a_i b_{n-i} = a_0 b_n + a_1 b_{n-1} + \dotsb + a_n b_0 \\ \end {aligned} \)

consisting of \(n + 1\) terms.

Looking at the third term

\( \begin{aligned} \sum_{k=n+1}^{m+n} \sum_{i=\max\{ 0, k-n \}}^{\min\{ m, k \}} a_i b_{k-i} \end {aligned} \)

we can see that \(n \lt k \le m+n\) and we already know that \(0 \lt m \le n\). Therefore

\( \begin{aligned} 0 \lt m \le n \lt k \le m+n & \implies \min\{ m, k \} = m \\ & \implies 0 \lt k-n \le m \implies \max\{ 0, k-n \} = k-n \\ \end {aligned} \)

\( \begin{aligned} \sum_{k=n}^{m+n} \sum_{i=\max\{ 0, k-n \}}^{\min\{ m, k \}} a_i b_{k-i} &= \sum_{k=n}^{m+n} \sum_{i=k-n}^m a_i b_{k-i} \\ &= \sum_{k=n+1}^{m+n} \left( \sum_{i=k-n}^m a_i b_{k-i} \right) \\ &= \sum_{i=1}^m a_i b_{n+1-i} + \sum_{i=2}^m a_i b_{n+2-i} + \dotsb + \sum_{i=m}^m a_i b_{m+n-i} \\ &= \underbrace{(a_1 b_n + a_2 b_{n-1} + \dotsb + a_m b_{n-m+1})}_{m \text{ terms}} + \underbrace{(a_2 b_n + a_3 b_{n-1} + \dotsb + a_m b_{n-m+2})}_{m-1 \text{ terms}} + \dotsb + \underbrace{(a_m b_n)}_{1 \text{ term}} \\ \end {aligned} \)

There are

\( \begin{aligned} \sum_{x=1}^m x = \frac{m(m + 1)}{2} \\ \end {aligned} \)

terms in this expression, which form the top-right triangular section of the coefficient matrix (see below).

Putting this together we have

\( \begin{aligned} & \left( \sum_{k=0}^{m-1} \sum_{i=\max\{ 0, k-n \}}^{\min\{ m, k \}} a_i b_{k-i} \right) + \left( \sum_{k=m}^{n-1} \sum_{i=\max\{ 0, k-n \}}^{\min\{ m, k \}} a_i b_{k-i} \right) + \left( \sum_{k=n}^{m+n} \sum_{i=\max\{ 0, k-n \}}^{\min\{ m, k \}} a_i b_{k-i} \right) \\ &= \boxed{ \sum_{k=0}^{m-1} \sum_{i=0}^k a_i b_{k-i} + \sum_{k=m}^n \sum_{i=0}^m a_i b_{k-i} + \sum_{k=n+1}^{m+n} \sum_{i=k-n}^m a_i b_{k-i} } \end {aligned} \)

The first term corresponds to the bottom-left triangle of the coefficient matrix (see below); the second term corresponds to the parallelogram that fills up the middle portion; and the third term fills in the remaining top-right triangle.

The first summation term gave us \(m(m + 1)/2\) terms. The second gave us \((n - m + 1)(m + 1)\). And the third gave us \(m(m + 1)/2\).

\( \begin{aligned} m(m + 1) + (n - m + 1)(m + 1) = (m + 1)(m + n - m + 1) = \boxed{(m + 1)(n + 1)} \end {aligned} \)

With \(0 \lt m \le n\) the coefficient matrix may be no shorter than it is wide (if \(m = n\)), but it may be taller (if \(m \lt n\)).

When \(m = n\) this reduces to

\( \begin{aligned} \sum_{k=0}^{n-1} \sum_{i=0}^k a_i b_{k-i} + \sum_{k=n}^n \sum_{i=0}^n a_i b_{k-i} + \sum_{k=n+1}^{2n} \sum_{i=k-n}^n a_i b_{k-i} \end {aligned} \)

Observe how one might go about re-compressing the expansion:

\( \begin{aligned} & \sum_{k=0}^{m-1} \sum_{i=0}^k a_i b_{k-i} + \sum_{k=m}^n \sum_{i=0}^m a_i b_{k-i} + \sum_{k=n+1}^{m+n} \sum_{i=k-n}^m a_i b_{k-i} \\ &= \sum_{k=0}^n \sum_{i=0}^{\min\{ m, k \}} a_i b_{k-i} + \sum_{k=n+1}^{m+n} \sum_{i=k-n}^m a_i b_{k-i} = \sum_{k=0}^{m-1} \sum_{i=0}^k a_i b_{k-i} + \sum_{k=m}^{m+n} \sum_{i=\max\{ 0, k-n \}}^m a_i b_{k-i} \\ &= \sum_{k=0}^{m+n} \sum_{i=\max\{ 0, n-k \}}^{\min\{ m, k \}} a_i b_{k-i} \\ \end {aligned} \)

This isn’t quite right. Look to the above derivation for the correction.

\( \begin{aligned} \sum_{i=0}^{m} a_i \sum_{j=0}^{n} b_j &= (a_0 + \dotsb + a_m) \sum_{j=0}^{n} b_j \\ &= a_0 \sum_{j=0}^n b_j + a_1 \sum_{j=0}^n b_j+ \dotsb + a_m \sum_{j=0}^n b_j \\ &= a_0 (b_0 + \dotsb + b_n) + a_1 (b_0 + \dotsb + b_n) + \dotsb + a_m (b_0 + \dotsb + b_n) \\ &= \underbrace{(a_0 b_0 + \dotsb + a_0 b_n)}_{1} + \underbrace{(a_1 b_0 + \dots + a_1 b_n)}_{2} + \dotsb + \underbrace{(a_m b_0 + \dotsb + a_m b_n)}_{m} \\ &= \textcolor{red}{a_0 b_0} + (\textcolor{orange}{a_0 b_1 + a_1 b_0}) + (\textcolor{yellow}{a_0 b_2 + a_1 b_1 + a_2 b_0}) + \dotsb + (\textcolor{#0070e0}{a_{m-2} b_n + a_{m-1} b_{n-1} + a_m b_{n-2}}) + (\textcolor{#00a8e0}{a_{m-1} b_n + a_m b_{n-1}}) + \textcolor{#00e0e0}{a_m b_n} \\ &= \sum_{i=0}^{0} a_i b_{0-i} + \sum_{i=0}^{1} a_i b_{1-i} + \sum_{i=0}^{2} a_i b_{2-i} + \dotsb + \sum_{i=0}^{n} a_i b_{n-i} \\ &= \sum_{k=0}^n \left( \sum_{i=0}^{k} a_i b_{k-i} \right) \\ \end {aligned} \)

\( \begin{array}{ccccccccc} a_0 b_{n+m} \\ a_0 b_{n+m-1} & a_1 b_{n+m-1} \\ a_0 b_{n+m-2} & a_1 b_{n+m-2} & a_2 b_{n+m-2} \\ a_0 b_{n+m-3} & a_1 b_{n+m-3} & a_2 b_{n+m-3} & a_3 b_{n+m-3} \\ \vdots & \vdots & \vdots & \vdots \\ a_0 b_{n+3} & a_1 b_{n+3} & a_2 b_{n+3} & a_3 b_{n+3} & \dots & a_{m-3} b_{n+3} \\ a_0 b_{n+2} & a_1 b_{n+2} & a_2 b_{n+2} & a_3 b_{n+2} & \dots & a_{m-3} b_{n+2} & a_{m-2} b_{n+2} \\ a_0 b_{n+1} & a_1 b_{n+1} & a_2 b_{n+1} & a_3 b_{n+1} & \dots & a_{m-3} b_{n+1} & a_{m-2} b_{n+1} & a_{m-1} b_{n+1} \\ \end {array} \) \( \begin{array}{cc} \begin{array}{c|c|c|c|c|c|c|c|c|} \hline 1 & 2 & 3 & 4 & & m-3 & m-2 & m-1 & m \\ \hline \phantom{_{+m}}a_0 b_{n\phantom{-1}} & \phantom{_{+m}}a_1 b_{n\phantom{-1}} & \phantom{_{+m}}a_2 b_{n\phantom{-1}} & \phantom{_{+m}}a_3 b_{n\phantom{-1}} & \dots & \textcolor{#0038e0}{a_{m-3} b_n} & \textcolor{#0070e0}{a_{m-2} b_n} & \textcolor{#00a8e0}{a_{m-1} b_n} & \textcolor{#00e0e0}{a_m b_n} \\ a_0 b_{n-1} & a_1 b_{n-1} & a_2 b_{n-1} & a_3 b_{n-1} & \dots & a_{m-3} b_{n-1} & \textcolor{#0038e0}{a_{m-2} b_{n-1}} & \textcolor{#0070e0}{a_{m-1} b_{n-1}} & \textcolor{#00a8e0}{a_m b_{n-1}} \\ a_0 b_{n-2} & a_1 b_{n-2} & a_2 b_{n-2} & a_3 b_{n-2} & \dots & a_{m-3} b_{n-2} & a_{m-2} b_{n-2} & \textcolor{#0038e0}{a_{m-1} b_{n-2}} & \textcolor{#0070e0}{a_m b_{n-2}} \\ a_0 b_{n-3} & a_1 b_{n-3} & a_2 b_{n-3} & a_3 b_{n-3} & \dots & a_{m-3} b_{n-3} & a_{m-2} b_{n-3} & a_{m-1} b_{n-3} & \textcolor{#0038e0}{a_m b_{n-3}} \\ \vdots & \vdots & \vdots & \vdots & \ddots & \vdots & \vdots & \vdots & \vdots \\ \textcolor{green}{a_0 b_3} & a_1 b_3 & a_2 b_3 & a_3 b_3 & \dots & a_{m-3} b_3 & a_{m-2} b_3 & a_{m-1} b_3 & a_m b_3 \\ \textcolor{yellow}{a_0 b_2} & \textcolor{green}{a_1 b_2} & a_2 b_2 & a_3 b_2 & \dots & a_{m-3} b_2 & a_{m-2} b_2 & a_{m-1} b_2 & a_m b_2 \\ \textcolor{orange}{a_0 b_1} & \textcolor{yellow}{a_1 b_1} & \textcolor{green}{a_2 b_1} & a_3 b_1 & \dots & a_{m-3} b_1 & a_{m-2} b_1 & a_{m-1} b_1 & a_m b_1 \\ \textcolor{red}{a_0 b_0} & \textcolor{orange}{a_1 b_0} & \textcolor{yellow}{a_2 b_0} & \textcolor{green}{a_3 b_0} & \dots & a_{m-3} b_0 & a_{m-2} b_0 & a_{m-1} b_0 & a_m b_0 \\ \end {array} \begin{array}{ccccccccc} a_{m+1} b_n \\ a_{m+1} b_{n-1} & a_{m+2} b_{n-1} \\ a_{m+1} b_{n-2} & a_{m+2} b_{n-2} & a_{m+3} b_{n-2} \\ a_{m+1} b_{n-3} & a_{m+2} b_{n-3} & a_{m+3} b_{n-3} & a_{m+4} b_{n-3} \\ \vdots & \vdots & \vdots & \vdots \\ a_{m+1} b_3 & a_{m+2} b_3 & a_{m+3} b_3 & a_{m+4} b_3 & \dots & a_{m+n-3} b_3 \\ a_{m+1} b_2 & a_{m+2} b_2 & a_{m+3} b_2 & a_{m+4} b_2 & \dots & a_{m+n-3} b_2 & a_{m+n-2} b_2 \\ a_{m+1} b_1 & a_{m+2} b_1 & a_{m+3} b_1 & a_{m+4} b_1 & \dots & a_{m+n-3} b_1 & a_{m+n-2} b_1 & a_{m+n-1} b_1 \\ a_{m+1} b_0 & a_{m+2} b_0 & a_{m+3} b_0 & a_{m+4} b_0 & \dots & a_{m+n-3} b_0 & a_{m+n-2} b_0 & a_{m+n-1} b_0 & a_{m+n} b_0 \\ \end {array} \\ \end {array} \)

Example

The following example is not yet fully worked out.

\( \begin{aligned} a &= \{ \underset{a_0}{0}, \underset{a_1}{1}, \underset{a_2}{2}, \underset{a_3}{3}, \underset{a_4}{4} \} \\ b &= \{ \underset{b_0}{0}, \underset{b_1}{1}, \underset{b_2}{2}, \underset{b_3}{3} \} \\ \end {aligned} \)

\( \begin{aligned} \sum_{i=0}^4 a_i &= 0 + 1 + 2 + 3 + 4 &&= 10 \\ \sum_{j=0}^3 b_j &= 0 + 1 + 2 + 3 &&= 6 \\ \end {aligned} \)

\( \begin{aligned} \sum_{i=0}^4 a_i \sum_{j=0}^3 b_j &= \sum_{i=0}^4 \sum_{j=0}^3 a_i b_j = \sum_{k=0}^7 \sum_{i+j=k} a_i b_j \\ &= \sum_{i+j=0} a_i b_j + \sum_{i+j=1} a_i b_j + \sum_{i+j=2} a_i b_j + \sum_{i+j=3} a_i b_j + \sum_{i+j=4} a_i b_j + \sum_{i+j=5} a_i b_j + \sum_{i+j=6} a_i b_j + \sum_{i+j=7} a_i b_j \\ &= (a_0 b_0) + (a_0 b_1 + a_1 b_0) + (a_0 b_2 + a_1 b_1 + a_2 b_0) + (a_0 b_3 + a_1 b_2 + a_2 b_1 + a_3 b_0) + \dotsb \\ &= \sum_{k=0}^7 \sum_{j=0}^{k} a_{k-j} b_j \\ &= \underbrace{\sum_{j=0}^{0} a_{0-j} b_j}_{1 \text{ term}} + \underbrace{\sum_{j=0}^{1} a_{1-j} b_j}_{2 \text{ terms}} + \underbrace{\sum_{j=0}^{2} a_{2-j} b_j}_{3 \text{ terms}} + \underbrace{\sum_{j=0}^{3} a_{3-j} b_j}_{4 \text{ terms}} + \underbrace{\sum_{j=0}^{4} a_{4-j} b_j}_{5 \text{ terms}} + \sum_{j=0}^{5} a_{5-j} b_j + \sum_{j=0}^{6} a_{6-j} b_j + \sum_{j=0}^{7} a_{7-j} b_j \\ &= a_0 b_0 + (a_1 b_0 + a_0 b_1) \\ \end {aligned} \)

\( \begin{array}{c|c|c|c|c} a_0 b_3 & a_1 b_3 & a_2 b_3 & a_3 b_3 & a_4 b_3 \\ a_0 b_2 & a_1 b_2 & a_2 b_2 & a_3 b_2 & a_4 b_2 \\ a_0 b_1 & a_1 b_1 & a_2 b_1 & a_3 b_1 & a_4 b_1 \\ a_0 b_0 & a_1 b_0 & a_2 b_0 & a_3 b_0 & a_4 b_0 \\ \end {array} \)

\( \begin{array}{c|c|c|c|c} 0 \times 3 & 1 \times 3 & 2 \times 3 & 3 \times 3 & 4 \times 3 \\ 0 \times 2 & 1 \times 2 & 2 \times 2 & 3 \times 2 & 4 \times 2 \\ \textcolor{orange}{0 \times 1} & 1 \times 1 & 2 \times 1 & 3 \times 1 & 4 \times 1 \\ \textcolor{red}{0 \times 0} & \textcolor{orange}{1 \times 0} & 2 \times 0 & 3 \times 0 & 4 \times 0 \\ \end {array} \)

\( \begin{array}{c|cccccccc} k = 0 & 4 & 3 & 2 & 1 & 0 \\ & & & & & 0 & 1 & 2 & 3 \\ \\ k = 1 & 4 & 3 & 2 & 1 & 0 \\ & & & & 0 & 1 & 2 & 3 \\ \\ k = 2 & 4 & 3 & 2 & 1 & 0 \\ & & & 0 & 1 & 2 & 3 \\ \\ k = 3 & 4 & 3 & 2 & 1 & 0 \\ & & 0 & 1 & 2 & 3 \\ \\ k = 4 & 4 & 3 & 2 & 1 & 0 \\ & 0 & 1 & 2 & 3 \\ \\ k = 5 & & 4 & 3 & 2 & 1 & 0 \\ & 0 & 1 & 2 & 3 \\ \\ k = 6 & & & 4 & 3 & 2 & 1 & 0 \\ & 0 & 1 & 2 & 3 \\ \\ k = 7 & & & & 4 & 3 & 2 & 1 & 0 \\ & 0 & 1 & 2 & 3 \\ \\ \end {array} \)

Finite Sum #

Given a sequence \(a_1, a_2, \dotsc, a_n\) of numbers where \(n\) is a nonnegative integer the finite sum \(a_1 + a_2 + \dotsb + a_n\) can be expressed as

\(\begin{aligned} \sum_{k = 1}^n a_k \end{aligned}\)

If \(n = 0\) then the summation is defined to be \(0\). The value of a finite series is always well-defined and the order in which its terms are added does not matter.

Infinite Sum #

Given an infinite sequence \(a_1, a_2, \dotsc\) of numbers the infinite sum \(a_1 + a_2 + \dotsb\) can be expressed as

\(\begin{aligned} \sum_{k = 1}^\infty a_k = \lim_{n \to \infty} \sum_{k = 1}^n a_k \end{aligned}\)

If the limit does not exist then the series diverges; otherwise, it converges. The terms of a convergent series cannot always be added in any order. However, the terms of an absolutely convergent series can be rearranged. (An absolutely convergent series \(\sum_{k = 1}^\infty a_k\) is a series for which the series \(\sum_{k = 1}^\infty |a_k|\) also converges.)

Linearity #

For any real number \(c\) and any finite sequences \(a_1, a_2, \dotsc, a_n\) and \(b_1, b_2, \dotsc, b_n\)

\(\begin{aligned} \sum_{k = 1}^n (c a_k + b_k) = c \sum_{k = 1}^n a_k + \sum_{k = 1}^n b_k \end{aligned}\)

\(\begin{aligned} \sum_{k = 1}^n \Theta(f(k)) = \Theta \left( \sum_{k = 1}^n f(k) \right) \end{aligned}\)

In this latter equation, the \(\Theta\)-notation on the left-hand side applies to the variable \(k\) but on the right-hand side it applies to the variable \(n\).

These linearity properties also holds for infinite convergent series.

Arithmetic Series #

The summation

\(\begin{aligned} \sum_{k = 1}^n k = 1 + 2 + \dotsb + n \end{aligned}\)

is an arithmetic series and has the value

\(\begin{aligned} \sum_{k = 1}^n k = \frac{n(n + 1)}{2} = \Theta(n^2) \end{aligned}\)

Gauss’ Proof

\( \begin{aligned} S &= 1 && + && 2 && + && \dotsb && + && n - 1 && + && n \\ S &= n && + && n - 1 && + && \dotsb && + && 2 && + && 1 \\ 2S &= (n + 1) && + && (n + 1) && + && \dotsb && + && (n + 1) && + && (n + 1) \\ &= n(n + 1) \\ S &= \frac{n(n + 1)}{2} \end {aligned} \)

\(\blacksquare\)

Proof by Mathematical Induction

\(n = 1 \implies \sum_{k = 1}^1 k = 1 = \frac{1 \times (1 + 1)}{2}\)

Assume that \(\sum_{k = 1}^n k = \frac{n(n + 1)}{2}\) up to \(n\) and show that it also holds for \(n + 1\).

\( \begin{aligned} \sum_{k = 1}^{n + 1} k = \left( \sum_{k = 1}^n k \right) + n + 1 = \frac{n(n + 1)}{2} + n + 1 = \frac{n(n + 1) + 2(n + 1)}{2} = \frac{(n + 1)((n + 1) + 1)}{2} \end {aligned} \)

\(\blacksquare\)

A general arithmetic series includes an additive constant \(a \ge 0\) and a constant coefficient \(b \gt 0\) in each term, but has the same total asymptotically.

\(\begin{aligned} \sum_{k = 1}^n (a + bk) = \Theta(n^2) \end{aligned}\)

Sum of Squares #

\(\begin{aligned} \sum_{k = 0}^n k^2 = \frac{n(n + 1)(2n + 1)}{6} \end{aligned}\)

On the one hand, the telescoping series

\( \begin{aligned} \sum_{k = 1}^n (k + 1)^3 - k^3 = (n + 1)^3 - 1 = n^3 + 3n^2 + 3n \end {aligned} \)

On the other hand,

\( \begin{aligned} \sum_{k = 1}^n (k + 1)^3 - k^3 &= \sum_{k = 1}^n (k + 1)(k^2 + 2k + 1) - k^3 = \sum_{k = 1}^n 3k^2 + 3k + 1 \\ &= 3 \sum_{k = 1}^n k^2 + 3 \sum_{k = 1}^n k + \sum_{k = 1}^n 1 \\ &= 3 \sum_{k = 1}^n k^2 + 3 \times \frac{n(n + 1)}{2} + n \\ &= 3S + \frac{3}{2} n^2 + \frac{3}{2} n + n \\ &= 3S + \frac{3}{2} n^2 + \frac{5}{2} n \\ \end {aligned} \)

And so

\( \begin{aligned} 3S + \frac{3}{2} n^2 + \frac{5}{2} n &= n^3 + 3n^2 + 3n \\ 3S &= n^3 + \frac{3}{2} n^2 + \frac{1}{2} n \\ 3S &= \frac{2n^3 + 3n^2 + n}{2} \\ S &= \frac{n(n + 1)(2n + 1)}{6} \\ \end {aligned} \)

Sum of Cubes #

\(\begin{aligned} \sum_{k = 0}^n k^3 = \left( \frac{n(n + 1)}{2} \right)^2 = \frac{n^2 (n + 1)^2}{4} \end{aligned}\)

Geometric Series #

For real \(x \ne 1\) the summation

\(\begin{aligned} \sum_{k = 0}^n x^k = 1 + x + x^2 + \dotsb + x^n \end{aligned}\)

is a geometric series and has the value

\(\begin{aligned} \sum_{k = 0}^n x^k = \frac{x^{n + 1} - 1}{x - 1} \end{aligned}\)

The infinite decreasing geometric series occurs when the summation is infinite and \(|x| \lt 1\)

\(\begin{aligned} \sum_{k = 0}^\infty x^k = \frac{1}{1 - x} \end{aligned}\)

If we assume that \(0^0 = 1\) these formulas apply even when \(x = 0\).

Integrating and differentiating formulas yield additional formulas. For example, differentiate the infinite decreasing geometric series and then multiply it by \(x\).

\( \begin{aligned} x \cdot \frac{d}{dx} \left( \sum_{k = 0}^\infty x^k \right) &= x \cdot \frac{d}{dx} \left( \frac{1}{1 - x} \right) \\ \sum_{k = 0}^\infty x \cdot \frac{d}{dx} (x^k) &= x \cdot \frac{d}{dx} \left( \frac{1}{1 - x} \right) \\ \sum_{k = 0}^\infty kx^k &= \frac{x}{(1 - x)^2} \\ \end {aligned} \)

And so we also have

\(\begin{aligned} \sum_{k = 0}^\infty kx^k = \frac{x}{(1 - x)^2} \end{aligned}\)

for \(|x| \lt 1\).

Harmonic Series #

For positive integers \(n\) the \(n\)-th harmonic number is

\(\begin{aligned} H_n = 1 + \frac{1}{2} + \frac{1}{3} + \dotsb + \frac{1}{n} = \sum_{k = 1}^n \frac{1}{k} = \ln n + O(1) \end{aligned}\)

\(\ln (n + 1) \le H_n \le \ln n + 1\)

Telescoping Series #

For any sequence \(a_0, a_1, \dotsc, a_n\)

\(\begin{aligned} \sum_{k = 1}^n (a_k - a_{k - 1}) = a_n - a_0 \end{aligned}\)

since each of the terms \(a_1, a_2, \dotsc, a_{n - 1}\) is added in exactly once and substracted out exactly once. We say that the sum telescopes.

Similarly

\(\begin{aligned} \sum_{k = 0}^{n - 1} (a_k - a_{k + 1}) = a_0 - a_n \end{aligned}\)

EXAMPLE

\( \begin{aligned} \sum_{k = 1}^{n - 1} \frac{1}{k(k + 1)} = \sum_{k = 1}^{n - 1} \left( \frac{1}{k} - \frac{1}{k + 1} \right) = 1 - \frac{1}{n} \end {aligned} \)

Re-indexing summations #

A series can sometimes be simplified by changing its index, often reversing the order of summation. Generally, if the summation index appears in the body of the sum with a minus sign, it’s worth thinking about re-indexing.

EXAMPLE

\( \begin{aligned} \sum_{k = 0}^n a_{n - k} = a_n + a_{n - 1} + \dotsb + a_1 + a_0 = a_0 + a_1 + \dotsb + a_{n - 1} + a_n = \sum_{j = 0}^n a_j && \text{where}\,\,\, j = n - k \end {aligned} \)

EXAMPLE

\( \begin{aligned} \sum_{k = 1}^n \frac{1}{n - k + 1} = \frac{1}{n} + \frac{1}{n - 1} + \dotsb + \frac{1}{2} + 1 = 1 + \frac{1}{2} + \dotsb + \frac{1}{n - 1} + \frac{1}{n} = \sum_{j = 1}^n \frac{1}{j} && \text{where}\,\,\, j = n - k + 1 \end {aligned} \)

Products #

The finite product \(a_1 a_2 \dotsm a_n\) can be expressed as

\(\begin{aligned} \prod_{k = 1}^n a_k \end{aligned}\)

If \(n = 0\) then the product is defined to be \(1\).

Converting between summations and products #

\( \begin{aligned} \lg \left( \prod_{k = 1}^n a_k \right) = \sum_{k = 1}^n \lg a_k \end {aligned} \)

Summations and asymptotic analysis #

Mathematical induction can be used to prove an upper or lower bound on a summation.

EXAMPLE

Prove the asymptotic upper bound \(\sum_{k = 0}^n 3^k = O(3^n)\). In other words, prove \(\sum_{k = 0}^n 3^k \le c3^n\) for some constant \(c\) for all sufficiently large \(n\).

Proof by Mathematical Induction

Basis: show that the bound holds for \(n = 0\).

\(n = 0 \implies \sum_{k = 0}^0 3^k = 1 \le c \cdot 1\) as long as \(c \ge 1\).

Assume that the bound holds for \(n\) and show that it also holds for \(n + 1\).

\( \begin{aligned} \sum_{k = 0}^{n + 1} 3^k = \left( \sum_{k = 0}^n 3^k \right) + 3^{n + 1} \le c3^n + 3^{n + 1} = \left( \frac{1}{3} + \frac{1}{c} \right) c3^{n + 1} \le c3^{n + 1} \end {aligned} \)

as long as \(\frac{1}{3} + \frac{1}{c} \le 1 \iff \frac{1}{c} \le \frac{2}{3} \iff c \ge \frac{3}{2}\)

\(\blacksquare\)

EXAMPLE

Prove the asymptotic upper bound \(\sum_{k = 1}^n k = O(n^2)\). In other words, prove \(\sum_{k = 1}^n k \le cn^2\) for some constant \(c\) for all sufficiently large \(n\).

Basis: show that the bound holds for \(n = 1\).

\(n = 1 \implies \sum_{k = 1}^1 k = 1 \le c \cdot 1^2\) as long as \(c \ge 1\).

Inductive step: assume that the bound holds for \(n\) and show that it also holds for \(n + 1\).

\( \begin{aligned} \sum_{k = 1}^{n + 1} k = \left( \sum_{k = 1}^n k \right) + n + 1 \le cn^2 + n + 1 \le cn^2 + n + 1 + ((c - 1)n + c(n + 1) - 1) = c(n + 1)^2 \end {aligned} \)

\( \begin{aligned} cn^2 + n + 1 + ((c - 1)n + c(n + 1) - 1) &= cn^2 + n + 1 + (cn - n + cn + c - 1) \\ &= cn^2 + n + 1 + 2cn - n + c - 1 \\ &= cn^2 + 2cn + c \\ &= c(n^2 + 2n + 1) \\ &= c(n + 1)^2 \\ \end {aligned} \)