摘要 本文旨在探讨生成函数在高中数学中解决数列问题的应用. 生成函数, 作为一种强大的数学工具, 允许我们将数列以形式幂级数的方式表示, 从而简化了许多复杂的数列问题. 文章首先介绍了生成函数的基本概念和定义, 包括其与序列的关系、系数的提取方法以及生成函数的加法和乘法运算规则. 随后, 通过一系列精选例题, 展示了生成函数在解决递推数列、寻找数列通项公式以及数列求和问题中的实际应用. 文章还详细讨论了如何从生成函数的封闭形式中还原出原始序列, 并提供了一些基础序列的生成函数封闭形式示例. 最后, 文章通过解决具体的数列问题, 如斐波那契数列和卡特兰数列, 进一步证明了生成函数在数学教育中的实际价值和解决问题的高效性.

关键词 生成函数; 数列; 幂级数; 泰勒展开; 组合数; 通项公式; 数列求和

0. 术语约定

• 自然数集 $\mathbb{N} = \{0,1,2,3,...\}$, $\mathbb{N}^+ = \{1,2,3,...\}$.

• 设 $\mathbb{P}$ 是某一数域, 如整数域、有理数域、实数域, $\mathbb{P}_{*} = \mathbb{P}-\{0\}$ 代表去掉 $0$ 元后的数域.

• 用 $\{a_i:i\in\mathbb{N}\}$ 来表示如下序列

$$ a_0,a_1,a_2,a_3,...,a_k,... $$

其中 $a_i$ 可以是 $\mathbb{P}$ 里的数字, 也可以是生成函数, 或者其它的东西, 总之用序列来表示一组有序对象.

• 本文中的序列均指无穷序列.
• 对于一个数字序列 $\{a_i\in\mathbb{P}\}$,若 $\exists k\in\mathbb{N}$, 使得 $\forall n > k$ 有 $a_n = 0$, 则称该序列为有限序列, 意思这个无穷序列在某一项后均为 $0$.
• 本文中的组合数不表示为 $C_{n}^{r}$, 而表示为 ${n \choose r}$, 二者定义基本相同, 但后者定义范围更广泛.

1. 生成函数定义

在这篇文章中, 首先会抛弃掉生成函数作为 “函数” 的意义, 认为它只序列的另一种表示方式, 然后再逐步证明这个 “ 序列” 具有的种种 “函数” 性质.

生成函数, 也称形式幂级数, 多项式.

设有序列 $\{a_i:a_i\in\mathbb{P}\}$. 根据序列 $\{a_i\}$, 生成函数 $f(x)$ 被定义为

$$ f(x)= a_0+a_1x+a_2x^2+a_3x^3+...+a_nx^n+... $$

也可以简记为

$$ f(x)=\sum_{i=0}^\infty a_ix^i $$

在生成函数 $f(x)$ 中, $x$ 不是未知数, 它只是一个占位符, $x^i$ 用来标记它是第几个占位符.

对于 $f(x)$ 第 $i$ 位上的 $a_i$, 我们记作 $f[i]$, $f[i]$ 也被称作 $f(x)$ 的第 $i$ 次项系数, 简称 $i$ 次项.

特别的有 $f(x)$ 的 $0$ 次项称作常数项. 于是

$$ f(x)=\sum_{i=0}^{\infty}f[i]x^i $$

$$ f(x)=f[0]+f[1]x+f[2]x^2+f[3]x^3+...+f[n]x^n+... $$

$\sum\limits^{\infty} $ 在这里的意义并不是无穷项求和, 上述定义看似是无穷项的求和, 实质上只是一个记号, 只是对序列的另一种表达方式, 因为目前已经抛弃掉生成函数作为函数的意义, 这一点尤为值得注意. 在下文, 会逐步证明 $\sum\limits^{\infty}$ 代表序列的意义与生成函数无穷项求和的意义是等价的.

为了提取序列中的某一项系数方便, 也记

$$ [x^i]f(x)=f[i] $$

这并不是多此一举, 比如提取 $1+x-2x^2+3x^3$ 的二次项系数可以简记为 $[x^2](1+x-2x^2+3x^3)$ . 对于两个生成函数 $f(x)$ 与 $g(x)$, $f(x) = g(x)$ 当且仅当 $\forall i\in\mathbb{N}$ 均满足 $f[i] = g[i]$ ,这阐明了生成函数相等的概念.

