Skip to content

离散经典例题

第 4 题：使用生成函数求解递推关系

题目：

使用生成函数求解递推关系 \(a_k = 5a_{k-1} - 6a_{k-2}\)，初始条件为 \(a_0 = 6\) 且 \(a_1 = 30\)。

答案：

该递推关系的通项公式为：\(a_k = 18 \cdot 3^k - 12 \cdot 2^k\)

解析：

  1. 构造生成函数：

    设序列 \(a_k\) 的生成函数为 \(G(x) = \sum_{k=0}^{\infty} a_k x^k = a_0 + a_1 x + a_2 x^2 + \dots\)

    将递推关系改写为标准形式：\(a_k - 5a_{k-1} + 6a_{k-2} = 0\) （对于 \(k \ge 2\)）。

  2. 将递推关系代入生成函数方程：

    将等式两边同乘 $x^k$ 并从 $k=2$ 到无穷大求和：

$$

    \sum_{k=2}^{\infty} a_k x^k - 5 \sum_{k=2}^{\infty} a_{k-1} x^k + 6 \sum_{k=2}^{\infty} a_{k-2} x^k = 0 $$

    将求和式用 $G(x)$ 表示：

- $\sum_{k=2}^{\infty} a_k x^k = G(x) - a_0 - a_1 x$

- $\sum_{k=2}^{\infty} a_{k-1} x^k = x \sum_{k=2}^{\infty} a_{k-1} x^{k-1} = x(G(x) - a_0)$

- $\sum_{k=2}^{\infty} a_{k-2} x^k = x^2 \sum_{k=2}^{\infty} a_{k-2} x^{k-2} = x^2 G(x)$

代入上述方程并代入初始条件 $a_0 = 6, a_1 = 30$：

$$

    (G(x) - 6 - 30x) - 5x(G(x) - 6) + 6x^2 G(x) = 0 $$

  3. 化简并求解 \(G(x)\)：

    展开后提取 $G(x)$：

$$

    G(x) - 6 - 30x - 5x G(x) + 30x + 6x^2 G(x) = 0 $$

    $$

    G(x)(1 - 5x + 6x^2) - 6 = 0 $$

    $$

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

  4. 进行部分分式分解 (Partial Fraction Decomposition)：

    首先分解分母：$1 - 5x + 6x^2 = (1 - 2x)(1 - 3x)$。

设 $\frac{6}{(1 - 2x)(1 - 3x)} = \frac{A}{1 - 2x} + \frac{B}{1 - 3x}$。

通分得：$A(1 - 3x) + B(1 - 2x) = 6$。

- 令 $x = 1/2$，得到 $A(1 - 3/2) = 6 \implies -A/2 = 6 \implies A = -12$。

- 令 $x = 1/3$，得到 $B(1 - 2/3) = 6 \implies B/3 = 6 \implies B = 18$。

    因此，生成函数为：

    $$

    G(x) = \frac{-12}{1 - 2x} + \frac{18}{1 - 3x} $$

  5. 展开为幂级数求通项：

    利用几何级数公式 \(\frac{1}{1 - rx} = \sum_{k=0}^{\infty} r^k x^k\) 展开：

    \[ G(x) = -12 \sum_{k=0}^{\infty} 2^k x^k + 18 \sum_{k=0}^{\infty} 3^k x^k = \sum_{k=0}^{\infty} (18 \cdot 3^k - 12 \cdot 2^k) x^k \]

    提取 \(x^k\) 的系数，得到通项公式：

    \[ a_k = 18 \cdot 3^k - 12 \cdot 2^k \]

第 3 题：递推关系 (Recurrence Relation)

题目要求： 已知递推关系形式为 \(a_n = c_1 a_{n-1} + c_2 a_{n-2} + c_3\)，以及初始值 \(a_0 = 0, a_1 = 1, a_2 = 4, a_3 = 11, a_4 = 26\)。求该递推关系的通项公式。

解析：

第一步：解出常数 \(c_1, c_2, c_3\)

将已知的 \(n=2, 3, 4\) 代入递推公式，建立方程组：

  1. \(a_2 = c_1 a_1 + c_2 a_0 + c_3 \implies 4 = c_1(1) + c_2(0) + c_3 \implies \mathbf{c_1 + c_3 = 4}\)

  2. \(a_3 = c_1 a_2 + c_2 a_1 + c_3 \implies 11 = c_1(4) + c_2(1) + c_3 \implies \mathbf{4c_1 + c_2 + c_3 = 11}\)

  3. \(a_4 = c_1 a_3 + c_2 a_2 + c_3 \implies 26 = c_1(11) + c_2(4) + c_3 \implies \mathbf{11c_1 + 4c_2 + c_3 = 26}\)

由 (1) 得 \(c_3 = 4 - c_1\)，代入 (2) 得到：

\(4c_1 + c_2 + (4 - c_1) = 11 \implies 3c_1 + c_2 = 7 \implies c_2 = 7 - 3c_1\)

将 \(c_3\) 和 \(c_2\) 的表达式都代入 (3)：

\(11c_1 + 4(7 - 3c_1) + (4 - c_1) = 26\)

\(11c_1 + 28 - 12c_1 + 4 - c_1 = 26\)

\(-2c_1 + 32 = 26 \implies 2c_1 = 6 \implies \mathbf{c_1 = 3}\)

回代得到：

\(c_2 = 7 - 3(3) = \mathbf{-2}\)

\(c_3 = 4 - 3 = \mathbf{1}\)

所以原递推公式为：\(a_n = 3a_{n-1} - 2a_{n-2} + 1\)

第二步：求解二阶非齐次线性递推关系

