小蓝书 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)$$

证毕。

---

其他例题还在咕咕咕。