若产生生成函数 $f(x)$ 的序列 $\{f[i]\}$ 是有限序列, 则称 $f(x)$ 是有限多项式、有限幂级数, 否则称 $f(x)$ 是无穷多项式、无穷幂级数.

若 $f(x)$ 是有限多项式, 它的最高次项为 $n$, 也可以将 $f(x)$ 记为

$$ f(x)=\sum_{i=0}^nf[i]x^i $$

或者

$$ f(x)=f[0]+f[1]x+f[2]x^2+...+f[n]x^n $$

注意, 这仍然不意味着上述两种记法中, 符号 $\sum _{i = 0}^n$ 或 $+ $ 意味着有限项求和, 它们仍然只是对有限序列的另一种表达方式, 因为我们还未定义关于生成函数的加法运算.

例如:

1. 除第 $0$ 项为 $a\in\mathbb{P}$ 外的项皆为 $0$ 的序列 $\{a,0,0,0,...\}$ , 它产生的生成函数为

$$ f(x)=\sum_{i=0}^0f[i]x^i=a $$

1. 序列 $\{1,-2,1,-3,0,0,0,...\}$ 产生的生成函数为

$$ f(x)=\sum_{i=0}^3f[i]x^i=1-2x+x^2-3x^3 $$

2. 生成函数的基本运算

限于篇幅及高中范围内实用程度, 仅介绍加法运算和乘法运算.

加法运算

设 $f(x)$ 与 $g(x)$ 是两个生成函数, 它们之间进行加法运算的结果也是一个生成函数, 记作 $f(x)+g(x)$,满足

$$ [x^i](f(x)+g(x))=f[i]+g[i]\quad(i\in\mathbb{N}) $$

于是 $$ f(x)+g(x)=\sum_{i=0}^{\infty}(f[i]+g[i])x^i $$

$\mathbb{P}$ 内的数字对加法满足交换律和结合律, 因此可以直接推出生成函数对加法运算满足交换律和结合律, 也就是说

$$ f(x)+g(x)=g(x)+f(x) $$

$$ (f(x)+g(x))+h(x)=f(x)+(g(x)+h(x)) $$

根据生成函数的加法运算, 我们可以定义对生成函数的求和式.

设 $f_i(x)\left(i = 1,2,...,n\right)$ 是一组生成函数, 定义它们的有限项求和

$$ \begin{align} \sum_{i=1}^n f_i(x)&=f_1(x)+f_2(x)+f_3(x)+\cdots+f_n(x)\\ &=\sum_{j=0}^\infty\left(\sum_{i=1}^nf_i[j]\right)x^j \end{align} $$

这里仍然强调一下, 这并不是说 $\sum\limits^{\infty}$ 与 $\sum\limits^{n}$ 这两个求和可交换次序, 前者是对序列的一种表达方式, 后者是对生成函数或普通数字的有限项求和, 也就是说对生成函数求和后体现的是下面的一个新序列

$$ \left\{\left(\sum_{i=1}^nf_i[j]\right):j\in\mathbb{N}\right\} $$

乘法运算

对于两个生成函数 $f(x)$ 与 $g(x)$ ,对它们做乘法运算的结果也是一个生成函数, 记作 $f(x)\cdot g(x)$ 或简写成 $f(x)g(x)$, 满足

$$ [x^i]f(x)g(x)=\sum_{j=0}^if[j]g[i-j] $$

相当于

$$ f(x)g(x)=\sum_{i=0}^\infty\left(\sum_{j=0}^if[j]g[i-j]\right)x^i $$

与生成函数的加法运算类似, 乘法运算也满足交换律和结合律, 同时乘法运算对加法运算还满足分配律, 也就是说

$$ \begin{gathered} \begin{aligned} f(x)g(x)&=g(x)f(x)\\ (f(x)g(x))\cdot h(x)&=f(x)\cdot(g(x)h(x))\\ (f(x)+g(x))\cdot h(x)&=f(x)h(x)+g(x)h(x) \end{aligned} \end{gathered} $$

