复分析小品-生成函数

关于生成函数, 以下直接引用 wiki 百科上的介绍:

In mathematics, a generating function is a way of encoding an infinite sequence of numbers ($a_n$) by treating them as the coefficients of a formal power series. This series is called the generating function of the sequence.

Unlike an ordinary series, the formal power series is not required to converge: in fact, the generating function is not actually regarded as a function, and the “variable” remains an indeterminate. Generating functions were first introduced by Abraham de Moivre in 1730, in order to solve the general linear recurrence problem. One can generalize to formal power series in more than one indeterminate, to encode information about infinite multi-dimensional arrays of numbers.

正如这段介绍中所说, 生成函数就是描述数列的另一种不同的方法而已, 这种方法将整个序列视作了一个对象进行考虑, 更具体的说, 就是个幂级数, 其系数有着某些特定含义.

作为一篇小品, 本文只简单介绍一下生成函数定义, 并利用该方法研究斐波那契数列.

生成函数的定义,几个简单的例子

[Defintion] 对于一个序列 ${a_n}$, 以下幂级数
$$\sum_{n=0}^{\infty}a_n z^n$$
称为该序列的一般生成函数; 而以下幂级数
$$\sum_{n=0}^{\infty}\frac{a_n z^n}{n!}$$
称为该序列的指数生成函数.

下面给几个简单的例子, 直观的感受一下.

【例1】 ${a_n}$ 为常数序列, 那么其一般生成函数为 $\sum a_n z^n = \frac{Const}{1-z}$; 而其指数生成函数为 $\sum\frac{a_n z^n}{n!} = Ce^z$.

【例2】求数列 ${n^3}$ 的一般生成函数. 首先, 我们有
$$n^3 = (n+3)(n+2)(n+1) - 6(n+2)(n+1) + 7(n+1) - 1,$$
于是, 对于 $|z|<1$, 级数是一致收敛的, 有下式:

$$
\sum_{n=0}^{\infty}n^3 z^n = \sum_{n=0}^{\infty} (n+3)(n+2)(n+1)z^n \\
-\sum_{n=0}^{\infty} 6(n+2)(n+1)z^n \\ + \sum_{n=0}^{\infty} 7(n+1)z^n - \sum_{n=0}^{\infty}z^n \\
= \frac{6}{(1-z)^4} - \frac{12}{(1-z)^3} + \frac{7}{(1-z)^2} - \frac{1}{1-z}.$$

Fibonacci 数列的

Fibonacci 数列的生成函数

我们都知道 Fibonacci 数列是通过以下二阶递归式来定义的: 设 $F_{0} = F_{1} = 1$, 对于 $n > 1$ 的通项满足
$$F_{n+2} = F_{n+1} + F_{n}.$$

考虑斐波那契数列的一般生成函数:
$$\sum_{n=0}^{\infty}F_n z^n.$$

用 $f(z)$ 表示该级数的和, 有
$$f(z)-1 = \sum_{n=0}^{\infty}F_{n+1} z^{n+1},\\
f(z)-1-z = \sum_{n=0}^{\infty}F_{n+2} z^{n+2},$$

根据递归公式, 有
$$\sum_{n=0}^{\infty}(F_n + F_{n+1}) z^{n+2} = \sum_{n=0}^{\infty}F_{n+2} z^{n+2},$$

由以上三式可以得到
$$z^2f(z)+z(f(z)-1) = f(z) - 1 - z.$$

上式整理后便得到, 若以上级数收敛, 其和为
$$f(z) = \frac{1}{1-z-z^2}.$$

以上级数在 $f(z)$ 解析时收敛的. 也就是要求 $\frac{1}{1-z-z^2}$ 解析, 显然, $1-z-z^2$ 有两个零点, 为 $\frac{-1\pm\sqrt{5}}{2}$, 级数在以 $0$ 为圆心的最大的收敛圆内是解析的. 故而, 在 $|z|<\frac{-1+\sqrt{5}}{2}$ 时, $f$ 收敛.

黄金比例

根据前面求出的生成函数, 我们知道级数在$|z|<\frac{-1+\sqrt{5}}{2}$ 时收敛, 而根据级数的比值判别法, 相邻两项做比取极限, 如果极限存在, 则其倒数就是收敛半径, 即:
$$\lim_{n\rightarrow \infty}\frac{F_{n+1}}{F_{n}} = \frac{1+\sqrt{5}}{2}.$$

这个数的近似值是 $1.61803398874989…$, 这就是我们常说的 黄金比例.