Summation

1. Direct Methods

求和，第一步应该考虑得到是 \(induction\) ，即 归纳 .

e.g. 1

计算 \(n\) 个奇数的和 : \(S_n=\sum\limits_{k=1}^{n} (2k-1)\) .

通过简单的找规律，可以猜测 , \(S_n=n^2\) .

归纳可得 : \(S_n+(2n+1)=n^2+2n+1=(n+1)^2\)

但是，归纳法的不足在于要有能力正确 “猜测” 答案 . 并且，有的时候很难做到从 \(n\) 推导到 \(n+1\) 的正确性 .

e.g. 2

\(a_1,a_2,a_3,\cdots,a_n\) 是一系列实数 . 证明

\[\sqrt[n]{a_1a_2\cdots a_n}\leq\frac{a_1+a_2+\cdots+a_n}{n} \]

或许比较阳间的表达，

\[a_1a_2\cdots a_n\leq ( \frac{a_1+a_2+\cdots a_n}{n} ) ^n \]

\(n=1\) 和 \(n=2\) 容易看出符合此规律 .

但是，不易从 \(n\) 推到到 \(n+1\) . 此时，从两个方向来考虑，

\[(a)\ (Pn)\Longrightarrow (P(n-1))\\ (b)\ (P(n))\and(P2)\Longrightarrow P(2n) \]

首先证明 \((a)\) , 设 \(b=\sum\limits_{i=1}^{n-1}\frac{a_i}{n-1}\) 得到，

\[(\prod\limits_{k=1}^{n+1}a_k)\sum\limits_{k=1}^{n-1}\frac{a_k}{n-1}=(\prod\limits_{k=1}^{n+1}a_k)b\ \leq\ (\frac{\sum_{k=1}^{n-1}a_k+b}{n})^n =(\frac{n\sum_{k=1}^{n-1}a_k}{n(n-1)})^n=(\frac{1}{n-1})^n(\sum_{k=1}^{n-1}a_k)^n \]

得到，

\[\prod\limits_{k=1}^{n-1}a_k\leq (\frac{1}{n-1})^{n-1}(\sum\limits_{k=1}^{n-1}a_k)^{n-1} \]

因此，\((a)\) 得证 .

对于 \((b)\) ,

\[\prod_{k=1}^{2n} a_k=(\prod\limits_{k=1}^{n}a_k)(\prod\limits_{k=n+1}^{2n}a_k)\leq (\sum\limits_{k=1}^{n} \frac{a_k}{n})^n(\sum\limits_{k=n+1}^{2n}\frac{a_k}{n})^n\leq (\frac{1}{2})^{2n} (\sum_{k=1}^{2n}\frac{a_k}{n})^{2n}=(\frac{1}{2n})^{2n}(\sum\limits_{k=1}^{2n} a_k)^{2n} \]

因此， \((b)\) 得证 .

另一个方法，就是提出第一项和最后一项 .

令 \(S_n=\sum_{k=1}^{n}a_k\) ，可得

\[S_{n+1}=S_n+a_{n+1}=a_0+\sum\limits_{k=1}^{n+1}a_k=a_0+\sum\limits_{k=0}^{n}a_{k+1} \]

通过比较 \(S_n\) 和 \(\sum_{k=0}^{n} a_{k+1}\) 得到求和公式 .

e.g. 3

\(S_n=1+a^1+a^2+\cdots+a^n=\sum\limits_{k=0}^{n}a^k\) .

\(S_{n+1}=S_n+a^{n+1}=a_0+\sum\limits_{k=0}^{n}a^{k+1}=1+a\sum\limits_{k=0}^{n}a^k=1+aS_n\) .

通过 \(S_n+a^{n+1}=1+aS_n\) 便可以推出 \(S_n=\frac{a^{n+1}-1}{a-1},a\not=1\) .

e.g. 4

\(S_n=\sum\limits_{k=0}^{n} k2^k\) .

\(S_{n+1}=S_n+(n+1)2^{n+1}=\sum\limits_{k=0}^n(k+1)2^{k+1}=2\sum\limits_{k=0}^{n}k2^k+s\sum\limits_{k=0}^{n}2^k=2S_n+2^{n+2}-2\) .

