Generating Functions

hbghlyj

PDF
Example 5. Note that $\frac{1}{89}=0.011235955056 \ldots .$ Prove that
$$
\frac{1}{89}=\sum_{n=1}^{\infty} \frac{F_{n}}{10^{n+1}}
$$
where $F_{n}$ is the $n$th term of the Fibonacci sequence defined by $F_{0}=0, F_{1}=1$, and $F_{n+2}=F_{n}+F_{n+1}$ for $n \geq 2$.

Proof. Let $G(x)=\sum_{n=0}^{\infty} F_{n} x^{n}$ be the generating function for $F_{n}$. Similar to the solution to Example 4, we can get
$$
G(x)=\frac{x}{1-x-x^{2}}=F_{0}+F_{1} x+F_{2} x^{2}+F_{3} x^{3}+\cdots\tag{$*$}
$$
Plugging $x=\frac{1}{10}$ into $(*)$, we get
$$
\frac{10}{89}=\frac{F_{1}}{10}+\frac{F_{2}}{100}+\frac{F_{3}}{1000}+\cdots
$$
and the result follows.

$\square$

5  Snake Oil Method
When each term $a_{n}$ of a sequence $A=\left\{a_{0}, a_{1}, a_{2}, \ldots\right\}$ is itself a sum, generating function $G(x)=\sum_{n=0}^{\infty} a_{n} x^{n}$ is especially helpful. Then we have a double sum to work with and swapping the order of summation usually helps. Herbert Wilf [3] coined the name Snake Oil Method, a cure for everything. In his own words, "don't try to evaluate the sum that you're looking at. Instead, find the generating function for the whole parameterized family of them, then read off the coefficients." Let's look at an example.
Example 6. For $n \geq 0$, compute
$$
\sum_{k \geq 0}\left(\begin{array}{c}
k \\
n-k
\end{array}\right)
$$
Solution. Here the free variable is $n$. So we define a generating function
$$
G(x)=\sum_{n}\left(\sum_{k \geq 0}\left(\begin{array}{c}
k \\
n-k
\end{array}\right)\right) x^{n}
$$
Next we interchange the sums, and get
$$
G(x)=\sum_{k \geq 0} \sum_{n}\left(\begin{array}{c}
k \\
n-k
\end{array}\right) x^{n}=\sum_{k \geq 0} x^{k} \sum_{n}\left(\begin{array}{c}
k \\
n-k
\end{array}\right) x^{n-k}
$$
Let $r=n-k$, we get
$$
\begin{aligned}
G(x) &=\sum_{k \geq 0} x^{k} \sum_{r}\left(\begin{array}{l}
k \\
r
\end{array}\right) x^{r}=\sum_{k \geq 0} x^{k}(1+x)^{k} \\
&=\sum_{k \geq 0}\left(x+x^{2}\right)^{k}=\frac{1}{1-x-x^{2}}
\end{aligned}
$$
From Example 5, we know that $\frac{x}{1-x-x^{2}}$ is the generating function for the Fibonacci sequence. Thus
$$
\sum_{k \geq 0}\left(\begin{array}{c}
k \\
n-k
\end{array}\right)=F_{n+1} \quad(n=0,1,2, \ldots)
$$
6 Exercises

• Let $a_{0}=1, a_{1}=1$, and $a_{n}=4 a_{n-1}-4 a_{n}$ for $n \geq 2$. Use generating functions to find a formula for $a_{n}$ in terms of $n$.
• Find the number $a_{n}$ of ways $n$ dollars can be changed into 1-dollar or 2-dollar coins regardless of the order. For example, when $n=3$, there are 2 ways, namely three 1-dollar coins or one 1-dollar coin and one 2-dollar coin.
• Let $n$ be a positive integer. Find the number $a_{n}$ of polynomials $P(x)$ with coefficients in $\{0,1,2,3\}$ such that $P(2)=n$.
• Let $a_{0}, a_{1}, a_{2}, \ldots$ be an increasing sequence of nonnegative integers such that every nonnegative integer can be expressed uniquely in the form $a_{i}+2 a_{j}+4 a_{k}$, where $i, j$ and $k$ are not necessarily distinct. Determine $a_{1998}$.
• Assume that for some positive integer $n$ there are sequences of positive numbers $a_{1}, a_{2}, \ldots, a_{n}$ and $b_{1}, b_{2}, \ldots, b_{n}$ such that the sums
  $$
  \begin{aligned}
  &a_{1}+a_{2}, a_{1}+a_{3}, \ldots, a_{n-1}+a_{n} \quad \text { and } \\
  &b_{1}+b_{2}, b_{1}+b_{3}, \ldots, b_{n-1}+b_{n}
  \end{aligned}
  $$
  are same up to permutation. Prove that $n$ is a power of two.
