小蓝书 16.3 题解

传送门：小蓝书16.3

---

例题

例1

求解下列递推式的通项 \[ a_0=-1,~a_1=1 \\[6pt]a_n=2 a_{n-1}+3 a_{n-2}+3^n,~n>1 \] 解：

记 \(F(x)=\sum_{n=0}^{\infty} a_n x^n\) ，并定义 \(a_x=0(x<0)\) 。

考虑把原式写成一个方程 \[ a_n = 2a_{n-1} + 3a_{n-2} + 3^n - 2\times [n=0] \] 两边同时乘上 \(x^n\) 并求和 \[ \sum_{n \ge 0}a_nx^n = 2\sum_{n\ge 0}a_{n-1}x^n + 3\sum_{n\ge 0}a_{n-2}x^n + \sum_{n\ge 0}3^nx^n - 2 \] 即 \[ F(x) = 2xF(x) + 3x^2F(x) + \frac{6x-1}{1-3x} \] 解得 \[ (1-2 x-3 x^2)F(x) = \frac{6 x-1}{1-3 x} \] 因此 \[ F(x) =\frac{6 x-1}{(1+x)(1-3 x)^2}=\frac{A}{1+x}+\frac{B}{(1-3 x)^2}+\frac{C}{1-3 x} \tag{1} \] 因为我们无需考虑 \(x\) 的解析意义，所以我们可以进行以下操作