得到，\(S_n=(n-1)2^{n-1}+2\) .

对于一些求和的相对简单的式子，形如 \(T(n),n\geq 0\) 满足

\[T_0=\alpha\\ a_nT_n=b_nT_{n-1}+c_n\ \ \ \ \ (n>1) \]

我们可以用 \(T_{n-1},T_{n-2},T_{n-3},\cdots,T_0\) 表示 \(T_n\) . 表达式中含有 , \(a_k,b_k,c_k\) 和 \(\alpha\) .

设 \(s_n\) 满足，\(s_{n-1}a_{n-1}=s_nb_n\) .

将上式左右两边同时乘上 \(s_n\) , 令 \(S_n=s_na_nT_n\) ，可以得到，

\[S_n=s_n(b_nT_{n-1}+c_n)=S_{n-1}+s_nc_n\\ S_n=\sum\limits_{k=1}^{n} s_kc_k+s_0a_0T_0\\ T_n=\frac{1}{s_na_n} (\sum\limits_{k=1}^n s_kc_k+s_0a_0T_0) \]

非常轻松地得到了递推式，问题在于怎么得到 \(s_n\) .

\[s_n=\frac{a_{n-1}s_{n-1}}{b_n}=\frac{a_{n-1}b_{n-2}s_{n-2}}{b_nb_{n-1}}=\cdots=\frac{a_{n-1}a_{n-2}\cdots a_0}{b_nb_{n-1}\cdots b_1},s_0=1 \]

前提条件为 \(a_i,b_j\) 不能为 \(0\) .

e.g. 5

定义 \(D_n\) 为长度为 \(n\) 的排列的错排数 . 有 \(D_1=0,D_2=1\) . 考虑 \(n\geq 3\) 的时候怎么得到 .

用 \(\pi(i)\) 表示第 \(i\) 个位置最后被填入的数字 .

首先考虑 \(\pi(1)\) 的值，有 \(n-1\) 种选择，从 \(2\) 到 \(n\) . 接下来，面临两种情况，\(\pi(i)=1\) 和 \(\pi(i)\not=1\) .

考虑 \(\pi(i)=1\) 的情况，得到

\[\pi=\begin{pmatrix} 1\ \ \ \cdots\ \ \ i\ \ \ \cdots\ \ \ n\\ i\ \ \ \cdots\ \ \ 1\ \ \ \cdots\ \ \ \pi(n) \end{pmatrix} \]

显然剩下的情况的 \(n-2\) 个数的分配方案为 \(D_{n-2}\) .

考虑 \(\pi(i)\not=1\) 的情况，得到

\[\pi=\begin{pmatrix} 1 &\cdots &i &\cdots &n\\ i &\cdots &\pi(i)\not=1 &\cdots &\pi(n) \end{pmatrix} \]

将 \(1\rightarrow i\) 那么，剩下的情况和刚才一摸一样，情况数为 \(D_{n-1}\) .

即可得到递推式 , \(D_n=(n-1)(D_{n-1}+D_{n-2})\) .

可以得到

\[\begin{align} D_n-nD_{n-1}&=-(D_{n-1}-(n-1)D_{n-2})\\ &=D_{n-2}-(n-2)D_{n-3}\\ &\cdots\\ &=(-1)^{n-1}(D_1-D_0)=(-1)^n \end{align} \]

所以，

\[D_n=nD_{n-1}+(-1)^n\ \ \ \ (n\geq 1) \]

此时，可以带入上述公式， \(a_n=1,b_n=n,c_n=(-1)^n\) . \(s_n=\frac{1}{n!}\) .

\[D_n=n!(\sum\limits_{k=1}^{n}\frac{(-1)^k}{k!}+1)=n!\sum\limits_{k=0}^{n}\frac{(-1)^k}{k!} \]

此时，可以得到，

\[\frac{D_n}{n!}=\sum\limits_{k=0}^{n}\frac{(-1)^k}{k!} \]

当 \(n\to \infty\) , \(\frac{D_n}{n!}\to e^{-1}>\frac{1}{3}\) .

这个式子有个通俗易懂的理解方式，当你的书被风吹走后，散落之后，每一页页码都不在原来的位置上的概率是大于 \(\frac{1}{3}\) 的 .