Problem 1
用生成函数求解递推式 $$ a_{n} = 4a_{n-1} - 5a_{n-2} + 2a_{n-3} $$ 初始值为 $ a_{0}=0,a_{1}=3,a_{2}=7 $。
解：
设数列 $ \{ a_{n} \} $ 的生成函数为 $ F(x) $，那么根据递推式和初值 $ a_{0}=0,a_{1}=3,a_{2}=7 $ 得到 $$ F(x) = 4xF(x) - 5x^{2}F(x) + 2x^{3}F(x) + 3x - 5x^{2} $$ 得到 $$ F(x) = \dfrac{5x^{2}-3x}{2x^{3}-5x^{2}+4x-1} = \dfrac{3x-5x^{2}}{(1-x)^{2}(1-2x)} $$ 我们希望分解成 $$ \dfrac{A}{1-x} + \dfrac{B}{(1-x)^{2}} + \dfrac{C}{1-2x} $$ 待定系数可以解得 $$ F(x) = \dfrac{-3}{1-x} + \dfrac{2}{(1-x)^{2}} + \dfrac{1}{1-2x} $$ 展开得到 $$ F(x) = \sum_{n=0}^{\infty} (-3+2(n+1)+2^{n})x^{n} $$ 因此 $$ a_{n} = -3+2(n+1)+2^{n} = 2^{n} + 2n - 1 $$
Problem 2
(1)
设 $ f(n) $ 为集合 $ [n] $ 中不包含两个连续数字的子集数量，求 $ f(n) $ 的递推关系。
解：
容易得到 $ f(0)=1,f(1)=2,f(2)=3,f(3)=\dots $。考虑集合 $ [n]=\{ 1,2,\dots,n \} $，如果选择的子集中包含 $ n $，那么一定不包含 $ n-1 $，等价于从 $ [n-2] $ 中选择；如果不包含 $ n $，那么等价于从 $ [n-1] $ 中选择，因此 $ f(n)=f(n-1)+f(n-2) $。这样就找出了 $ f(n) $ 的递推关系，进一步同理斐波那契数列，我们考虑求出通项。
设生成函数 $ F(x)=\sum_{n=0}^{\infty}f(n)x^{n} $，满足 $ F(x)=xF(x-1)+x^{2}F(x-2)+1+x $，解出 $$ F(x) = \dfrac{1+x}{1-x-x^{2}} \xlongequal{\phi= \frac{1+\sqrt{ 5 }}{2},\psi= \frac{1-\sqrt{ 5 }}{2}} \dfrac{\phi^{2} / \sqrt{ 5 }}{1 - \phi x} - \dfrac{\psi^{2} / \sqrt{ 5 }}{1 - \psi x} $$ 展开得到 $$ F(x) = \sum_{n=0}^{\infty} \left( \dfrac{\phi^{n+2}- \psi^{n+2}}{\sqrt{ 5 }} \right)x^{n} $$ 于是 $$ f(n) = \dfrac{\phi^{n+2} - \psi^{n+2}}{\sqrt{ 5 }} = \dfrac{1}{\sqrt{ 5 }}\left( \left( \dfrac{1+\sqrt{ 5 }}{2} \right)^{n+2} - \left( \dfrac{1-\sqrt{ 5 }}{2} \right)^{n+2} \right) $$
(2)
设 $ f(n,k) $ 为集合 $ [n] $ 中不包含两个连续数字的 $ k $-子集（大小为 $ k $ 的子集）的数量。求 $ f(n,k) $ 的递推关系，找到一个合适的生成函数，并求出这些数本身。
解：
同理先考虑 $ f(n,k) $ 的递推关系。从 $ [n] $ 中选出不包含连续数字的大小为 $ k $ 的子集，如果选出的子集包含 $ n $，那么可以看成从 $ [n-2] $ 中选取有 $ k-1 $ 个元素的子集，否则看成从 $ [n-1] $ 中选出 $ k $ 个元素，得到递推式 $$ f(n,k)=f(n-2,k-1) + f(n-1,k) $$ 边界条件有 $ f(n,0)=1,f(n,k< 0)=f(n,k>n)=0,f(1,1)=1 $。
于是我们定义 $$ F_{k}(x) = \sum_{n=0}^{\infty} f(n,k)x^{n} $$ 对于 $ k=0 $， $$ F_{0}(x) = \sum_{n=0}^{\infty} x^{n} = \dfrac{1}{1-x} $$ $ k=1 $ 时 $$ F_{1}(x) = \sum_{n=0}^{\infty} nx^{n} = \dfrac{x}{(1-x)^{2}} $$ $ k> 1 $ 时边界条件不会影响递推 $$ F_{k}(x) = \sum_{n=k}^{\infty} f(n,k)x^{n} = \sum_{n=k}^{\infty} f(n-1,k)x^{n} + \sum_{n=k}^{\infty} f(n-2,k-1)x^{n} = xF_{k}(x) + x^{2}F_{k-1}(x) $$ 于是 $$ F_{k}(x) = \dfrac{x^{2}}{1-x}F_{k-1}(x) = \left( \dfrac{x^{2}}{1-x} \right)^{k-1}F_{1}(x) = \dfrac{x^{2k-1}}{(1-x)^{k+1}} $$ 现在需要从这个形式中提取出 $ f(n,k) $。
根据广义二项式定理 $$ \dfrac{1}{(1-x)^{k+1}} = \sum_{n=0}^{\infty} \binom{ n+k }{ k } x^{n} $$ 带入即可得到 $$ F_{k} = \sum_{n=0}^{\infty} \binom{ n+k }{ k } x^{n+2k-1} \xlongequal{m=n+2k-1} \sum_{m=2k-1}^{\infty} \binom{ m-k+1 }{ k } x^{m} $$
于是 $$ f(n,k)=\binom{ n-k+1 }{ k } \quad (n\geq 2k) $$ （显然 $ n< 2k-1 $ 时不可能找出不含两个连续数字，大小为 $ k $ 的子集，结果符合直觉）
(3)
设 $ F_{n} $ 为斐波那契数列的第 $ n $ 项，证明 $$ F_{n+1} = \sum_{k\geq 0}\binom{ k }{ n-k } $$ 证：
由于斐波那契数列，有 $ F_{n+1}=F_{n}+F_{n-1} $，容易推导出其生成函数为 $ G(x) = \dfrac{1}{1-x-x^{2}} $。
现在考虑 $ h_{n}=\sum_{k\geq 0}\binom{ k }{ n-k } $，生成函数为 $ H(x)=\sum_{n=0}^{\infty}h_{n}x^{n} $，化简得到 $$ \begin{align*} H(x) & = \sum_{n=0}^{\infty} \sum_{k=0 }^{\infty} \binom{ k }{ n-k }x^{n} \\ & \xlongequal{ i=k,j=n-k} \sum_{i=0}^{\infty} \sum_{j=0}^{\infty} \binom{ i }{ j } x^{i+j} \\ & = \sum_{i=0}^{\infty} x^{i}\sum_{j=0}^{i} \binom{ i }{ j } x^{j} \\ & = \sum_{i=0}^{\infty} x^{i}\cdot(1+x)^{i} = \sum_{i=0}^{\infty} (x+x^{2})^{i} \\ & = \dfrac{1}{1-x-x^{2}} = G(x) \end{align*} $$ 因此 $ F_{n+1}=h_{n} $，证毕！
Problem 3
(1)
对于任意正整数 $ n $ 和 $ k $，定义 $ f(n, k) $ 如下：对于将 $ n $ 写成有序的 $ k $ 个非负整数之和的每一种方式，设 $ S $ 为这 $ k $ 个整数的乘积。那么 $ f(n, k) $ 是通过这种方式获得的所有 $ S $ 的总和。请找到 $ f(n, k) $ 的合适生成函数，并求出这些数本身。
证 1
设 $ x_{1}+x_{2}+\dots+x_{k}=n $，我们需要 $ \prod_{i=1}^{k}x_{i} $。
对于 $ x_{i} $，它对求和的贡献就是 $ x_{i} $，所以我们考虑生成函数 $ \sum_{x_{i}=0}^{\infty}x_{i}z^{x_{i}}=\frac{z}{(1-z)^{2}} $。$ k $ 个这样的变量叠加可以表示为 $$ \left( \sum_{x_{1}=0}^{\infty} x_{1}z^{x_{1}} \right)\left( \sum_{x_{2}=0}^{\infty} x_{2}z^{x_{2}} \right)\dots\left( \sum_{x_{k}=0}^{\infty} x_{k}z^{x_{k}} \right) = \dfrac{z^{k}}{(1-z)^{2k}} $$ 展开以后就可以得到 $$ \sum_{x_{1},\dots,x_{n}} \prod_{i=1}^{k}x_{i}\cdot z^{\sum x_{i}} = \sum_{n=1}^{\infty} f(n,k)z^{n} = \dfrac{z^{k}}{(1-z)^{2k}} $$ 因此 $ f(n,k) $ 的生成函数为 $$ H_{k}(x) = \dfrac{x^{k}}{(1-x)^{2k}} $$ 由于 $$ \dfrac{1}{(1-x)^{2k}} = \sum_{n=0}^{\infty} \binom{ n+2k-1 }{ 2k-1 } x^{n} $$ 于是 $$ H_{k}(x) = \sum_{n=0}^{\infty} \binom{ n+2k-1 }{ 2k-1 } x^{n+k} \xlongequal{m=n+k} \sum_{m=k}^{\infty} \binom{ m+k-1 }{ 2k-1 } x^{m} $$ 于是 $$ f(n,k) = \binom{ n+k-1 }{ 2k-1 } $$
证 2
考虑递推关系 $$ f(n,k) = \begin{cases} 0 & ,k\geq n+1 \\ n & ,k = 1 \\ \sum_{r=0}^{n} rf(n-r,k-1) & ,\text{others} \end{cases} $$ 于是设对应的生成函数为 $ H_{k}(x) $。
首先 $$ H_{1}(x) = \sum_{n=0}^{\infty} nx^{n} = \dfrac{x}{(1-x)^{2}} $$ 之后我们需要对 $ H_{k}(x) $ 建立递推关系： $$ \begin{align*} H_{k}(x) & = \sum_{n=0}^{\infty} f(n,k)x^{n} = \sum_{n=0}^{\infty} \sum_{r=0}^{n} rf(n-r,k-1)x^{n} \\ & \xlongequal{i=r,j=n-r} \sum_{i=0}^{\infty} \sum_{j=0}^{\infty} if(j,k-1)x^{i+j} \\ & = \sum_{j=0}^{\infty} f(j,k-1)x^{j}\left( \sum_{i=0}^{\infty} ix^{i} \right) \\ & = H_{1}(x)\cdot H_{k-1}(x) \end{align*} $$ 于是 $$ H_{k}(x) = \dfrac{x}{(1-x)^{2}}H_{k-1}(x) = \dfrac{x^{k}}{(1-x)^{2k}} $$ 后续步骤相同。
(2)
设 $ f(n, k, c) $ 为将 $ n $ 写成有序的 $ k $ 个整数之和的方式数量，其中每个整数至少为 $ c $。请找到 $ f(n, k, c) $ 的合适生成函数，并求出这些数本身。
证：
同理 $ (1) $ ，由于此时需要的是计数，每个值的贡献都是 $ 1 $，因此对于 $ x_{i} $ 的生成函数为 $ \sum_{x_{i}=c}^{\infty}z^{x_{i}} = \dfrac{z^{c}}{1-z} $ 因此 $ k $ 个变量叠加表示为 $$ \left( \sum_{x_{1}=c}^{\infty} z^{x_{1}} \right)\left( \sum_{x_{2}=c}^{\infty} z^{x_{2}} \right)\dots\left( \sum_{x_{k}=c}^{\infty} z^{x_{k}} \right) = \dfrac{z^{ck}}{(1-z)^{k}} $$ 同时展开可以得到 $$ H_{c,k}(z) = \sum_{n=ck}^{\infty} f(n,c,k)z^{n} = \dfrac{z^{ck}}{(1-z)^{k}} $$ 这就得到了 $ f(n,c,k) $ 的生成函数。
下面求出数列通项。根据广义二项式定理 $$ \dfrac{1}{(1-z)^{k}} = \sum_{n=0}^{\infty} \binom{ n+k-1 }{ k-1 } z^{n} $$ 于是 $$ \begin{align*} H_{c,k}(z) & = \sum_{n=0}^{\infty} \binom{ n+k-1 }{ k-1 } z^{n+ck} \\ & \xlongequal{m = n+ck} \sum_{m=ck}^{\infty} \binom{ m-ck+k-1 }{ k-1 } z^{m} \end{align*} $$ 得到 $$ f(n,c,k) = \dbinom{ n-ck+k-1 }{ k-1 } $$