生成函数可以被粗略地看做一个有无穷项的多项式, 所以其基本运算法则均与多项式相同.

对于两个有限生成函数 $f(x),g(x)$, 设它们的最高次分别是 $n,m$, 可以证明

$$ f(x)g(x)=\sum_{i=0}^n\sum_{j=0}^mf[i]g[j]x^{ij} $$

即等式左边的生成函数等于右边一堆生成函数的求和.

这是分配律的直接推论.

3.基础序列的生成函数封闭形式举例

1. $1,1,1,1,1,\dots$ 的生成函数是 $\sum_{n = 0}^{\infty} x^n = \frac{1}{1-x} (|x| < 1)$

   证明: $(1-x) \sum_{n = 0}^{\infty} x^n = \sum_{n = 0}^{\infty}(x^n-x^{n+1}) = 1-\lim\limits_{n \to \infty}x^{n+1} = 1$

2. $1,0,1,0,1,0,\dots$ 的生成函数是 $\sum_{n = 0}^{\infty} x^{2n} = \frac{1}{1-x^2}(x^2 < 1) $

   证明: $(1-x^2) \sum_{n = 0}^{\infty} x^{2n} = 1-\lim\limits_{n \to \infty}x^{2n+2} = 1 $

3. $1,2,4,8,16,\dots$ 的生成函数是 $\sum_{n = 0}^{\infty} 2^n x^n = \sum_{n = 0}^{\infty} (2x)^n = \frac{1}{1-2x}(|x| < \frac{1}{2})$

4. $1,a,a^2,a^3,\dots$ 的生成函数是 $\sum_{n = 0}^{\infty} a^n x^n = \sum_{n = 0}^{\infty} (ax)^n = \frac{1}{1-ax}(|ax| < 1)$

5. ${n \choose 0},{n \choose 1},{n \choose 2},{n \choose 3},\dots$ 的生成函数是 $\sum_{i = 0}^{n} {n \choose i}x^i = (1+x)^n$

6. $0,1,-\frac{1}{2},\frac{1}{3},-\frac{1}{4},\dots$ 的生成函数是 $\sum_{n = 0}^{\infty}(-1)^{n}\frac{x^{n+1}}{n+1} = \ln(1+x)$

   证明: 由 $\ln (1+x)$ 的泰勒级数可得.

7. $1,\frac{1}{2},\frac{1}{3},\frac{1}{4},\dots$ 的生成函数是 $-\frac{\ln (1-x)}{x}$

4.从封闭的幂级数形式还原原来的序列

首先知道些公式, 关于组合数的（其中 $m,n \in \N^*$）

$$ \begin{aligned} &\left(x+y\right)^{m} =\sum_{n=0}^m\binom mnx^ny^{m-n} \\ &\binom{m+n}n =\sum_{i=0}^n\binom{m+i-1}i \end{aligned} $$

第一个式子可用高中数学选择性必修三第六章中提到的二项式定理证明.

至于第二个式子的证明, 其实拿杨辉三角一直往上拆直到拆光就行了.

我们定义牛顿二项式系数如下:

$$ {r\choose n}= \begin{cases} 0 &(n<0)\\ 1 &(n=0)\\ \frac{r(r-1)\cdots(r-n+1)}{n!} &(n>0) \end{cases} $$

虽然这和组合数定义很像, 但其中 $n \in \Z,r \in \R$, 所以其没有组合意义. 后面出现的类似式子在没有强调时都代表牛顿二项式系数.

类似的我们可以有牛顿二项式定理:

$$ \left(x+y\right)^{m} =\sum_{n=0}^{\infty} \binom mnx^ny^{m-n} $$

其中 $m \in \R$. 证明方式: 将左式泰勒展开.

同时给出如下常用结论:

1. $\large {-m \choose n} = (-1)^n {m+n-1 \choose n}$, 其中 $m$ 为正整数, $n$ 为整数

2. 令 $m$ 为正整数, 则有

   $$ \begin{aligned} &(1+x)^m =\sum_{n=0}^\infty(-1)^n\binom{m+n-1}nx^n \\ &(1-x)^m =\sum_{n=0}^\infty\binom{m+n-1}nx^n \end{aligned} $$

