- 求和
- 差分
- 有限积分（前缀和）
- 二项式反演
求和
对于递推式：
T_0 = \alpha \\
a_nT_n = b_nT_{n - 1} + c_n \tag{1.1}
求出第 n 项的通项公式。
引入求和因子 s_n，满足：
s_{n - 1}a_{n - 1} = s_nb_n \tag{1.2}
令
S_n =\begin{cases}
T_0 & n = 0 \\
s_na_nT_n & n > 0
\end{cases} \tag{1.3}
则重写递归式我们可以得到：
\begin{aligned}
S_n &= s_na_nT_n\\
&= s_nb_nT_{n - 1}+s_nc_n \\
&=s_{n - 1}a_{n-1}T_{n - 1} + s_nc_n \\
&=S_{n - 1} + s_nc_n
\end{aligned} \tag{1.4}
故我们得到了：
S_n = S_{n - 1} + s_nc_n \tag{1.5}
发现这是一个前缀和的形式，改写成和式为：
S_n = T_0 + \sum_{i = 1}^n s_ic_i \tag{1.6}
又由于：
s_n = \dfrac{a_{n - 1}}{b_n} \times s_{n - 1} \tag{1.7}
这是一个前缀积的形式，改写成积式为：
s_n = s_0 \times \prod_{i = 1}^{n} \dfrac{a_{i - 1}}{b_i} \tag{1.8}
由于 s_0 没有定义，但不难发现应该为单位元 1，所以：
s_n = \prod_{i = 1}^n \dfrac{a_{i - 1}}{b_i} \tag{1.9}
那么有：
\begin{aligned}
\color{red}
T_n &= \dfrac{S_n}{s_na_n} \\
& \color{red} = (a_n \times \prod_{i = 1}^n \dfrac{a_{i - 1}}{b_i})^{-1} * (T_0 + \sum_{i = 1}^n s_ic_i)
\end{aligned} \tag{1.10}
差分
定义
对于函数 f(x)，定义映射 E^a : f(x) \mapsto f(x + a)，特别的，记 E^1 为 E，记 E^0 为 I。
\Delta f(x) = E - I \tag{2.1.1}
即
\Delta : f(x) \mapsto f(x + 1) - f(x) \tag{2.1.2}
定义 k 阶差分：
\begin{aligned}
\color{red}
\Delta^k f(x) &= \Delta(\Delta^{k - 1} f(x)) \\
&= (E - I)^k f(x) \\
&= \sum_{i = 0}^k \binom{k}{i}E^k(-I)^{k - i}f(x) \\
&\color{red}= \sum_{i = 0}^k \binom{k}{i}(-1)^{k - i}f(x + k)
\end{aligned} \tag{2.1.3}
性质
差分为线性符号。
\begin{aligned}
\color{red}
\Delta(c\times f(x)) &= c\times f(x + 1) - c \times f(x) \\
&\color{red}= c\times \Delta(f(x))
\end{aligned} \tag{2.2.1}
\begin{aligned}
\color{red}
\Delta(u(x) + v(x)) &= u(x + 1) + v(x + 1) - u(x) + v(x) \\
&\color{red}= \Delta(u(x)) - \Delta(v(x))
\end{aligned} \tag{2.2.2}
\begin{aligned}
\color{red}
\Delta(u(x) \times v(x)) &= u(x + 1) \times v(x + 1) - u(x) \times v(x) \\
&= u(x + 1) \times v(x + 1) - u(x) \times v(x) + u(x) \times v(x + 1) - u(x) \times v(x + 1) \\
&= v(x + 1) \times [u(x + 1) - u(x)] - u(x) \times [v(x + 1) - v(x)] \\
&\color{red}= E(v(x)) \times \Delta(u(x)) - u(x) \times \Delta(v(x))
\end{aligned} \tag{2.2.3}
结论
\color{red}\Delta(x^{\underline{n}}) = n \times x^{\underline{n - 1}} \tag{2.3.1}
可以发现上述性质与 (x^n)' = n \times x^{n - 1} 十分类似。
\color{red}\Delta(a^x) = (a - 1) \times a^x \tag{2.3.2}
可以发现上述性质与 (a^x)' = \ln a \times a ^x 有些类似。
有限积分
定义
有限积分符号：
\sum_{k = a}^b f(k) \tag{3.1.1}
表示对于所有 k \in [a, b] 的 f(k) 的和。
对于函数 f(x) 的离散反导函数，可以简写为 \sum f(x)
性质
类似积分基本定理，我们有：
\color{red}\sum_{k = a}^b f(k) = g(b + 1) - g(a) \tag{3.2.1}
其中，g(x) 为 f(x) 的离散反导函数，满足 \Delta(g(x)) = f(x)。
有限积分符号为线性符号。
\color{red}\sum [c \times f(x)] = c \times \sum f(x) \tag{3.2.2}
乘法分配律。
\color{red}\sum [u(x) + v(x)] = \sum u(x) + \sum v(x) \tag{3.2.3}
\color{red} \sum[u(x) \times \Delta(v(x))] = u(x) \times v(x) - \sum \Delta(u(x))E(v(x)) \tag{3.2.4}
上式可以从 (2.2.3) 变形而得。
结论
\color{red} \sum x^{\underline{n}} =
\begin{cases}
\dfrac{x^{\underline{n + 1}}}{n + 1} & n \neq -1 \\
H_x & n = -1
\end{cases} \tag{3.3.1}
\color{red} \sum a^x =
\begin{cases}
\dfrac{a^x}{a - 1} & a \neq 1 \\
x & a = 1
\end{cases} \tag{3.3.2}
\color{red}\sum x^n = \sum_{k = 0}^nS_{n, k} \times \dfrac{(n + 1)^{\underline{k +1}}}{k + 1} \tag{3.3.3}
二项式反演
反演原理
对于和式：
\begin{aligned}
&g_{n}=\sum_{k=0}^{n} a_{n, k} f_{k}\\
&f_{n}=\sum_{k=0}^{n} b_{n, k} g_{k}
\end{aligned}
如果对于所有合法的 m，都有：
\sum_{k = m}^n a_{n, k} \times b_{k, m} = [n = m]
那么：
\color{red}g_{n}=\sum_{k=0}^{n} a_{n, k} f_{k} \Longleftrightarrow f_{n}=\sum_{k=0}^{n} b_{n, k} g_{k}
\text{proof}:
将 g_{n}=\sum_{k=0}^{n} a_{n, k} f_{k} 带入 f_{n}=\sum_{k=0}^{n} b_{n, k} g_{k}
g_{n}=\sum_{k=0}^{n} a_{n, k} \sum_{m=0}^{k} b_{k, m} g_{m}=\sum_{m=0}^{n} g_{m} \sum_{k=m}^{n} a_{n, k} b_{k, m}
如果有：\sum_{k=m}^{n} a_{n, k} b_{k, m}=[n=m] 则 :
g_{n}=\sum_{m=0}^{n} g_{m}[n=m]=g_{n}
所以有：
g_{n}=\sum_{k=0}^{n} a_{n, k} f_{k} \Leftarrow f_{n}=\sum_{k=0}^{n} b_{n, k} g_{k}
用类似的方法可以得到：
g_{n}=\sum_{k=0}^{n} a_{n, k} f_{k} \Rightarrow f_{n}=\sum_{k=0}^{n} b_{n, k} g_{k}
综上有：
g_{n}=\sum_{k=0}^{n} a_{n, k} f_{k} \Longleftrightarrow f_{n}=\sum_{k=0}^{n} b_{n, k} g_{k}
二项式反演
离散麦克劳伦公式：
对于 n 次多项式 f(x)，有：
f(x) = \sum_{k = 0}^n \binom{x}{k} \Delta^kf(0)
而对于 (2.1.3)，我们有：
\Delta^k(f(0)) = \sum_{i = 0}^k \binom{k}{i}(-1)^{k - i}f(k)
令 u_n = \Delta^nf(0), v_n = f(n)，那么有：
u_n = \sum_{i = 0}^k \binom{k}{i}(-1)^{k - i}v_k \\
v_n = \sum_{k = 0}^n \binom{n}{k} u_k
则我们希望得到：
u_n = \sum_{k = 0}^n \binom{n}{k}(-1)^kv_k \Longleftrightarrow
v_n = \sum_{k = 0}^n \binom{n}{k} u_k
\text{proof}:
令 u_k \leftarrow (-1)^k u_k 根据反演原理，只要：
\begin{aligned}
[n = m ] &= \sum_{k = m}^n \binom{n}{k}(-1)^k \binom{k}{m}(-1)^m \\
&= (-1)^m\sum_{k = m}^n (-1)^k \times \dfrac{n!}{k! \times (n - k)!} \times \dfrac{k!}{m! \times (k - m)!} \times \dfrac{(n - m)!}{(n - m)!} \\
&= (-1)^m \sum_{k = m}^n (-1)^k \times \dfrac{n!}{m! \times (n -m)!} \times \dfrac{(n - m!)}{(n - k)! \times (k - m)!} \\
&= (-1)^m \sum_{k = m}^n (-1)^k \binom{n}{m} \binom{n - m}{n - k} \\
&= (-1)^m \binom{n}{m} \sum_{k = m}^n (-1)^k \binom{n - m}{n - k} \\
&= (-1)^m \binom{n}{m} \sum_{k = 0}^{n - m} (-1)^{n - k} \binom{n - m}{n - m - k} \\
&= (-1)^m \binom{n}{m} \sum_{k = 0}^{n - m} (-1)^{n - k} \binom{n - m}{k} \\
&= (-1)^{m + n} \binom{n}{m} \sum_{k = 0}^{n - m} (-1)^k \binom{n - m}{k}1^{n - m - k}\\
&= (-1)^{m + n} \binom{n}{m} (1 - 1)^{n - m} \\
&= (-1)^{m + n} \binom{n}{m} 0^{n - m}
\end{aligned}
当 m \neq n 时，上式显然为 0。而 n = m 时，等于 1。故满足反演原理。
故：
\color{red}
u_n = \sum_{k = 0}^n \binom{n}{k}(-1)^kv_k \Longleftrightarrow
v_n = \sum_{k = 0}^n \binom{n}{k} u_k