谈谈和式处理
可爱的小棉羊
·
·
算法·理论
主要讲述具体数学第二章的内容。
万恶之源
f_n=\sum_{i=1}^ni^2
这个式子的通项公式是什么？
1. 百度优先搜索
)
这应该不算个方法，但我们可以以此了解更多。
好的，随便点一个看看就知道怎么做了。
2. 猜测法
昨天晚玩原神，我看到了这个式子，我猜答案就是这个吧！
我们不妨猜测；
f_n=\dfrac{n(n+1)(2n+1)}{6}
我们如何证明呢？这时就要使出数学归纳法了。
什么是数学归纳法？
注意：虽然他名字里有归纳，但是还是非常严谨的。
一般来讲一个数学归纳法有两个命题需证：
-
证明命题 P(1) 成立。
-
假设 \forall i \in [1,n] ,P(i) 都成立，证明 P(n+1) 也成立。
这时我们可以说明 \forall i \in [1,\infty) ,P(i) 都成立。
注意：这里的两个命题通俗点就是边界和转移，我们不一定要把命题限那么死。
比如 《具体数学》 第 1 章习题 9：
P(n):\prod^n_{i=1}x_i \le (\dfrac{\sum^{n}_{i=1}x_i}{n})^n, \forall i \in [1,n] ,x_i\ge0
-
令 x_n=\dfrac{(\sum^{n-1}_{i=1}x_i)}{n-1} 证明 P(n) \Rightarrow P(n-1)
-
证明 P(2) 且 P(n) \Rightarrow P(2n)
-
通过上面两个证明，来说明对于所有 n 都成立。
这个大家自己证。
现在我们证明刚才那个问题就简单了。
显然 f_1=\dfrac{1\times (1+1)\times{(2\times1+1)}}{6}=1 成立。
假设 f_n 都满足这个公式。
那么 f_{n+1}=f_n+n^2=\dfrac{n(n+1)(2n+1)}{6}+n^2=\dfrac{(n+1)(n+1+1)(2(n+1)+1)}{6}
显然我们证明对于所有 n 都成立。
但是这个方法嘛，缺点很明显，我们除非是上辈子拯救了世界攒了巨量 RP，否则我们猜个两三年都没有结果。
而下面的每一种方法可以让我们百分百出金（bushi 得到答案。
3. 扰动法
我们先看一个和式：
(\sum_{i=1}^na_i)+a_{n+1}=\sum^{n}_{i=0}a_{i+1}
我们就是要在这个 \sum^n_{i=0}a_{i+1} 上做手脚来求出通项。
我们得到：
\sum_{i=1}^{n}i^2+(n+1)^2 &=\sum_{i=0}^{n}(i+1)^2\\&=\sum_{i=0}^{n}(i^2+2i+1)\\&=\sum_{i=1}^{n}i^2+2\sum_{i=1}^{n}i+(n+1)\\
\end{aligned}
很难受，我们的 \sum_{i=1}^{n}i^2 被抵消掉了，但我们明白了一个规律：
2\sum^{n}_{i=1}i=n(n+1)
由上面那个式子得到的。我们一样的道理，既然可以用 \sum^n_{i=1}i^2 得到 \sum_{i=1}^n i 的通项，那么可不可以用 \sum^n_{i=1}i^3 得到 \sum_{i=1}^n i^2 的通项呢？
\sum_{i=1}^{n}i^3+(n+1)^3 &=\sum_{i=0}^{n}(i+1)^3 \\
&=\sum_{i=0}^{n}(i^3+3i^2+3i+1) \\
&=\sum_{i=1}^{n}i^3+3\sum_{i=1}^{n}i^2+3\sum_{i=1}^{n}i+(n+1) \\
\end{aligned}
把它当成一个关于 \sum_{i=1}^{n}i^2 的方程来解。
\sum_{i=1}^{n}i^3+(n+1)^3=\sum_{i=1}^{n}i^3+3\sum_{i=1}^{n}i^2+3\sum_{i=1}^{n}i+(n+1)
3\sum^n_{i=1}i^2=(n+1)^3-3\sum_{i=1}^ni-n-1
3\sum^n_{i=1}i^2=n^3+3n^2+3n+1-3\times \frac{n(n+1)}{2}-n-1
展开再做点因式分解就推出来了。
对于这种求法，我看过另一种表达方式：
(1+1)^3-1^3=3\times1^2+3\times1^1+1
(2+1)^3-2^3=3\times2^2+3\times2^1+1
(3+1)^3-3^3=3\times3^2+3\times3^1+1
我们得到：
(n+1)^3-n^3=3n^2+3n+1
将上述式子相加：
\sum^n_{i=1}(i+1)^3-i^3=3\sum^n_{i=1}i^2+3\sum^n_{i=1}i+n
左边相互抵消得到：
(n+1)^3-1=3\sum^n_{i=1}i^2+3\sum^n_{i=1}i+n
同理可求。
4. 微积分
总所周知：
\int_{0}^{n} n^2\mathrm{d}x=\frac{n^3}{3}
我们可以发现，我们的 f_n 和这个 \frac{n^3}{3} 误差不大。
我们不妨令 E_n=f_n-\frac{n^3}{3}。
那么：
E_n&=f_n-\frac{n^3}{3}\\
&=f_{n-1}+n^2-\frac{n^3}{3}\\
&=f_{n-1}-\frac {n^3}3+\frac{3n^2}3-\frac{3n}{3}+\frac{1}{3}-\frac 1 3+n\\
&=f_{n-1}-\frac{(n-1)^3}{3}-\frac{1}{3}+n\\
&=E_{n-1}+n-\frac 13
\end{aligned}
那我们得到：
\sum^n_{i=1}(i-\frac{1}{3})=\frac{n(n+1)}{2}-\frac n3=E_n
&=\frac{n(n+1)}2-\frac{n(n^2-1)}{3}\\
&=\frac{3n(n+1)}6-\frac{2n(n+1)(n-1)}6\\
&=\frac{n(n+1)(2n+1)}6
\end{aligned}
得到答案。
5. 成套方法
我们先来讲讲成套方法。
我们假设有这样的一个递推式：
R_1=\alpha
R_n=R_{n-1}+\beta+\gamma n
怎么求通解呢？
我们这时就要用成套方法了 （这个名字的来源，我也不知道，我也不敢问。）
首先这个递推式，一看就很线性，我们不妨假设：
R_n=A(n)\alpha+B(n)\beta+C(n)\gamma
我们如何求 A(n),B(n),C(n) 呢？
先假设 R_n=1。
我们显然有：\alpha=1,\beta=\gamma=0
代入得：R_n=A(n)=1.
接着假设 $R_n=n$。
我们有 $\alpha=1,\beta=1,\gamma=0$。
我们代入得：$R_n=A(n)+B(n)=n
那么 B(n)=n-1。
再令 R_n=n^2，我们有 \alpha=1,\beta=-1,\gamma=2。
得到 R_n=n^2=A(n)-B(n)+2C(n)。
该咋做都会了吧。
进入正题，我们该如何求这个式子呢？
我们把刚才得过程推广一下：
R_1=\alpha
R_n=R_{n-1}+\beta+\gamma n+\delta n^2
一样令：
R_n=A(n)\alpha+B(n)\beta+C(n)\gamma+D(n)\delta
我们令 R_n=n^3，那么 \alpha=1,\beta=1,\gamma=-3,\delta=3。
得到 A(n)+B(n)-3C(n)+D(n)=n^3。
显然可求 D(n)，令 \alpha=\beta=\gamma=0,\delta=1，得到 R_n=f_n=D(n)，这样我们就得到了答案。
6. 展开与放缩
不妨把这个变成一个二重和式：
\begin{aligned}f_n=\sum_{i=1}^ni^2&=\sum_{i=1}^n\sum_{j=1}^ii\\&=\sum_{i=1}^n\sum^{n-i+1}_{j=1}(n-j+1)\\&=\sum_{i=1}^n\frac{(n+i)(n-i+1)}{2}\\&=\frac 1 2\sum_{i=frac{}{} 1}^nn(n+1)-ni-i^2+(n+1)i\\&=\frac 1 2\sum_{i=1}^nn(n+1)-i^2+i\\&=\frac {n^2(n+1)-f_n+\frac{n(n+1)}2} 2\\&=\frac{n^2(n+1)}2+\frac{n(n+1)}4-\frac{1}{2}f_n\\&=\frac{(2n+1)n(n+1)}4-\frac{1}{2}f_n\end{aligned}
我们得到了答案。
7. 有限微积分
我们先看一个小学奥数的例子：
\sum^n_{i=1}\frac{1}{i(i+1)}
这个式子该怎么求，当年小学的做法是：
\sum_{i=1}^n\frac{1}{i(i+1)}&=\sum^{n}_{i=1}(\frac{1}{i}-\frac{1}{i+1})\\
&=\sum_{i=1}^n\frac{1}{i}-\sum^{n}_{i=1}\frac 1 {i+1}\\
&=(1+\sum_{i=2}^n\frac 1i)-(\sum_{i=2}^n\frac{1}{i}+\frac{1}{n+1})\\
&=\frac{n}{n+1}
\end{aligned}
等我们看了看书，才发现，这玩意非常像前缀和和差分啊！
为啥这么说呢？
我们发现这个方法的本质就是对于数列 a_i，找到一个数列使得 a_i=b_{i+1}-b_i，让他们相互抵消，使得得到答案为 b_{n+1}-b_1。
和前缀和差不多，使用两个端点处的值，让来表示一个区间的和，刚才的 b_i 就像是在前缀和。
那么这种方法可以推广吗？
当然可以。
我们来一起进入有限微积分的定义。
在高等数学中我们有一个东西叫求导。
f'(x)=\lim_{\Delta x\to 0}\frac{f(x+\Delta x)-f(x)}{\Delta x}
细细观察我们发现这玩意很像差分。
那么我们在离散数学中不妨定义算子 \Delta。
\Delta f(x)=f(x+1)-f(x)
那么我们不妨猜想，对于有限微积分又没有和无限微积分一样或者差不多的性质呢？
那我们来看看 (x^n)'=nx^{n-1} 是否在有限微积分上成立。
\Delta (x^n)=(x+1)^n-x^n
感觉很难计算了，次幂好像不是那么适合有限微积分，我们发现这样一个东西：上升下降幂。
定义：
x^{\overline{n}}=\prod^n_{i=1}(x+i-1)=x(x+1)(x+2)\cdot\cdot\cdot(x+n-1)
x^{\underline{n}}=\prod^n_{i=1}(x-i+1)=x(x-1)(x-2)\cdot\cdot\cdot(x-n+1)
我们神奇地发现：
\Delta(x^{\underline{n}})=nx^{\underline{n-1}}
既然有微分，那么我们也来定义一下积分吧！
定义：
令 \Delta f(x)=g(x)，那么：\sum^b_ag(x)\delta x=f(x)\mid^b_a=f(b)-f(a)
按照刚才的规律，我们知道 \sum^b_ag(x)\delta x=\sum^{b-1}_{i=a}g(i)
有了这玩意，我们再来看看这两个东西各有什么性质。
-
-
-
关于乘法的运算法则：
&=f(x+1)(\Delta g(x)+g(x))-f(x)g(x)\\
&=f(x+1)\Delta g(x)+(f(x+1)-f(x))g(x)\\
&=f(x+1)\Delta(x)+\Delta f(x)g(x)
\end{aligned}
再定义算子 E 为 Ef(x)=f(x+1)。
我们就得到了分布求和法则：
\Delta(f(x)g(x))=Ef(x)\Delta g(x)+\Delta f(x)g(x)
来扯正题：
如何计算那个万恶之源呢？
我们先算 \sum^{n+1}_1x^{\underline{k}}\delta x 吧。
发现 \Delta\frac{x^{\underline{k+1}}}{k+1}=x^{\underline k}。
那么有：
\sum_{i=0}^{n-1}i^{\underline{k}}=\sum^{n}_0x^{\underline{k}}\delta x=\frac{x^{\underline{k+1}}}{k+1}\mid^{n}_0=\frac{n^{\underline{k+1}}}{k+1}
注意到：i^2=i^{\underline{2}}+i^{\underline{1}}。
那么有：
\sum_{i=0}^{n-1}i^{2}=\sum^{n}_0(x^{\underline{2}}+x^{\underline{1}})\delta x=\frac{2x(x-1)(x-2)}6+\frac{3x(x-1)}6=\frac{n(n-1)(2n-1)}{6}
这里是 f_{n-1} 的再加上 1 就行了。
8. 生成函数
原来的《具体数学》上是一个努伯利数得到任意方幂的通解，很复杂，我找了个简单一点的搞法，以后再补。
我们令 \sum^n_{i=0}f_ix^i 是数列 f 的普通生成函数，那这有什么用呢？
我们要求这个东西的封闭形式，什么意思呢？
我们拿数列 f_n=1（\langle 1,1,1,1....\rangle） 举例，我们设 F 为他的生成函数。
我们可以得到 F(x)=xF(x)+1，那么 F(x)=\frac{1}{1-x}。
这个结果看起来很唐，某些时候发散的可以算成收敛的，但这不影响。
接着搞出广义二项式定理：
原来的二项式定理是：
(a+b)^n=\sum^n_{i=0}\binom n i a^ib^{n-1}
但我们推广把它推广到 n<0 的情况：
(a+b)^n=\sum^\infty_{i=0}\frac{n^{\underline{i}}}{i!}a^ib^{n-i}
用这两个唐氏的卧龙凤雏一算，欸，好像还对得上。
我们先推一个小式子：
&=\sum^\infty_{i=0}\frac{(-n)^{\underline{i}}}{i!}(-x)^i\\
&=\sum^{\infty}_{i=0}\frac{(n+i-1)^{\underline{i}}}{i!}x^i\\
&=\sum^{\infty}_{i=0}\binom{n+i-1}ix^i\\
&=\sum^{\infty}_{i=0}\binom{n+i-1}{n-1}x^i
\end{aligned}
同时我们又发现：
对于 g 的生成函数 G(x)，我们与刚才的那玩意相乘：
F(x)G(x)=\sum^\infty_{i=0}\sum_{j+k=i}f_jg_k
F(x)G(x)=\sum^\infty_{i=0}\sum^i_{j=0}g_j
相当于求了遍前缀和，现在我们可以愉快地推式子了。
我们知道：
\sum^n_{i=0}x^i=\frac{1}{1-x}
对他求个导，得到：
\sum^n_{i=0}(i+1)x^{i}=\frac{1}{(1-x)^2}
继续乘上 x。
\sum^\infty_{i=1}ix^i=\frac{x}{(1-x)^2}
最后求个前缀和：
\sum^\infty_{i=1}\sum_{j=0}^ijx^i=\frac{x}{(1-x)^3}
我们求出 n 次项的次数就相当于 \sum^n_{i=1}i。
那我们从等式右边入手：
\frac{x}{(1-x)^3}&=x\sum^\infty_{i=0}\binom {2+i}{2}x^i\\
&=\sum^\infty_{i=0}\binom{1+i} 2x^i
\end{aligned}
我们得出答案 \sum_{i=1}^ni=\frac{(n+1)n}2。
我们回到上一步就是这里：
\sum^\infty_{i=0}ix^i=\frac{x}{(1-x)^2}
再求一个导，乘上一个 x:
\sum^\infty_{i=0}i^2x^i=\frac{x^2+x}{(1-x)^3}
最后我们求前缀和就得到了 \frac{x^2+x}{(1-x)^4}。
我们考虑分开算对于 x 这就是 n-1 次项系数，而对于 x^2 他的贡献是 n-2 次项系数：
\frac{1}{(1-x)^4}=\sum^{\infty}_{i=0}\binom{3+i}3x^i
答案为 \binom {2+n}3+\binom{1+n}3=\frac{n(n+1)(2n+1)}6
也推出了结果。
希望这篇文章对你有所帮助！