• Problem 2

$\left\{\begin{array}{l}{a}_k=4a_{k-1}-4a_{k-2}+k^2\\ a_0=2\\ a_1=5\end{array}\right.$

我们首先令f(x)为序列{ak}的生成函数，即

$\mathit{\text{f}}\left(x\right)=\sum _{k\ge 0}{a}_k{x}^k$

然后我们对递推关系式（也就是上面大括号中的第一个式子）中的每一项都乘以xk，得

$a_k{x}^k=4a_{k-1}{x}^k-4a_{k-2}{x}^k+k^2{x}^k$

接着对每一项都取k从2开始的和

$\sum _{k\ge 2}{a}_k{x}^k=\sum _{k\ge 2}4a_{k-1}{x}^k-\sum _{k\ge 2}4a_{k-2}{x}^k+\sum _{k\ge 2}{k}^2{x}^k$

$\text{=}4\sum _{k\ge 2}{a}_{k-1}{x}^k-4\sum _{k\ge 2}{a}_{k-2}{x}^k+\sum _{k\ge 2}{k}^2{x}^k$

在这之后我们将对每一项都进行变形，变形之后将会消去求和符号。变形的目标是将和式写为f(x)和已知的项的和。

$\sum _{k\ge 2}{a}_k{x}^k=\left(\sum _{k\ge 2}{a}_k{x}^k+a_{1}x+a_0\right)-a_{1}x-a_0$

$\text{=}\sum _{k\ge 0}{a}_k{x}^k-a_{1}x-a_0$

$\text{=}\mathit{\text{f}}\left(x\right)-5x-2$


$\sum _{k\ge 2}{a}_{k-1}{x}^k=x\sum _{k\ge 2}{a}_{k-1}{x}^{k-1}$

$\text{=}x\sum _{k\ge 1}{a}_k{x}^k$

$\text{=}x\left(\sum _{k\ge 0}{a}_k{x}^k-a_0\right)$

$\text{=}x\left(\mathit{\text{f}}\left(x\right)-2\right)$


$\sum _{k\ge 2}{a}_{k-2}{x}^k=x^2\sum _{k\ge 2}{a}_{k-2}{x}^{k-2}$

$\text{=}{x}^2\sum _{k\ge 0}{a}_k{x}^k$

$\text{=}{x}^2\mathit{\text{f}}\left(x\right)$

最后的这个k2的和式处理稍微复杂一些

$\sum _{k\ge 2}{k}^2{x}^k=\sum _{k\ge 0}{k}^2{x}^k-x$

$\text{=}x\sum _{k\ge 0}{k}^2{x}^{k-1}-x$

$\text{=}x\sum _{k\ge 0}kk{x}^{k-1}-x$

化简到这一步之后，下面我们对和式积分，然后再求导



$\text{=}x{\left(x\sum _{k\ge 0}k{x}^{k-1}\right)}^{\text{'}}-x$

再来一次

$\text{=}x{\left(x{\left(\sum _{k\ge 0}{x}^k\right)}^{\text{'}}\right)}^{\text{'}}-x$

到了这一步之后就简单了

$\text{=}x{\left(x{\left(\frac{1}{1-x}\right)}^{\text{'}}\right)}^{\text{'}}-x$

$\text{=}x{\left(\frac{x}{{\left(1-x\right)}^2}\right)}^{\text{'}}-x$

$\text{=}\frac{x\left(1+x\right)}{{\left(1-x\right)}^3}-x$

现在我们将变形后的式子替换回去

$\mathit{\text{f}}\left(x\right)-5x-2=4x\left(\mathit{\text{f}}\left(x\right)-2\right)-4x^2\mathit{\text{f}}\left(x\right)+\frac{x\left(1+x\right)}{{\left(1-x\right)}^3}-x$

合并同类项，然后分解分式多项式得

$\mathit{\text{f}}\left(x\right)=\frac{2}{{\left(1-x\right)}^3}+\frac{5}{{\left(1-x\right)}^2}+\frac{13}{1-x}+\frac{6}{{\left(1-2x\right)}^2}-\frac{24}{1-2x}$

根据生成函数与序列{ak}的关系，可得

$a_k\text{=}2\mathit{\text{C}}\left(3+k-1,3-1\right)+5\mathit{\text{C}}\left(2+k-1,2-1\right)+13+6\mathit{\text{C}}\left(2+k-1,2-1\right)2^k-24\text{·}{2}^k$

$\text{=}2\frac{\left(2+k\right)\left(1+k\right)}{2}+5\left(1+k\right)+13+6\left(1+k\right)2^k-24\text{·}{2}^k$

展开、合并同类项

$\text{=}\left(2+13+5\right)+\left(6\text{·}{2}^k-24\text{·}{2}^k\right)+\left(3k+5k\right)+6k\text{·}{2}^k+k^2$

$\text{=}20-18\text{·}{2}^k+8k+6k\text{·}{2}^k+k^2$

至此，我们解出了满足递推关系和初始条件的解

• Problem 3

Problem 3的和处理方式前面的Problem 1十分相似，这里不再给出解答。

• 总结

一般来讲，使用生成函数求解递推关系第一步是在递推关系式的各项上乘以x^k，然后取k>=m(m为递推关系式的阶数，即如果是二阶递推关系式m就取2)时的和式并分别变形，最后通过生成函数f(x)与序列a_k的关系解出。

• References

[1]: How to solve these recurrence relations bu using generating function