• For $n \geq 0$, compute
  $$
  \sum_{k \geq 0}\left(\begin{array}{c}
  n+k \\
  2 k
  \end{array}\right) 2^{n-k}
  $$
• Prove that, for $m, n \geq 0$,
  $$
  \sum_{k \geq 0}\left(\begin{array}{c}
  m \\
  k
  \end{array}\right)\left(\begin{array}{c}
  n+k \\
  m
  \end{array}\right)=\sum_{k \geq 0}\left(\begin{array}{c}
  m \\
  k
  \end{array}\right)\left(\begin{array}{l}
  n \\
  k
  \end{array}\right) 2^{k}
  $$
  without evaluating either of the two sums.
  

References
[1] Evan Chen, Summation, web.evanchen.cc/handouts/Summation/Summation.pdf
[2] Albert Meyer and Ronitt Rubinfeld, Generating Functions, MIT6.042J/18.062J
[3] Herbert Wilf, generatingfunctionology, math.upenn.edu/~wilf/gfologyLinked2.pdf

hbghlyj

zhuanlan.zhihu.com/p/25195967 备份

今天我与大家分享一种用发生函数来证明组合恒等式的「万金油方法」，特别是对于复杂的组合数求值和恒等式非常有效。这种方法在 Herbert S. Wilf 编著的 Generatingfunctionology 中有详细研究，感兴趣的读者可以参考。习惯阅读中文的读者也可以参考中文译本《发生函数论》。在本文中我们将用

$$\left( \begin{array} { c } { n } \\ { m } \end{array} \right) : = \frac { n ( n - 1 ) \cdots ( n - m + 1 ) } { m ! }$$

来表示组合数。至于为什么用这个记号而不用高中竞赛书中更常见的$\textrm{C}^m_n$，我只能说因为我习惯了 ? 让我们先看一个例子。

例 1 求值

$$\sum _ { k = m } ^ { n } ( - 1 ) ^ { k } \left( \begin{array} { l } { n } \\ { k } \end{array} \right) \left( \begin{array} { l } { k } \\ { m } \end{array} \right)$$这个题难度并不大，如果你擅长利用组合模型计数，或者对于二项式展开有深入的研究，相信已经有了初步的解题思路。但是在这里我打算换个角度来看这个问题。首先这不是求一个值，而是一串值，有无穷个——对于每一个$m$，都有一个等式，我希望把这无穷个值放在一起求。那么我们需要一个工具把他们串起来。一个有无穷项的「多项式」似乎是一个理想的对象。我们将其称之为关于$m$的数列的发生函数。于是我们试图计算$$\sum _ { m = 0 } ^ { \infty } \sum _ { k = m } ^ { n } ( - 1 ) ^ { k } \left( \begin{array} { l } { n } \\ { k } \end{array} \right) \left( \begin{array} { l } { k } \\ { m } \end{array} \right) x ^ { m }$$

在这里我们人为地加大了问题的复杂度，但这却给了我们交换和号的自由。注意到二项式定理，接下来的计算都是水到渠成的。