将 \((1)\) 两侧乘上 \((1+x)\) 后令 \(x=-1\) 得 \[ A = \left.\frac{6x-1}{(1-3x)^2}\right|_{x=-1} = -\frac{7}{16} \] 将 \((1)\) 两侧乘上 \((1 + 3x)^2\) 后令 \(x = \frac{1}{3}\) 得 \[ B = \left.\frac{6x-1}{1+x}\right|_{x=\frac{1}{3}} = \frac{3}{4} \] 将 \((1)\) 两侧乘上 \(x\) ，并令 \(x \to \infty\) 可得 \[ \lim_{x\to \infty}\frac{x(6 x-1)}{(1+x)(1-3 x)^2} =\lim _{x \rightarrow \infty}\left(\frac{A x}{1+x}+\frac{B x}{(1-3 x)^2}+\frac{C x}{1-3 x}\right) \] 左侧因为分子的次数小于分母的次数，趋于 \(0\) ，于是 \[ \begin{aligned} 0 &=\lim _{x \rightarrow \infty}\left(\frac{A x}{1+x}+\frac{B x}{(1-3 x)^2}+\frac{C x}{1-3 x}\right) \\[6pt]&=\lim _{x \rightarrow \infty}\left(\frac{A}{\frac{1}{x}+1}+\frac{B x}{(1-3 x)^2}+\frac{C}{\frac{1}{x}-3}\right) \\[6pt]&=A-\frac{1}{3} C \end{aligned} \] 解得 \(C=-\frac{21}{16}\) 。于是 \[ \begin{aligned} F(x) &=-\frac{7}{16(1+x)}+\frac{3}{4(1-3 x)^2}-\frac{21}{16(1-3 x)} \\ &=-\frac{7}{16} \sum_{n \ge 0}(-1)^n x^n+\frac{3}{4} \sum_{n \ge 0}\left(\begin{array}{c} n+2-1 \\ 2-1 \end{array}\right) \cdot 3^n x^n-\frac{21}{16} \sum_{n \ge 0} 3^n x^n \\ &=\sum_{n \ge 0}\left[\frac{(4 n-3) \cdot 3^{n+1}-7(-1)^n}{16}\right] x^n \\ \end{aligned} \] 即 \[ a_n=\frac{1}{16}\left[(4 n-3) \cdot 3^{n+1}-7(-1)^n\right] \] 当然这是小蓝书上的写法，不仔细想一想简直不知道在干什么。我们回到这一步 \[ F(x) =\frac{6 x-1}{(1+x)(1-3 x)^2}=\frac{A}{1+x}+\frac{B}{(1-3 x)^2}+\frac{C}{1-3 x} \tag{1} \] 直接通分不就好了吗 \[ \frac{9 A x^2-6 A x+A+B x+B-3 C x^2-2 C x+C}{(x+1)(3 x-1)^2} \] 整理一下可得 \[ \begin{cases} 9A - 3C = 0 \\[6pt]-6A+B-2C = 6 \\[6pt]A + B + C = -1 \end{cases} \] 解得 \[ \left\{\begin{array}{l} A=-\frac{7}{16} \\ B=\frac{3}{4} \\ C=-\frac{21}{16} \end{array}\right. \] 虽然不是很优雅，但是确实有暴力的美感（确信）。

例2

求证：对一切正整数 \(n\) 有 \[ \sum _{i=0}^{n}\binom{2n+1}{2i}\binom{2i}{i}2^{2n-2i+1} = \binom{4n+2}{2n+1} \] 证明：

首先 \((1+x)^{4n+2} = \sum_{i=0}^{4n+2}\binom{4n+2}{i}x^i\) 中 \(x^{2n+1}\) 的系数为 \(\binom{4n+2}{2n+1}\) 。其次 \[ \begin{aligned} (1 + x)^{4n+2} &= ((1 + x^2) + 2x)^{2n+1} \\[6pt]&=\sum_{k=0}^{2n+1}\binom{2n+1}{k}(1 + x^2)^k(2x)^{2n+1-k} \\[6pt]&=\sum_{k=0}^{2n+1} \binom{2n+1}{k} 2^{2n+1-k}x^{2n+1-k}\sum_{j=0}^{k} \binom{k}{j} x^{2j} \end{aligned} \] 中 \(x^{2n+1}\) 的系数为 \(\sum_{i=0}^{n}\binom{2n+1}{2i}2^{2n+1-2i}\binom{2i}{i}\) ，所以 \[ \sum _{i=0}^{n}\binom{2n+1}{2i}\binom{2i}{i}2^{2n-2i+1} = \binom{4n+2}{2n+1} \] 证毕。

例3

求证： \[ \sum_{k=0}^{\left\lfloor\frac{n-1}{2}\right\rfloor}(-1)^k\binom{n+1}{k}\binom{2n-2k-1}{n} = \frac{1}{2}n(n+1) \quad(n \ge 1) \] 证明：

首先 \((1+x)^{n+1} = \sum_{k=0}^{n+1}\binom{n+1}{k}x^k\) 中 \(x^{n-1}\) 的系数为 \[ \binom{n+1}{n-1} = \binom{n+1}{2} = \frac{1}{2}n(n+1) \] 其次 \[ \begin{aligned} (1+x)^{n+1} &= \frac{(1-x^2)^{n+1}}{(1-x)^{n+1}} \\&=\left(\sum_{k=0}^{n}(-1)^k\binom{n+1}{k}x^{2k}\right)\left(\sum_{j=0}^{\infty}\binom{n+j}{j}x^j\right) \end{aligned} \] 中 \(x^{n-1}\) 的系数为 \[ \begin{aligned} &\sum_{k=0}^{\left\lfloor\frac{n-1}{2}\right\rfloor}(-1)^{k}\binom{n+1}{k}\binom{n+(n-1-2k)}{n} \\[4pt]=&\sum_{k=0}^{\left\lfloor\frac{n-1}{2}\right\rfloor}(-1)^{k}\binom{n+1}{k}\binom{2n-2k-1}{n} \end{aligned} \] 所以 \[ \sum_{k=0}^{\left\lfloor\frac{n-1}{2}\right\rfloor}(-1)^k\binom{n+1}{k}\binom{2n-2k-1}{n} = \frac{1}{2}n(n+1) \] 证毕。

---

其他例题还在咕咕咕。