3. 令 $m = \frac{1}{2}$, 则有

   $$ (1+x)^{\frac12}=1+\sum_{n=1}^{\infty}\frac{(-1)^{n-1}}{2^{2n-1}n}\binom{2n-2}{n-1}x^n $$

我们从斐波那契数列的生成函数推导通项公式为例讲解.

斐波那契通项公式

给定斐波那契数列递推式

$$ \left.\left\{\begin{aligned}&f_0=f_1=1\\&f_n=f_{n-1}+f_{n-2}\quad(n\geq2)\end{aligned}\right.\right. $$

求其第 $n$ 项的通项公式.

设斐波那契数列 $\{f_n\}$ 的普通生成函数为 $G(x) = \sum_n^\infty f_nx^n$ .

则有:

$$ \begin{aligned} G(x)& =1+x+\sum_{n=2}^\infty(f_{n-1}+f_{n-2})x^n \\ &=1+x+x\sum_{n=2}^\infty f_{n-1}x^{n-1}+x^2\sum_{n=2}^\infty f_{n-2}x^{n-2} \\ &=1+x+x\sum_{n=1}^\infty f_nx^n+x^2\sum_{n=0}^\infty f_nx^n \\ &=1+x+x(G(x)-1)+x^2G(x) \\ &=1+(x^2+x)G(x) \end{aligned} $$

解得:

$$ G(x)=-\frac{1}{x^2+x-1} $$

我们的目的是将其拆成

$$ C_1(x_1+y_1)^{\alpha_1}+C_2(x_2+y_2)^{\alpha_2}+C_3(x_3+y_3)^{\alpha_3}+\cdots $$

才能使用二项式定理, 因此我们对 $x^2+x-1$ 因式分解: $x^2+x-1 = (x-\frac{-1+\sqrt{5}}{2})(x-\frac{-1-\sqrt{5}}{2})$

因此

$$ G(x)=\frac{1}{\sqrt{5}}(\frac{-1}{x-\frac{-1+\sqrt{5}}{2}}+\frac{1}{x-\frac{-1-\sqrt{5}}{2}}) $$

对 $\large -(x-\frac{-1+\sqrt{5}}{2})^{-1}$ 和 $\large (x-\frac{-1-\sqrt{5}}{2})^{-1}$ 分别代入牛顿二项式定理（常数用 $p$ 代替）可得

$$ (x-p)^{-1}=\sum_{n=0}^{\infty} \binom {-1} {n} x^n (-p)^{-1-n}=-\sum_{n=0}^{\infty} \frac{x^n}{p^{n+1}} $$

因而

$$ G(x)=\sum_{n=0}^{\infty}\frac{1}{\sqrt{5}}\left((\frac{-1+\sqrt{5}}{2})^{-n-1}-(\frac{-1-\sqrt{5}}{2})^{-n-1} \right)x^n $$

因此斐波那契数列通项公式则为:

$$ \begin{align} f_n&=\frac{1}{\sqrt{5}}\left((\frac{-1+\sqrt{5}}{2})^{-n-1}-(\frac{-1-\sqrt{5}}{2})^{-n-1} \right)\\ &=\frac{1}{\sqrt{5}}\left((\frac{1+\sqrt{5}}{2})^{n+1}-(\frac{1-\sqrt{5}}{2})^{n+1} \right) \end{align} $$

卡特兰数通项公式

给定卡特兰数数列递推式 (下标从 1 开始)

$$ \left.\left\{\begin{aligned}h_1&=1\\h_n&=\sum_{k=1}^{n-1}h_kh_{n-k}&(n\geq2)\end{aligned}\right.\right. $$

求其第 $n$ 项的通项公式.

设 $\{h_n\}$ 的生成函数为 $H(x) = \sum\limits_{i = 1}^\infty h_nx^n$.

将其两边平方得

$$ \begin{aligned} H^{2}(x)& =\left(\sum_{i=1}^\infty h_ix_i\right)\left(\sum_{j=1}^\infty h_jx_j\right) \\ &=\sum_{n=2}^\infty x^n\sum_{k=1}^{n-1}h_kh_{n-k} \\ &=\sum_{n=2}^\infty h_nx^n \\ &=H(x)-x \end{aligned} $$

解上式中推出的关于 $H(x)$ 的方程得

$$ \begin{aligned}H_1(x)&=\frac{1+(1-4x)^{\frac12}}2\\H_2(x)&=\frac{1-(1-4x)^{\frac12}}2\end{aligned} $$

由于 $H(0) = 0$, 所以 $H_1(x)$ 舍去, 取 $H(x) = H_2(x)$.

根据常用结论 3 $$ (1+x)^{\frac12}=1+\sum_{n=1}^{\infty}\frac{(-1)^{n-1}}{2^{2n-1}n}\binom{2n-2}{n-1}x^n $$

可知

$$ (1-4x)^{\frac12}=1+\sum_{n=1}^{\infty}\frac{(-1)^{n-1}}{2^{2n-1}n}\binom{2n-2}{n-1}(-4x)^n=1-\sum_{n=1}^{\infty}\frac2n\binom{2n-2}{n-1}x^n $$

将上式带入 $H_2(x)$

$$ H(x)=H_2(x)=\sum_{n=1}^\infty\frac1n\binom{2n-2}{n-1}x^n $$

故

$$ h_n=\frac1n\binom{2n-2}{n-1} $$

所以, 下标从 $0$ 开始的卡特兰数通项公式即为

$$ h_n=\frac{1}{n+1} {2n \choose n} $$

总结: 使用生成函数求解给定递推式序列的通项式的一般方法:

1. 设出 $\{a_n\}$ 的生成函数 $G(x)$ .
2. 利用递推方程的依赖关系, 导出关于生成函数 $G(x)$ 的方程.
3. 求解方程, 得到关于 $G(x)$ 的函数表达式.
4. 将 $G(x)$ 展开成属级数的形式, $x^n$ 项的系数即为 $a_n$ .

5.题目探究

求数列通项公式

1. （高考数学压轴题P4例1(2)）设 $b > 0$, 数列 $\{a_n \}$ 满足 $a_1 = b,a_n = \frac{nba_{n-1}}{a_{n-1}+n-1}( n \ge 2)$, 求数列 $\{a_n \}$ 的通项公式.

   解: 对 $a_n = \frac{nba_{n-1}}{a_{n-1}+n-1}$ 进行变换可得

   $$ a_n(a_{n-1}+n-1) =nba_{n-1}\\ b\frac{n}{a_n}=1+\frac{n-1}{a_{n-1}} $$

   设 $\Large F(x) = \sum\limits_{n = 1}^{\infty} \frac{n}{a_n} x^n$, 则

   $$ \begin{align} F(x)&=\sum\limits_{n=1}^{\infty} \frac{n}{a_n} x^n\\ &=\frac{x}{b} + \frac{1}{b} \sum\limits_{n=2}^{\infty} (1+\frac{n-1}{a_{n-1}}) x^n\\ &=\frac{x}{b} + \frac{x}{b} \sum\limits_{n=1}^{\infty} (1+\frac{n}{a_{n}}) x^n\\ &=\frac{x}{b}+\frac{x^2}{b(1-x)}+\frac{x}{b} F(x) \end{align} $$

   $$ \begin{align} (\frac{b}{x} -1)F(x)&=\frac{1}{1-x}\\ F(x)&=\frac{x}{(1-x)(b-x)}\\ &=\frac{\frac{1}{1-b}}{1-x}-\frac{\frac{b}{1-b}}{b-x} \end{align} $$

   当 $b = 1$ 时, 可得 $F(x) = \frac{x}{(1-x)^2}$. 因此

   $$ \begin{align} F(x)&=x\cdot (x-1)^{-2}\\ &=x\cdot\sum_{n=0}^{\infty} {-2 \choose n} x^n (-1)^{-2-n}\\ &=x\cdot \sum_{n=0}^{\infty} (-1)^n (n+1)x^n(-1)^{-2-n}\\ &=\sum_{n=1}^{\infty}n x^n\\ \end{align} $$

   也即 $\frac{n}{a_n} = n \implies a_n = 1$.

   当 $b \neq 1$ 时, 可得

   $$ \begin{align} F(x)&=\frac{1}{1-b}\sum_{n=0}^{\infty} x^n-\frac{b}{1-b}\sum_{n=0}^{\infty}\frac{x^n}{b^{n+1}}\\ &=\sum_{n=0}^{\infty} \left(\frac{1}{1-b}-\frac{1}{(1-b)b^n} \right)x^n\\ &=\sum_{n=1}^{\infty} \left(\frac{b^n-1}{(1-b)b^n} \right)x^n \end{align} $$

   因此

   $$ \frac{n}{a_n}=\frac{b^n-1}{(1-b)b^n}\\ a_n=\frac{nb^n(1-b)}{b^n-1} $$

2. （高考数学压轴题P5例2(1)）数列 $\{a_n \}$ 满足 $a_1 = 1,a_2 = 11,a_{n+2} = 2a_{n+1}+3a_n+4 (n \in \N^*)$, 求数列 $\{a_n \}$ 的通项公式.

   解: 设 $\Large F(x) = \sum\limits_{n = 1}^{\infty} a_n x^n$, 则

   $$ \begin{align} F(x)&=\sum\limits_{n=1}^{\infty} a_n x^n\\ &=x+11x^2+ \sum\limits_{n=3}^{\infty} (2a_{n-1}+3a_{n-2}+4) x^n\\ &=x+11x^2+2x\sum_{n=2}^{\infty}a_nx^n+3x^2\sum_{n=1}^{\infty}a_nx^n+4x^3\sum_{n=0}^{\infty}x^n\\ &=x+11x^2+2x(F(x)-x)+3x^2F(x)+\frac{4x^3}{1-x}\\ &=x+9x^2+(3x^2+2x)F(x)+\frac{4x^3}{1-x} \end{align} $$

   因此 $$ (3x^2+2x-1)F(x)=\frac{x}{1-x}(5x^2-8x-1) $$

   设 $t_1,t_2,t_3 \in \R$, 则

   $$ \left\{ \begin{align} F(x)=x\left(\frac{t_1}{1-x}+\frac{t_2}{3x-1}+\frac{t_3}{x+1} \right)\\ t_1(3x-1)(x+1)+t_2(1-x)(x+1)+t_3(1-x)(3x-1)=5x^2-8x-1 \end{align} \right. $$

   解得

   $$ t_1=-1,t_2=-\frac{7}{2} ,t_3=-\frac{3}{2} $$

   因此

   $$ \begin{align} F(x)&=x\sum_{n=0}^{\infty}\left(-1+ \frac{7}{2}\cdot 3^n-\frac{3}{2}\cdot (-1)^n \right)x^n\\ &=\sum_{n=1}^{\infty}\left(-1+ \frac{7}{6}\cdot 3^n+\frac{3}{2}\cdot (-1)^n \right)x^n \end{align} $$

   从而得 $a_n = -1+ \frac{7}{6}\cdot 3^n+\frac{3}{2}\cdot (-1)^n$.

数列求和

1. 求 $\Large \sum\limits_{n = 0}^{\infty} \frac{1}{n+1}(\frac{1}{2})^n$

   解: 我们发现可以将上式写成 $\Large \sum\limits_{n = 0}^{\infty} \frac{1}{n+1}x^n$, 其中 $x = \frac{1}{2}$.

   因此我们求出 $\{\frac{1}{n+1} \}$ 的生成函数 $-\frac{\ln(1-x)}{x}$, 并将 $x = \frac{1}{2}$ 代入可得答案 $2\ln 2$.

2. 设数列 $\{a_n \}$ 满足 $a_0 = \frac{1}{2} ,a_1 = \frac{3}{4} b$, $a_n = \frac{b \cdot a_{n-1}}{2}(n \ge 2)$, 其中 $b$ 为正实数. 当满足: 对任意正整数 $n$ 都有 $\displaystyle \sum_{k = 0}^{n}a_k < 2^b$ 时, 求 $b$ 的取值范围.

   解: 由题可得 $a_n = \frac{3}{4} b^n \cdot 2^{1-n} (n\ge 1)$.

   因此我们只需求出 $\{\frac{1}{2} ,\frac{3}{4} ,\frac{3}{8},\frac{3}{16},\cdots \}$ 的生成函数, 即

   $$ \displaystyle F(x)=\frac{1}{2} +\frac{3}{2} \sum_{n=1}^{\infty}\frac{1}{2^n}x^n=\frac{1}{2} +\frac{3}{2} (\frac{2}{2-x}-1)=\frac{1+x}{2-x} $$

   将 $x = b$ 代入即得 $F(b) = \frac{1+b}{2-b}$. 由于数列 $\{a_n \}$ 在 $b\ge 2$ 时单调不递减, 因此总存在 $n$ 使得 $b > 2$ 时 $\displaystyle \sum_{k = 0}^{n}a_k > 2^b $.

   当 $0 < b < 2$ 时, $\{a_n\}$ 单调递减, 因此只需解 $\frac{1+b}{2-b} \le 2^b$.

   设 $f(x) = 2^x-\frac{1+x}{2-x}$, 则 $f'(x) = 2^x\ln 2-\frac{3}{(2-x)^2}$.

   要证 $2^x\ln 2 < \frac{3}{(2-x)^2}$, 则需证 $2^x(2-x)^2 < \frac{3}{\ln 2}$.

   对左式求导可得 $2^x\ln 2(2-x)^2-2\cdot 2^x(2-x)$. 当其等于 $0$ 时, $x = 2$ 或 $x = 2-\frac{2}{\ln 2}$.

   当 $x \in (2-\frac{2}{\ln 2},2)$ 时, $2^x\ln 2(2-x)^2-2\cdot 2^x(2-x) < 0$.

   因此 $f'(x) = 2^x\ln 2-\frac{3}{(2-x)^2} < 0 (0 < x < 2)$.

   因此 $f(x)$ 在 $(0,2)$ 单调递减.

   又由 $f(1) = 0$ 可得当 $b \in (0,1]$ 时 $\frac{1+b}{2-b} \le 2^b$.

3. 设数列 $\{a_n\}$ 满足 $a_n = n^2$, 数列 $\{b_n \}$ 满足 $b_n = \frac{1}{2^n}$. 设数列 $\{c_n\}$ 满足 $\displaystyle c_n = \sum_{k = 0}^{n}a_kb_{n-k}$. 求证: 对任意正整数 $n$ 都有 $\displaystyle \sum_{k = 0}^n b_kc_k < 8$.

   解: 我们分别求出 $\{a_n\},\{b_n \}$ 的生成函数为 $F(x) = \frac{x(x+1)}{(1-x)^3},G(x) = \frac{2}{2-x}$.

   则 $\{c_n \}$ 的生成函数 $H(x) = F(x)G(x) = \frac{2x(x+1)}{(1-x)^3(2-x)}$.

   将 $x = \frac{1}{2}$ 代入可得 $\displaystyle \sum_{k = 0}^{\infty} b_kc_k = 8$. 由 $\{b_nc_n\}$ 为递增数列可得 $\displaystyle \sum_{k = 0}^n b_kc_k < 8$.

6. 练习题

1. 给 $n_1$ 个 $1$, $n_2$ 个 $2$, $n_3$ 个 $5$, 问它们不能组成的最小正整数是多少？(建立生成函数, 并指出答案对应的是生成函数中哪一项的指数或系数)

2. 小光得到了 $3$ 罐糖果. 不同的糖果罐, 糖果的种类不同（即同一个糖果罐里的糖果种类是相同的, 不同的糖果罐里的糖果的种类是不同的）. 三个糖果罐里分别有 24 3 25 个糖果. 小光决定吃掉一些糖果, 他想吃掉至少 $5$ 个糖果, 但不超过 $14$ 个.

   小光无法确定吃多少个糖果和每种糖果各吃几个. 有多少种方法可以做这件事呢？(提示：生成函数建立正确后, 本题计算并不复杂)

参考文献

1. Lando, S.K. (2003). Lectures on Generating Functions.
2. Wilf, H.S. (2005). Generating Functionology: Third Edition (3rd ed.). A K Peters/CRC Press. https://doi.org/10.1201/b10576
3. 曹永生 (2023). 高考数学压轴题破解策略
4. 张新华 (2023). 信息学竞赛宝典