$$\begin{array} { l }{ \sum _ { m = 0 } ^ { \infty } \sum _ { k = m } ^ { n } ( - 1 ) ^ { k } \left( \begin{array} { l } { n } \\ { k } \end{array} \right) \left( \begin{array} { l } { k } \\ { m } \end{array} \right) x ^ { m } }\\{ = \sum _ { k = 0 } ^ { \infty } \sum _ { m = 0 } ^ { k } ( - 1 ) ^ { k } \left( \begin{array} { l } { n } \\ { k } \end{array} \right) \left( \begin{array} { l } { k } \\ { m } \end{array} \right) x ^ { m } }\\{ = \sum _ { k = 0 } ^ { \infty } ( - 1 ) ^ { k } \left( \begin{array} { l } { n } \\ { k } \end{array} \right) \sum _ { m = 0 } ^ { k } \left( \begin{array} { l } { k } \\ { m } \end{array} \right) x ^ { m } }\\{ = \sum _ { k = 0 } ^ { \infty } ( - 1 ) ^ { k } \left( \begin{array} { l } { n } \\ { k } \end{array} \right) ( 1 + x ) ^ { k } }\\{ = ( - x ) ^ { n } = ( - 1 ) ^ { n } x ^ { n } . } \end{array} $$
注意到原来需要求的是$x^m$项的系数，于是如果$m=n$，则答案是$(-1)^n$，否则答案是 0。

我们使用的方法就称为「万金油方法」。让我们来回顾一下在这个解答的过程中我们干了些什么，以及我们还需要些什么。

1. 我们把要求的式子当做一个系数建立了发生函数，这一步不需要任何技术。
2. 我们通过代数计算，得到了一个没有求和号的形式（我们称之为闭形式），这一步计算我们使用了二项式定理。
3. 我们从闭形式中读出了相应项的系数，这一步也是相对容易的。
   

值得一提的是，在万金油方法里，发生函数的闭形式是「算出来」的，而不是「猜出来」的。这也是我们用「发生」函数这个词的原因。这使得我们的解题过程更有目标性，而不是根据经验凭空召唤出一个式子，通过不同的展开方式来创造算两次的机会，从而得到答案。我们的发生函数就好比一跟晾衣绳，我们可以轻松地挂上和取下衣服（系数）。我们注意到在步骤 2 的核心技巧是使用了二项式定理，这对于解决更一般的问题是远远不够的。为了用万金油方法来解决更多的问题，我们需要更多的基本公式来转化求和形式至闭形式。

在介绍基本公式公式之前我再啰嗦几句。使用万金油方法的时候我们会经常用到交换和号，需要注意几个变量的大小关系以及一些边界情况。当求和号是对所有整数求和（太大和太小的时候组合数自然就是零了）的时候，我们就不专门指出求和范围了，只写出求和变量。另外，我们这里的发生函数都属于「形式幂级数」。它的加法，乘法和复合和多项式的计算方式一样，只不过我们要按升幂排列来进行计算。如果常数项非零的话我们可以用待定系数法来求逆。如果你熟悉数学分析里的收敛性，在收敛域内的$x$的值是可以代入求值的。

常用公式

对于任意实数$\alpha$定义广义二项式系数：

$$\left( \begin{array} { l } { \alpha } \\ { k } \end{array} \right) : = \frac { \alpha ( \alpha - 1 ) \cdots ( \alpha - k + 1 ) } { k ! }$$我们有广义二项式定理：$$( 1 + x ) ^ { \alpha } = \sum _ { k = 0 } ^ { \infty } \left( \begin{array} { l } { \alpha } \\ { k } \end{array} \right) x ^ { k }$$不难看出当$\alpha$为正整数的时候，系数${\alpha\choose k}=0$对$k>\alpha$成立。从而广义二项式定理和通常的二项式定理吻合。特别地，当$\alpha=-(n+1),\frac{1}{2},-\frac{1}{2}$的时候，稍加代数变形，我们有辅助公式$$\begin{array} { l }{ \frac { 1 } { ( 1 - x ) ^ { n + 1 } } = \sum _ { k \geq 0 } \left( \begin{array} { c } { n + k } \\ { n } \end{array} \right) x ^ { k } }\\{ \frac { 1 } { \sqrt { 1 - 4 x } } = \sum _ { k \geq 0 } \left( \begin{array} { c } { 2 k } \\ { k } \end{array} \right) x ^ { k } }\\{ \frac { 1 - \sqrt { 1 - 4 x } } { 2 x } = \sum _ { k \geq 0 } \frac { 1 } { k + 1 } \left( \begin{array} { c } { 2 k } \\ { k } \end{array} \right) x ^ { k } } \end{array}$$现在让我们看一个稍微复杂一点的例子。

