Using generating functions to solve recurrence relations

前几天在《Discrete Mathematics and its Applications》上看到了这三道题,均要求使用生成函数求解,题目如下:

  1. ak = ak-1 + 2ak-2 + 2k, a0 = 4, a1 = 12
  2. ak = 4ak-1 - 4ak-2 + k2, a0 = 2, a1 = 5
  3. ak = 2ak-1 - 3ak-2 + 4k + 6, a0 = 20, a1 = 60

昨天在StackExchange[1]上询问之后,今天花了一早上的时间做了一遍,下面就是完整的步骤和总结。

  • Problem 1

 ak=ak-1+2ak-2+2k a0=4 a1=12

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

fx=k0akxk

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

akxk=ak-1xk+2ak-2xk+2kxk

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

k2akxk=k2ak-1xk+k22ak-2xk+k22kxk

= k2ak-1xk+2k2ak-2xk+k22kxk

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

k2akxk=k2akxk+a1x+a0-a1x-a0

=k0akxk-a1x-a0

= fx-4x-12


k2ak-1xk=xk2ak-1xk-1

= xk1akxk

= xk0akxk-a0

= xfx-4


k2ak-2xk=x2k2ak-2xk-2

= x2k0akxk

= x2fx


k22kxk=k02kxk-2x

=11-2x-1-2x-1

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

fx-4x-12=xfx-4+2x2fx+11-2x-2x-1
合并同类项,然后分解分式多项式得

fx=23·11-2x2+389·11-2x-89·11+x

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

ak=23C2+k-12-12k+389·2k-89·-1k

=231+k2k+389·2k-89·-1k

=449·2k+23k·k3-89·-1k
至此,我们解出了满足递推关系和初始条件的解
  • Problem 2

 ak=4ak-1-4ak-2+k2 a0=2 a1=5

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

fx=k0akxk

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

akxk=4ak-1xk-4ak-2xk+k2xk

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

k2akxk=k24ak-1xk-k24ak-2xk+k2k2xk

= 4k2ak-1xk-4k2ak-2xk+k2k2xk

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

k2akxk=k2akxk+a1x+a0-a1x-a0

=k0akxk-a1x-a0

= fx-5x-2


k2ak-1xk=xk2ak-1xk-1

= xk1akxk

= xk0akxk-a0

= xfx-2


k2ak-2xk=x2k2ak-2xk-2

= x2k0akxk

= x2fx

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

k2k2xk=k0k2xk-x

=xk0k2xk-1-x

=xk0kkxk-1-x

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

=xk0kxk'-x

=xxk0kxk-1'-x

再来一次

=xxk0xk''-x

到了这一步之后就简单了

=xx11-x''-x

=xx1-x2'-x

=x1+x1-x3-x

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

fx-5x-2=4xfx-2-4x2fx+x1+x1-x3-x

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

fx=21-x3+51-x2+131-x+61-2x2-241-2x

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

ak=2C3+k-13-1+5C2+k-12-1+13+6C2+k-12-12k-24·2k

=22+k1+k2+51+k+13+61+k2k-24·2k

展开、合并同类项

=2+13+5+6·2k-24·2k+3k+5k+6k·2k+k2

=20-18·2k+8k+6k·2k+k2

至此,我们解出了满足递推关系和初始条件的解
  • 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

Leave a Reply

Your email address will not be published. Required fields are marked *

1 × 1 =