1. From Sums to Recurences.
The general idea is that $$ S_n = \sum _{i = i} ^n a_i $$
can be writen as:
$$ \begin{cases} S_0 &=& 0\cr S_n &=& S _{n-1} + a_n \end{cases} $$
In the last post of Rpertoire Method, we have seen how to compute the sum of constant-efficient polynomials.
2. From Recurences to Sums
We will talk about the following recurence: $$ a_nT_n = b_nT _{n-1} + c_n $$ We want to find a summation factor to change the recurence to a sum.
Assume $s_n$ is a factor to be determined. We multiply both side of the recurence by $s_n$: $$s_na_nT_n = s_nb_nT _{n-1} + s_nc_n,$$ where $n\ge 1$.
We want this recurence to be a recurence induced by a sum. So we assume $$ s_n b_n = s _{n-1} a _{n-1}.$$
We write $S_n = s_n a_n T_n$, then we get $S_n = S _{n-1} + s_nc_n$.
That is, $$S_n = S_0 + \sum _{i = 1} ^n s_ic_i$$ (Since $n\ge 1$)
Now let’s find a factor $s_n$. The only condition is $$ \frac{s_n}{s _{n-1}} = \frac{a _{n-1}}{b_n}$$ and we only need to find only one such kind of factor, so it is safe to assume $s_1 = 1$. Usually we choose $$ s_n = \frac{s_n}{s _{n-1}} \frac{s _{n-1}}{s _{n-2}}… \frac{s_2}{s_1} s_1 = \frac{a _{n-1}a _{n-2}…a_1}{b _{n}b _{n-1} … b_2} $$
This will lead to $$ T_n = \frac{1}{s_na_n}(\sum _{i = 1}^n s_i c_i + s_1b_1T_0) $$
Example 2.1
$$ \begin{cases} C_0 &=& 0, \cr C_n &=& n+1 + \frac{2}{n}\sum _{k = 0}^{n-1}C_k. \end{cases} $$
First we eliminate the sum in the recurence by replacement of index and subtraction: $$nC_n - (n-1)C _{n-1} = 2n + 2C _{n-1}, \ \ n>1$$ We can check that this also holds when $n=1$ So the original recurence can be reduced to : $$ \begin{cases} C_0 &= 0 \cr nC_n &= (n+1)C _{n-1} + 2n \end{cases} $$
In this case, $$\begin{cases} a_n &= n\cr b_n &= n + 1\cr c_n &= 2n \end{cases} $$
We set $$s_n = \frac{a _{n-1}…a_1}{b_n…b_2} = \frac{2}{n(n+1)}.$$ Then we have $\sum _{i=1}^n s_ic_i= \sum _{i=1}^n \frac{4}{i+1}$.
Finally, we get $$ C_n = 2(n+1)\sum _{k=1}^n \frac{1}{k+1} $$
With $H_n = \sum _{k = 1}^n \frac{1}{k}$, we can rewrite $C_n$ as $$C_n = 2(n+1)H_n - 2n$$
3. Manipulation of Sums
3.1 Rearrangement
We treat the indices in a sum as a set, then we can manipulate it using set operation.
Example 3.1.1
Prove: $$(\sum _{k=1}^n a_k)(\sum _{k=1}^n b_k) = n\sum _{k = 1}^n a_k b_k - \sum _{1\le j<k\le n}(a_k - a_j)(b_k - b_j)$$
Proof. $$ \begin{split} S = \sum _{1\le j<k\le n}(a_k - a_j)(b_k - b_j) = \sum _{1 \le k < j \le n} (a_k - a_j)(b_k - b_j) \end{split} $$ $$ \begin{split} 2S &= \sum _{1 \le j, k \le n}(a_j - a_k)(b_j - b_k) - \sum _{1 \le j=k \le n} (a_j - a_k) (b_j - b_k)\cr &=\sum _{1 \le j, k \le n}(a_j - a_k)(b_j - b_k)\cr &=\sum _{1 \le j, k \le n} (a_j b_j - a_j b _k - a_k b_j + a_k b_k) \cr & =2n \sum _{k = 1} ^ n a_kb_k - 2(\sum _{k = 1}^n a_k) (\sum _{k = 1} ^ n b_k) \end{split} $$
Example 3.1.2
Prove Lagrange’s Identity: $$ (\sum _{k = 1} ^n a_k^2)(\sum _{k = 1} ^n b_k^2) = (\sum _{k=1}^n a_k b_k)^2 + \sum _{1 \le j < k \le n} (a_kb_j - a_jb_k)^2 $$
Proof. $$ S = \sum _{1 \le j < k \le n} (a_kb_j - a_jb_k)^2 = \sum _{1 \le k < j \le n} (a_kb_j - a_jb_k)^2 $$ $$ \begin{split} 2S = & \sum _{1 \le j, k \le n} (a_kb_j - a_jb_k)^2\cr =& \sum _{1 \le j, k \le n} (a_k^2 b_j^2 - 2a_jb_ja_kb_k + a_j^2 b_k^2)\cr =& 2(\sum _{k = 1} ^n a_k^2)(\sum _{k = 1}^n b_k^2) - 2(\sum _{k =1} ^n a_kb_k)(\sum _{k = 1}^n a_kb_k) \end{split} $$
3.2 Perturbation Method
$$S_n + a _{n+1} = a_0 + \sum _{k=1} ^{n+1} a_k = a_0 + \sum _{k=0}^n a _{k+1}$$
Example 3.2.1
$$ S_n = \sum _{0 \le k \le n} k 2^k $$
$$ \begin{split} S_n + (n +1)2^ {n+1} &= \sum _{k = 0}^n (k+1)2 ^{k+1}\cr &= 2S_n + 2\sum _{k = 0}^n 2 ^{k} \end{split} $$
4. Finite Calculus
4.1 Definitions
Difference operator: $$\Delta f(x) = f(x+1) - f(x)$$
Discrete Integral: $$\Sigma_a^b = \sum _{[a,b)}$$
Note that we cannot include the right end of $[a, b)$, since we the integral should be transitive, that is, $$ \Sigma_a^b + \Sigma_b^c = \Sigma_a^c $$
Shift operator: $$Ef(x) = f(x+1)$$
Discrete power: $$ x ^{ \underline{m}} = \begin{cases} x(x-1)…(x-m+1), &m\ge 0\cr \frac{1}{(x+1)…(x+m)}, &m<0 \end{cases} $$
4.2 Properties
$$x ^{\underline{m} + \underline{n}} = x ^{\underline{m}} (x-m) ^{\underline{n}}$$ $$\Delta x ^{\underline{m}} = m x ^{\underline{m-1}}$$ $$\Sigma x ^{\underline{m}} = \begin{cases} \frac{x^{\underline{m+1}}}{m+1} +C,&m \not =-1\cr H_x + C, &m = -1 \end{cases} $$ $$ \Delta c^x = (c-1)c^x$$ $$\Delta (uv) = u\Delta v + Ev \Delta u$$ $$\Sigma u \Delta v = uv - \Sigma Ev\Delta u$$
Example 4.2.1
$$\Sigma x 2^x = \Sigma x \Delta 2^x = x 2^x - \Sigma 2 ^{x+1} \Delta x = x 2^x - 2^{x+1} + C$$
$$ \begin{split} \Sigma x H_x &= \Sigma x ^{\underline{1}}H_x = \frac{1}{2}\Sigma H_x \Delta x ^{\underline{2}} \cr &=\frac{1}{2}H_x x^{\underline{2}} - \frac{1}{2}\Sigma x^{\underline{-1}}(x - (-1))^{\underline{2}}\cr &=\frac{1}{2}H_x x^{\underline{2}} - \frac{1}{2}\Sigma x^{\underline{1}} = \frac{1}{2}x^{\underline{2}}H_x - \frac{1}{4}x^{\underline{2}} + C \end{split} $$