例 2 对正整数$m,n$，求证

$$\sum _ { k } \left( \begin{array} { c } { m } \\ { k } \end{array} \right) \left( \begin{array} { c } { m + k } \\ { m } \end{array} \right) = \sum _ { k } \left( \begin{array} { l } { m } \\ { k } \end{array} \right) \left( \begin{array} { l } { m } \\ { k } \end{array} \right) 2 ^ { k }$$让我们把两边看做指标为$m$的数列建立发生函数，用万金油方法吧！慢着，好像哪里不对。左边的两个组合数里都有$m$这样无论怎样交换和号，内层求和总有两个组合数的乘积，而我们没有这样的公式可以用！所以这里我们只能对$n$来做。接下来的计算便是万金油方法的日常。$$\begin{array} { l }{ \sum _ { n \geq 0 } \sum _ { k } \left( \begin{array} { c } { m } \\ { k } \end{array} \right) \left( \begin{array} { c } { n + k } \\ { m } \end{array} \right) x ^ { n } }\\{ = \sum _ { k } \left( \begin{array} { l } { m } \\ { k } \end{array} \right) \sum _ { n \geq 0 } \left( \begin{array} { c } { n + k } \\ { m } \end{array} \right) x ^ { n } }\\{ = \sum _ { k } \left( \begin{array} { c } { m } \\ { k } \end{array} \right) x ^ { m - k } \sum _ { n \geq 0 } \left( \begin{array} { c } { n + k } \\ { m } \end{array} \right) x ^ { n + k - m } }\\{ = \sum _ { k } \left( \begin{array} { c } { m } \\ { k } \end{array} \right) x ^ { m - k } \frac { 1 } { ( 1 - x ) ^ { m + 1 } } }\\{ = \frac { ( 1 + x ) ^ { m } } { ( 1 - x ) ^ { m + 1 } } } \end{array}$$

值得注意的是，在第二行内层，指标求和范围是$n\ge0$，但是要使用公式的话，指标求和范围应该是$n\ge m-k$才对。在这里不会引起问题，因为外层$m\choose k$的存在使得只有$m\ge k$的时候才需要算内层的和，而这时$0\le n\lt m-k$的部分又会使得内层$n+k\choose m$为$0$，从而没有影响。不要小看这些求和指标的边界条件，特别是当我们用发生函数来求值的时候有时会导致答案错误！让我们继续来计算右边。

$$\begin{array} { l }{ \sum _ { n \geq 0 } \sum _ { k } \left( \begin{array} { c } { m } \\ { k } \end{array} \right) \left( \begin{array} { l } { n } \\ { k } \end{array} \right) 2 ^ { k } x ^ { n } }\\{ = \sum _ { k } \left( \begin{array} { l } { m } \\ { k } \end{array} \right) 2 ^ { k } \sum _ { n \geq 0 } \left( \begin{array} { l } { n } \\ { k } \end{array} \right) x ^ { n } }\\{ = \sum _ { k } \left( \begin{array} { l } { m } \\ { k } \end{array} \right) ( 2 x ) ^ { k } \sum _ { n \geq 0 } \left( \begin{array} { l } { n } \\ { k } \end{array} \right) x ^ { n - k } }\\{ = \sum _ { k } \left( \begin{array} { l } { n } \\ { k } \end{array} \right) ( 2 x ) ^ { k } \frac { 1 } { ( 1 - x ) ^ { k + 1 } } }\\{ = \frac { 1 } { 1 - x } \sum _ { k } \left( \begin{array} { l } { m } \\ { k } \end{array} \right) ( \frac { 2 x } { 1 - x } ) ^ { k } }\\{ = \frac { 1 } { 1 - x } ( 1 + \frac { 2 x } { 1 - x } ) ^ { m } }\\{ = \frac { ( 1 + x ) ^ { m } } { ( 1 - x ) ^ { m + 1 } } } \end{array}$$

