前几天在《Discrete Mathematics and its Applications》上看到了这三道题,均要求使用生成函数求解,题目如下:
- ak = ak-1 + 2ak-2 + 2k, a0 = 4, a1 = 12
- ak = 4ak-1 - 4ak-2 + k2, a0 = 2, a1 = 5
- ak = 2ak-1 - 3ak-2 + 4k + 6, a0 = 20, a1 = 60
昨天在StackExchange[1]上询问之后,今天花了一早上的时间做了一遍,下面就是完整的步骤和总结。
- Problem 1
我们首先令f(x)为序列{ak}的生成函数,即
然后我们对递推关系式(也就是上面大括号中的第一个式子)中的每一项都乘以xk,得
接着对每一项都取k从2开始的和
在这之后我们将对每一项都进行变形,变形之后将会消去求和符号。变形的目标是将和式写为f(x)和已知的项的和。
现在我们将变形后的式子替换回去
合并同类项,然后分解分式多项式得
根据生成函数与序列{ak}的关系,可得
至此,我们解出了满足递推关系和初始条件的解
- Problem 2
我们首先令f(x)为序列{ak}的生成函数,即
然后我们对递推关系式(也就是上面大括号中的第一个式子)中的每一项都乘以xk,得
接着对每一项都取k从2开始的和
在这之后我们将对每一项都进行变形,变形之后将会消去求和符号。变形的目标是将和式写为f(x)和已知的项的和。
最后的这个k2的和式处理稍微复杂一些
化简到这一步之后,下面我们对和式积分,然后再求导
再来一次
到了这一步之后就简单了
现在我们将变形后的式子替换回去
合并同类项,然后分解分式多项式得
根据生成函数与序列{ak}的关系,可得
展开、合并同类项
至此,我们解出了满足递推关系和初始条件的解
- Problem 3
Problem 3的和处理方式前面的Problem 1十分相似,这里不再给出解答。
- 总结
一般来讲,使用生成函数求解递推关系第一步是在递推关系式的各项上乘以xk,然后取k>=m(m为递推关系式的阶数,即如果是二阶递推关系式m就取2)时的和式并分别变形,最后通过生成函数f(x)与序列ak的关系解出。
- References
[1]: How to solve these recurrence relations bu using generating function