递推式变形为：\(a_n - 3a_{n-1} + 2a_{n-2} = 1\)

  1. 求齐次部分的通解：

    特征方程为 \(r^2 - 3r + 2 = 0\)，解得 \(r_1 = 1, r_2 = 2\)。

    所以齐次通解为 \(a_n^{(h)} = A \cdot 1^n + B \cdot 2^n = A + B \cdot 2^n\)。

  2. 求非齐次部分的特解：

    等式右侧 \(f(n) = 1\) 是常数（即 \(1^n\)）。由于 \(r=1\) 是特征方程的一个单根，我们猜测特解形式为 \(a_n^{(p)} = C \cdot n \cdot 1^n = Cn\)。

    代入原递推式：

    \(Cn - 3C(n-1) + 2C(n-2) = 1\)

    \(Cn - 3Cn + 3C + 2Cn - 4C = 1\)

    \(-C = 1 \implies C = -1\)

    所以特解为 \(a_n^{(p)} = -n\)。

  3. 求通项公式：

    总解为 \(a_n = a_n^{(h)} + a_n^{(p)} = A + B \cdot 2^n - n\)。

    利用初始条件 \(a_0 = 0, a_1 = 1\) 求解常数 \(A, B\)：

    \(a_0 = 0 \implies A + B - 0 = 0 \implies A = -B\)

    \(a_1 = 1 \implies A + 2B - 1 = 1 \implies A + 2B = 2\)

    将 \(A = -B\) 代入得：\(-B + 2B = 2 \implies \mathbf{B = 2}\)，进而 \(\mathbf{A = -2}\)。

将 \(A, B\) 代回总解公式得到最终结果。

答案：

该递推关系的通项解为：

\[ a_n = 2^{n+1} - n - 2 \]

任何凸多面体的棱边结构都可以平展在二维平面上而不发生边相交（这种投影图在图论中被称为施莱格尔图 / Schlegel diagram）。

画法解析：

  • 四面体 (Tetrahedron)： 画一个大的三角形，在三角形内部中心画一个点，然后将这个中心点与外围三角形的三个顶点相连。

  • 立方体 (Cube)： 画一个大正方形，在它内部再画一个稍小的正方形。然后将内、外两个正方形对应的四个角两两相连（看起来像一个透视的正方框）。

  • 八面体 (Octahedron)： 画一个大的三角形，在其内部画一个倒置的小三角形。将内部小三角形的三个顶点与外部大三角形对应的边或顶点相连，使得图中所有面都是三角形且没有边交叉。

(c) 利用欧拉定理证明只有 5 种凸正多面体，并列出它们

解析：

设该正多面体每个面有 \(n\) 条边（\(n \ge 3\)），每个顶点相交有 \(m\) 条边（\(m \ge 3\)）。

设顶点数为 \(V\)，边数为 \(E\)，面数为 \(F\)。

  1. 建立方程：

    • 每条边由 2 个面共享，所以 \(nF = 2E \implies F = \frac{2E}{n}\)。

    • 每条边连接 2 个顶点，所以 \(mV = 2E \implies V = \frac{2E}{m}\)。

  2. 代入欧拉公式 (Euler's Formula)：

    平面或凸多面体的欧拉公式为：$V - E + F = 2$。

代入上面的式子得：

$$

    \frac{2E}{m} - E + \frac{2E}{n} = 2 $$

    两边同除以 $2E$，得到：

$$

    \frac{1}{m} + \frac{1}{n} - \frac{1}{2} = \frac{1}{E} $$

  3. 分析不等式：

    因为边数 $E$ 必定是正数，所以 $\frac{1}{E} > 0$，即：

$$

    \frac{1}{m} + \frac{1}{n} > \frac{1}{2} $$

    已知 $m \ge 3$ 且 $n \ge 3$。如果 $m$ 和 $n$ 都大于等于 4，那么 $\frac{1}{m} + \frac{1}{n} \le \frac{1}{4} + \frac{1}{4} = \frac{1}{2}$，不等式无法成立。因此，**$m$ 和 $n$ 中至少有一个必须等于 3**。

  4. 分类讨论所有可能的整数解：

    • 情况 1：\(n = 3\)（每个面是三角形）

      代入不等式得 \(\frac{1}{m} > \frac{1}{6}\)，所以 \(m\) 只能是 3, 4, 5。

      • 当 \(m=3, n=3\) 时，解得 \(E=6\)，\(V=4, F=4\)。（正四面体）

      • 当 \(m=4, n=3\) 时，解得 \(E=12\)，\(V=6, F=8\)。（正八面体）

      • 当 \(m=5, n=3\) 时，解得 \(E=30\)，\(V=12, F=20\)。（正二十面体）

    • 情况 2：\(n = 4\)（每个面是正方形）

      代入不等式得 \(\frac{1}{m} > \frac{1}{4}\)，所以 \(m\) 只能是 3（因为 \(m \ge 3\)）。

      • 当 \(m=3, n=4\) 时，解得 \(E=12\)，\(V=8, F=6\)。（正六面体/立方体）

    • 情况 3：\(n = 5\)（每个面是正五边形）

      代入不等式得 \(\frac{1}{m} > \frac{3}{10}\)，所以 \(m\) 只能是 3。

      • 当 \(m=3, n=5\) 时，解得 \(E=30\)，\(V=20, F=12\)。（正十二面体）

    • 情况 4：\(n \ge 6\)

      \(\frac{1}{m} > \frac{1}{3}\)，即 \(m < 3\)，这违背了多面体每个顶点至少相交 3 条边的几何常识，故不存在。

总结列表：

种类 面数 (F) 顶点数 (V) 边数 (E)
正四面体 (Tetrahedron) 4 4 6
立方体/正六面体 (Cube) 6 8 12
正八面体 (Octahedron) 8 6 12
正十二面体 (Dodecahedron) 12 20 30
正二十面体 (Icosahedron) 20 12 30