两个形式幂级数相等，从而对应项的系数相等。这里略出乎我们意料的是，我们其实不知道这个系数具体是多少，只知道发生函数长什么样。在用万金油方法证明组合恒等式的过程中，这是经常出现的现象。再让我们看一个简单但万金油方法用起来略有些卡手的例子。

例 3 证明

$$\sum _ { k } \left( \begin{array} { l } { n } \\ { k } \end{array} \right) \left( \begin{array} { c } { 3 n } \\ { 2 n - k } \end{array} \right) = \left( \begin{array} { l } { 4 n } \\ { 2 n } \end{array} \right)$$说这个题简单是因为发生函数的闭形式很容易猜出来，然后反推即可。具体来说，我们只需要将恒等式$(1+x)^n(1+x)^{3n}=(1+x)^{4n}$两边展开，比较$x^{2n}$的系数就可以得到答案。但是应用万金油方法的难点在于$$\sum _ { n } \sum _ { k } \left( \begin{array} { l } { n } \\ { k } \end{array} \right) \left( \begin{array} { c } { 3 n } \\ { 2 n - k } \end{array} \right) x ^ { n } = ( 1 + x ) ^ { n } ( 1 + x ) ^ { 3 n }$$不容易直接通过计算证明。主要问题是$n$这个变量出现在两个组合数中，交换和号以后内层求和依然有两个组合数。解决这个问题我们只需要加强命题，来证明$$\sum _ { k } \left( \begin{array} { c } { n _ { 1 } } \\ { k } \end{array} \right) \left( \begin{array} { c } { n _ { 2 } } \\ { n _ { 3 } - k } \end{array} \right) = \left( \begin{array} { c } { n _ { 1 } + n _ { 2 } } \\ { n _ { 3 } } \end{array} \right)$$即可。之后的计算都是万金油方法的常规路数了，证明的细节留给读者思考。在一些更复杂的情况下，如果变量出现的次数太多，我们可以考虑加强命题来使用万金油方法。

小练习：例 1 当中可以把$n$当做参数来建立发生函数用万金油方法吗？对$m,n$双重指标可不可以？答案是肯定的，细节留给读者思考。

说几句题外话。我们在研究一个数学对象的同时，把和它类似的所有对象放在一起考虑是大有益处的。这些对象聚在一起往往能赋予新的结构，并给我们以新的视角来研究原先的个体，正如我们在使用万金油方法时所做的那样。这种思维方式在 20 世纪的代数几何，数论和表示论的研究里有着广泛的应用。代数曲线的模空间就是这么建立起来的。粗略地来说，每一类同构的曲线对应模空间中一个点，而曲线任何连续变化的过程，都可以从曲线对应的点在模空间中连续变化探测到。从阿贝尔簇，向量丛，代数曲线基本群的表示，到更复杂的 Shtuka 都可以建立模空间。几何 Langlands 纲领研究的就是在特定的模空间上几何对象的对应关系。

扯远了，我们就聊到这里。希望发生函数和万金油方法能在解决组合恒等式当中提供一种新的思路，在解决困难问题的时候发挥出它的威力。

hbghlyj

en.wikipedia.org/wiki/Generating_function#Introducing_a_free_parameter_(snake_oil_method)
Sometimes the sum $s_n$ is complicated, and it is not always easy to evaluate. The "Free Parameter" method is another method (called "snake oil" by H. Wilf) to evaluate these sums.

Both methods discussed so far have $n$ as limit in the summation. When $n$ does not appear explicitly in the summation, we may consider $n$ as a “free” parameter and treat $s_n$ as a coefficient of $F(z) = \sum{s_n z^n}$, change the order of the summations on $n$ and $k$, and try to compute the inner sum.

