资源描述：
《组合数学课件-第二章第三节关于线性常系数非齐次递推关系》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、第2章递推关系与母函数2.1递推关系2.2母函数(生成函数)2.3Fibonacci数列2.4优选法与Fibonacci序列的应用2.5母函数的性质2.6线性常系数齐次递推关系2.7关于常系数非齐次递推关系2.8整数的拆分2.9ferrers图像2.10拆分数估计2.11指数型母函数2.12广义二项式定理2.13应用举例2.14非线性递推关系举例2.15递推关系解法的补充12.7关于线性常系数非齐次递推关系如下面的递推关系：称为k阶线性递推关系，其中若c1,c2,…,ck都是常数，则称为常系数线性递
2、推关系，若bn=0，则称为是齐次的，否则为非齐次的。22.10任意阶齐次递推关系设r1,r2,…,rs是线性常系数齐次递推关系的不同的特征根，并设hi是ri的重根数，i=1,2,3,…,s。则3Fibonacci递归算法:intfibonacci(intn){if(n=1
3、
4、n=2)return(1);elsereturn(fibonacci(n-1)+fibonacci(n-2));}2.1递推关系时间复杂性：f(n)=f(n-1)+f(n-2)+142.7关于线性常系数非齐次递推关系如果序列xn
5、和yn满足非齐次递推关系，对应的齐次递推关系。则序列zn=xn-yn满足其对应的齐次递推关系。证明：略52.7关于线性常系数非齐次递推关系特解与一般解:例2：某人有n元钱，一次可买1元的矿泉水，也可以买2元的（啤酒、方便面）的一种，直到所有的钱花完为止(买东西的顺序不同，也算不同方案)，求n元钱正好花完的买法方案数。解：递推关系：an=an-1+2an-2a1=1,a2=3特征方程x2-x-2=0的根r1=-1，r2=26定理1若fn是线性常系数非齐次递推关系的特解，则这个线性常系数非齐次递推关系的
6、解有如下形式：an=fn+对应的线性常系数齐次递推关系的解。证明：fn是特解，设sn是一个解令tn=sn-fn2.7关于线性常系数非齐次递推关系则序列{ti}是线性常系数齐次递推关系的解sn=tn+fn证毕72.7关于线性常系数非齐次递推关系一阶、二阶线性常系数非齐次递推关系(1)右端项为常数han+ban-1=c(n)(2)右端项为hmn,h为常数，m为已知整数。an+ban-1+can-2=c(n)8下面讨论若干特殊右端项的找特解的办法。(1)猜解法:猜an解的可能情况?2.7关于线性常系数非齐
7、次递推关系an+ban-1=hmn,h为常数，m为已知整数。9下面讨论若干特殊右端项的找特解的办法。(1)猜解法:设an=kmn2.7关于线性常系数非齐次递推关系an+ban-1=hmn,h为常数，m为已知整数。kmn+bkmn-1=hmn,km+bk=hm,m等于-b时无效m是特征方程的根时无效10设an=kmn2.7关于线性常系数非齐次递推关系an+ban-1+can-2=hmn,h为常数，m为已知整数。kmn+bkmn-1+ckmn-2=hmn,km2+bkm+ck=hm2,分母为零时无效m是
8、特征方程的根时无效11例1假定特解为：两边同除以4n-2：2.7关于线性常系数非齐次递推关系12特征方程2.7关于线性常系数非齐次递推关系13例2假定特解为：c×3n,代入递推关系。无解！对于这种情况怎么处理?2.7关于线性常系数非齐次递推关系14故导致二阶齐次递推关系，（1）式的解必然是（2）式的解，但（2）式解不一定是（1）式的解。(2)划为高阶齐次递推关系，通过比较推测递推关系的特解an-ban-1=hmn,an-1-ban-2=hmn-1,an-ban-1=hmn,(1)man-1-mban
9、-2=hmn,an-(b+m)an-1+bman-2=0（2）2.7关于线性常系数非齐次递推关系15若b=m,则解为:（2）式的特征方程是：x2-(b+m)x+bm=0,它有两个特征根b和m。若b≠m,则解为:2.7关于线性常系数非齐次递推关系an=k1bn+k2mn,an=(k1+k2n)mn,16分别讨论如下：(a)若b≠m,则an-ban-1=hmn的解必可写成如下形式。an=k1bn+k2mn,定理1可知，非齐次递推关系的解可表示为齐次递推关系的解加上特解fn。比较可得：fn=k2mn,k2
10、是待定系数，代入递推关系an-ban-1=hmn，k2mn-bk2mn-1=hmnk2=hm/(m-b),因此fn=[hm/(m-b)]mn是特解2.7关于线性常系数非齐次递推关系17解:2.7关于线性常系数非齐次递推关系例3:18(b)若b=m,即an-ban-1=hbn其中b和h都是已知常数。但当b=m时，对应的二阶齐次递推关系an-(b+m)an-1+bman-2=0的解为：an=(l+kn)bn2.7关于线性常系数非齐次递推关系所以fn=knbn令an=knb
