递推关系和母函数

标签（空格分隔）：数学

推荐一篇很棒很生动的博客http://ruanx.pw/post/%E7%89%B9%E5%BE%81%E6%96%B9%E7%A8%8B.html

母函数

定义

对于任意数列(a_0,a_1,a_2cdots),用如下方法与一个函数联系起来：$$G(x)=a_0+a_1x+a_2x^2+cdots$$
则称G(x)是数列的生成函数(generating function),也称为母函数.
说白了就是,你可以用多项式的n次项系数表示一个数列.那母函数有什么用呢?可以用来证明一些组合数学的定理...可以用来标准化一些数学组合意义...比如一个小学数学的例子,两盘水果,一盘2个苹果,一盘3个梨子,这些水果同类型都长得一模一样,问你,拿到3个水果的方案,你可能可以很快回答出来:"三种方案啊.1个苹果2个梨子,2个苹果1个梨,3个梨",但是用母函数就可以这样来算.

[(1+x+x^2)(1+x+x^2+x^3)=1+2x+3x^2+3x^3+2x^4+x^5 ]

哎!!3次项的系数是3!!第一个小括号里的就是拿苹果的方案,你可以不拿(1),可以拿1个(x),也可以拿两个((x^2)),由于多项式乘法会两两都相乘,最后合并同类项的时候,相同的个数的水果的方案数就合并到了一起,这就是母函数一个基本的作用.算方案数

母函数与fibonacci

设$$f_1=f_2=1f_{n+2}=f_{n+1}+f_n$$
现在我们已知递推关系,如何来找通项公式呢?引入母函数.
设$$G(X)=f_1x+f_2x^2+f_3x^3+cdots$$

[f_3=f_1+f_2\f_4=f_2+f_3\f_5=f_3+f_4\cdots ]

((1)*x^3+(2)*x^4+...)得:

[G(x)-x^2-x=x[G(x)-x]+x^2G(x) ]

移项合并同类项之后就得到:

[(1-x-x^2)G(x)=x\G(x)=frac{x}{1-x-x^2} ]

强行因式分解:

[1-x-x^2=(1-frac{1-sqrt 5}{2}x)(1-frac{1+sqrt 5}{2}x) ]

再设:

[G(x)=frac{A}{1-frac{1+sqrt 5}{2}x}+frac{B}{1-frac{1-sqrt 5}{2}x} ]

因为两个函数完全一样只要系数对应就可以了,待定系数这样接一下解得:
egin{cases}
A=frac{1}{sqrt 5}B=-frac{1}{sqrt 5}
end{cases}
带回去:设(a=frac{1+sqrt 5}{2},b=frac{1-sqrt 5}{2})

[G(x)=frac{frac{1}{1-ax}+frac{1}{1-bx}}{sqrt 5} ]

根据无穷等比数列求和可以展开写成:

[G(x)=frac{1}{sqrt 5}[(a-b)x+(a^2-b^2)x^2cdots] ]

对应的每项的系数(f_n=frac{a^n-b^n}{sqrt 5})
这是准确的通项公式,考虑如何表示得简洁一点,很容易发现(|b|<1)当n很大的时候,(b^n)是趋近于0的,这样我们就得到一个更好的式子:

[f_n=frac{1}{sqrt 5}(frac{1+sqrt 5}{2})^n ]

我们还可以写成这个样子:

[frac{f_n}{f_n-1}=frac{1+sqrt 5}{2} ]

这不是黄金分割么...难怪有人说斐波那契数列彰显了数学的美..
还有一个关于fibonacci的美丽的结论:

[f_1+f_2+...+f_n=f_{n+2} ]

恒等变换一下就好了,这个可以用来求fibonacci的前缀和.

线性常系数齐次递推关系

定义

(a_n+c_1a_{n-1}+c_2a_{n-2}+...+c_ka_{n-k}=0)
(a_0=d_0,a_1=d_1,...,ak-1=d_{k-1})
若(c_1,c2,...,c_k,d_0,d_1,...,d_{k-1})都是常数，则称之为k阶的线性常系数齐次递推关系.
特征多项式:

[C(x)=x^k+C_1x^{k-1}+...+C_{k-1}x+C_k ]

这个特征多项式...为什么要叫特征多项式呢?因为它有特征啊!废话...
当我们碰到一个递推关系,例如(f_n=2f_{n-1}+2,f_1=1),利用高中数学必修五的知识,就是把它转化为(f_n+2=2(f_{n-1}+2),f_1=1,f_2=2),令(g_n=f_n+2),(g_n)是等比数列,所以(f_n=3*2^{n-1}-2).是通过构造辅助数列求解,但是不是每个式子都可以这样方便地表示,比如有的递推关系(f_n=5f_{n-1}-6f_{n-2},f_1=1,f_2=2),这就很麻烦了.我们发现,之前的递推式总是可以写成一个数的多少次方的形式,大胆地假设一下,这个也可以表示成(f_n=k*x^n+b)的形式,x,k,b为常数.那我们来找一找.
(f_3=5*2-6*1=4\f_4=5*4-6*2=8\f_5=5*8-6*4=16)
好像还真的有规律...(f_n=2^{n-1})
(f_1=1,f_2=3)呢?
(f_3=5*3-6*1=9\f_4=5*9-6*3=27\f_5=5*27-6*9=81)
绝了,(f_n=3^{n-1})次方...绝了,那你会不会想再把(f_1f_2)换成什么别的东西会有什么新的递推关系?做梦,那是不可能的...
为什么这个式子在茫茫数海中间,为什么只有2,3对它情有独钟,怕不是有什么本质的联系...
这个联系就是接下来要讨论的特征方程.
仔细推敲一下,发现(f_n=2f_n+2)这样的式子,你要是忽略掉后面的+2,很容易发现是指数增长的,每次都乘了一个2,那像(f_n=5f_{n-1}-6f_{n-2})这样的,想象一下,(f_{n-1})是由(f_{n-2})乘了一个什么东西得来的,(f_n)是由(f_{n-1})乘了一个相同的东西得来的.那么(f_n)就是(f_{n-2})乘了一个这东西的平方得来的,然后我们要让这个递推关系成立,设这个东西为x,则:

[x^2=5x-6x ]

x有两个解对不对(x_1=2,x_2=3)!!!!哎,2,3,又出现了!
于是数学家就把这玩意叫做,特征根了.是不是很有特征啊...

用法

这个特征方程是个很有用的东西,用它可以解出所有的线性常系数齐次递推关系的通项公式.
梳理一下解这类问题的一般的过程:
1.找出递推关系
2.用含(f)的项来消掉常数,得到特征方程.
3.分情况讨论.
来看看怎么找特征方程.
拿一个例子可能会比较好理解.
比如对于一个(f_n=2*f_{n-1}+1,f_1=1),怎么消掉那个常数呢?

[f_n=2*f_{n-1}+1=3f_{n-1}+1-f_{n-1}\=3*f_{n-1}+1-2f_{n-2}-1 ]

所以$$f_n-3f_{n-1}+2f_{n-2}=0$$
哎!我么发现这个和那个定义式子长得好像!

[a_n+c_1a_{n-1}+c_2a_{n-2}+...+c_ka_{n-k}=0 ]

那对于这个例子,我们找到它的特征多项式

[C(x)=x^2-3x+2$$只要知道这个式子等于零时候的解,就可以得到递推关系了!是不是很神奇hhh,证明的话可以看组合数学第二章里面有,那个老师讲了一个小时的证明听得我头皮发麻,索性直接记结论... 这个时候我们就要分类讨论了. ####case1:没有重根若这m个单根为$t_1,t_2...t_m$ 母函数就是: $$G(x)=sum_{h=1}^mfrac{A_h}{1-t_hx}]

用无穷等比数列求和的性质可以得到

[G(x)=A_1(1+t_1x+t_1^2x^2+cdots)+A_2(1+t_2x+t_2^2x^2cdots)+cdots\ ]

所以(f_n=A_1t_1^n+A_2t_2^n+cdots+A_mt_m^n)
接着上面那个例子,特征方程的解是(x_1=1,x_2=2),带入母函数里就是:

[G(x)=frac{A_1}{1-x}+frac{A_2}{1-2x} ]

[f_1=1,f_2=3,f_n=A_1*1^n+A_2*2^n ]

$$
	herefore
egin{cases}
A_1+2A_2=1\
A_1+4A_2=3
end{cases}
	herefore
egin{cases}
A_1=-1\
A_2=1
end{cases}
\	herefore
f_n=2^n-1 
$$

case2:共轭复根

直接上例子:求(f_n-f_{n-1}+f_{n-2}=0,f_1=1,f_2=0)的通项.这个看其来和之前差不多的样子,但是写出它的特征方程:(x^2-x+1=0,x=frac{1pmsqrt {-3}}{2})就会发现,它没有实数解!!!这怎么办???
没关系,我们试着用上面的方法:

[f_n=A(frac{1+sqrt 3i}{2})^n+B(frac{1-sqrt 3i}{2})^n$$$$=frac12(1-frac{1}{sqrt 3}i)(frac{1+sqrt 3i}{2})^n+frac12(1+frac{1}{sqrt 3}i)(frac{1-sqrt 3i}{2})^n ]

这些乱七八糟的看起来很不爽对不对?想起一个美妙的等式...

[e^{pi i}+1=0 ]

复数的三角表示法:

[r(cos heta+isin heta)=re^{i heta} ]

所以我们可以把它换一种表示方式:
令$$frac{1+sqrt 3i}{2}=frac 12+frac{sqrt 3i}{2}=e^{frac {pi i}3}$$

[ herefore f_n=cosfrac{npi}{3}+frac{1}{sqrt 3}sinfrac{npi}3 ]

这样就没有i了.
针对一对共轭复根还有更简便的方法.就是直接先利用复数的指数表示法,再转化成三角表示法,最后回带通项公式,计算量要小很多.

二重根

推倒实在很麻烦,直接记结论就好,母函数:

[G(x)=sum_{h=1}^msum_{j=1}^{k_h}frac{A_{h,j}}{(1-t_hx)^{j}} ]

[f_n=sum_{h=1}^{m}sum_{j=1}^{k_h}n^{j-1}A_jt_h^j ]

再举个例子:(f_n-4f_{n-1}+4f_{n-2}=0,f_1=0,f_2=4)
特征方程:

[x^2-4x+4=0 \ herefore x_1=x_2=2 ]

[f_n=(A+Bn)2^n ]

解一下系数就可以得到,(f_n=(1+n)*2^n)

线性常系数非齐次递推关系

(a_n+c_1a_{n-1}+c_2a_{n-2}+...+c_ka_{n-k}=r^nb(n))
特解形式为 (r^n(k_0n^m+k_1n^{m+1}+cdots+k_pn^{m+p}))
用无重根为例子:$$ herefore f_n=A_1t_1^n+A_2t_2^n+cdots+A_mt_m^n+c$$
例子,(f_n-f_{n-1}-2f_{n-2}=2^nn)

[x^2-x-2=0,x_1=-1,x_2=2 ]

特解(c=2^n(k_0+k_1n)),带入原方程解得,(k_1=frac 45,k_0=frac{16}{25})
带到结论里就可以:$$ herefore f_n=A_1t_1^n+A_2t_2^n+c$$