For example, if we want to compute
$$s_n = \sum_{k = 0}^{\infty}{\binom{n+k}{m+2k}\binom{2k}{k}\frac{(-1)^k}{k+1}} \quad (m,n \in \mathbb{N}_0),$$
we can treat $n$ as a "free" parameter, and set
$$F(z) = \sum_{n = 0}^{\infty}{\left[ \sum_{k = 0}^{\infty}{\binom{n+k}{m+2k}\binom{2k}{k}\frac{(-1)^k}{k+1}}\right] }z^n.$$

Interchanging summation (“snake oil”) gives
$$F(z) = \sum_{k = 0}^{\infty}{\binom{2k}{k}\frac{(-1)^k}{k+1} z^{-k}}\sum_{n = 0}^{\infty}{\binom{n+k}{m+2k} z^{n+k}}.$$

Now the inner sum is $\frac{z^{m+2k}}{(1-z)^{m+2k+1}}$. Thus
\begin{align*}
F(z)
&= \frac{z^m}{(1-z)^{m+1}}\sum_{k = 0}^{\infty}{\frac{1}{k+1}\binom{2k}{k}\left(\frac{-z}{(1-z)^2}\right)^k} \\
&= \frac{z^m}{(1-z)^{m+1}}\sum_{k = 0}^{\infty}{C_k\left(\frac{-z}{(1-z)^2}\right)^k} \quad \text{(where } C_k = k^\text{th} \text{ Catalan number)} \\
&= \frac{z^m}{(1-z)^{m+1}}\frac{1-\sqrt{1+\frac{4z}{(1-z)^2}}}{\frac{-2z}{(1-z)^2}} \\
&= \frac{-z^{m-1}}{2(1-z)^{m-1}}(1-\frac{1+z}{1-z}) \\
&= \frac{z^m}{(1-z)^m} = z\frac{z^{m-1}}{(1-z)^m}.
\end{align*}

Then we obtain
$$s_n = \binom{n-1}{m-1}\quad \text{ for } \quad m\geq1 \quad,\quad s_n = [n = 0]\quad \text{ for } \quad m = 0.$$

It is instructive to use the same method again for the sum, but this time take $m$ as the free parameter instead of $n$. We thus set
$$G(z) = \sum_{m = 0}^{\infty}\left[ \sum_{k = 0}^{\infty} \binom{n+k}{m+2k}\binom{2k}{k}\frac{(-1)^k}{k+1} \right] z^m.$$

Interchanging summation ("snake oil") gives
$$G(z) = \sum_{k = 0}^{\infty} \binom{2k}{k}\frac{(-1)^k}{k+1} z^{-2k} \sum_{m = 0}^{\infty} \binom{n+k}{m+2k} z^{m+2k}.$$

Now the inner sum is $(1+z)^{n+k}$. Thus
\begin{align*}
G(z)
&= (1+z)^n \sum_{k = 0}^{\infty} \frac{1}{k+1}\binom{2k}{k}\left(\frac{-(1+z)}{z^2}\right)^k \\
&= (1+z)^n \sum_{k = 0}^{\infty} C_k \,\left(\frac{-(1+z)}{z^2}\right)^k \quad \text{(where } C_k = k^\text{th} \text{ Catalan number)} \\
&= (1+z)^n \,\frac{1-\sqrt{1+\frac{4(1+z)}{z^2}}}{\frac{-2(1+z)}{z^2}} \\
&= (1+z)^n \,\frac{z^2-z\sqrt{z^2+4+4z}}{-2(1+z)} \\
&= (1+z)^n \,\frac{z^2-z(z+2)}{-2(1+z)} \\
&= (1+z)^n \,\frac{-2z}{-2(1+z)} = z(1+z)^{n-1}.
\end{align*}

Thus we obtain
$$s_n = \left[z^m\right] z(1+z)^{n-1} = \left[z^{m-1}\right] (1+z)^{n-1} = \binom{n-1}{m-1},$$
for $m \geq 1$ as before.