Brace yourselves for a wall of equations. These are really just for me, I like them and wanted to have a list.

Chapter is about sums of the general form:

$$$a_1+a_2+a_3+ \dotsm +a_n \text{,}$$$

Where each $$a_k$$ is called a term.

Sigma notation

$$$\sum_{k=1}^n a_k$$$

We called it a “term” in previous notation. Here they’re called summand.

Another way to write in Sigma notation

$$$\sum_{1 \leq k \leq n} a_k$$$

For any recurrence of the form

$$$a_nT_n = b_nT_{n-1}+c_n$$$

The solution is

$$$T_n = \frac{1}{s_na_n} \left( s_1b_1T_0 + \sum_{k=1}^ns_kc_k \right)$$$

If we can find a summation factor of the form

$$$s_n = \frac{a_{n-1}a_{n-2} \dots a_1 }{b_nb_{n-1} \dots b_2 }$$$

Harmonic numbers appear everywhere.

$$$H_n = 1 + \frac{1}{2} + \dotsm + \frac{1}{n} = \sum_{k=1}^n \frac{1}{k}$$$

Distributive law

$$$\sum_{k \in K}ca_k = c \sum_{k \in K}a_k$$$

Associative law

$$$\sum_{k \in K} (a_k + b_k) = \sum_{k \in K}a_k + \sum_{k \in K}b_k$$$

Commutative law (permutative law)

$$$\sum_{k \in K}a_k = \sum_{p(k) \in K}a_{p(k)}$$$

To combine different sets of indices

$$$\sum_{k \in K}a_k + \sum_{k \in K’}a_k = \sum_{k \in K \cap K’}a_k + \sum_{k \in K \cup K’}a_k$$$

Perturbation method

$$$S_n + a_{n+1} = \sum_{0 \leq k \leq n+1}a_k = a_0 + \sum_{0 \leq k \leq n}a_{k+1}$$$

Interchanging the order of summation

$$$\sum_j\sum_k a_{j,k}[P(j,k)] = \sum_{P(j,k)}a_{j,k} = \sum_k\sum_j a_{j,k}[P(j,k)]$$$

Variation “vanilla” of interchanging the order of summation

$$$\sum_{j \in J}\sum_{k \in K}a_{j,k} = \sum_{\substack{j \in J \\ k \in K}}a_{j,k} = \sum_{k \in K}\sum_{j \in J} a_{j,k}$$$

Variation “rocky road” $$\sum_{j \in J}\sum_{k \in K(j)}a_{j,k} = \sum_{k \in K’}\sum_{j \in J’(k)}a_{j,k}$$

$$\left( \sum_{k=1}^na_k \right) \left( \sum_{k=1}^nb_k \right) = n \sum_{1 \leq j < k \leq n} (a_k - a_j)(b_k-b_j)$$

In commutative law, when $$p(k)$$ is instead any arbitrary function $$f$$

$$$\sum_{j \in J}a_{f(j)} = \sum_{k \in K}a_k \# f^-(k)$$$ $$$\sum_{j \in J}a_{f(j)} = \sum_{f(j) \in K}a_{f(j)} = \sum_{k \in K}a_k$$$
\begin{align} \Delta f(x) & = f(x+1) - f(x) \\ x^{\underline{m}} & = \overbrace{x(x-1)\dots (x-m+1)}^{m\; \text{factors}} \\ x^{\overline{m}} & = \overbrace{x(x+1) \dots (x+m-1)}^{m \; \text{factors}} \\ x^{\underline{-m}} & = \frac{1}{(x+1)(x+2)\dots (x+m)} \\ \Delta(x^{\underline{m}}) & = mx^{\underline{m-1}} \\ x^{\underline{m+n}} & = x^{\underline{m}}(x-m)^{\underline{n}} \end{align} \begin{align} g(x) & = \Delta f(x) \iff \sum g(x) \delta x = f(x) + C \\ \sum_a^bg(x)\delta x & = \sum_{k=a}^{b-1}g(k) = \sum_{a \leq k < b}g(k) \\ \sum_a^bg(x) \delta x & = f(x)\bigg\rvert_a^b = f(b) - f(a) \\ \sum_a^bg(x) \delta x & + \sum_b^cg(x) \delta x = \sum_a^cg(x)\delta x \end{align}

These rules applied, give

$$$\sum_{0 \leq k < n}k^{\underline{m}} = \frac{k^{\underline{m+1}}}{m+1}\bigg\rvert_0^n = \frac{n^{\underline{m+1}}}{m+1}$$$

Summation by parts

$$$\sum u \Delta v = uv - \sum Ev \Delta u$$$