组合数学课件第六章递推关系

组合数学课件第六章递推关系第1页，共63页，2023年，2月20日，星期二目录（1）第1章什么是组合数学1.1引例 1.2组合数学研究对象、内容和方法第2章鸽巢原理2.1鸽巢原理：简单形式2.2鸽巢原理：加强形式2.3Ramsey定理2.4鸽巢原理与Ramsey定理的应用本章小结习题第3章排列与组合3.1两个基本的计数原理3.2集合的排列与组合3.3多重集的排列与组合本章小结习题第四章二项式系数4.1二项式定理4.2组合恒等式4.3非降路径问题4.4牛顿二项式定理4.5多项式定理4.6基本组合计数的应用本章小结习题第五章包含排斥原理5.1包含排斥原理5.2多重集的r-组合数5.3错位排列5.4有限制条件的排列问题5.5有禁区的排列问题本章小结习题目录第2页，共63页，2023年，2月20日，星期二目录（2）

第六章递推关系6.1Fibonacci数列6.2常系数线性齐次递推关系的求解6.3常系数线性非齐次递推关系的求解6.4用迭代和归纳法求解递推关系本章小结习题第七章生成函数7.1生成函数的定义和性质7.2多重集的r-组合数7.3正整数的划分7.4指数生成函数与多重集的排列问题7.5Catalan数和Stiring数本章小结习题

第八章Polya定理8.1置换群中的共轭类与轨道8.2Polya定理的特殊形式及其应用本章小结习题**********************课程总结第3页，共63页，2023年，2月20日，星期二第6章递推关系

本章主要介绍递推关系的建立及几种常见的求解方法：6.1Fibonacci数列6.2常系数线性齐次递推关系的求解6.3常系数线性非齐次递推关系的求解6.4用迭代和归纳法求解递推关系第4页，共63页，2023年，2月20日，星期二第6章递推关系教学目标：1．掌握几种递推关系的建立方法；2．理解并掌握常系数线性齐次及非齐次递推关系的求解方法；3．能运用迭代归纳法求解递推关系；4．记住并理解Fibonacci数的定义及递推公式，会推导Fibonacci数的一些性质，能运用它们解决一些组合计数问题。重点：递推关系的建立方法、常系数线性齐次及非齐次递推关系的求解方法、Fibonacci数和Catalan数的定义、递推公式及性质难点：Catalan数的定义、递推公式及性质第6章递推关系第5页，共63页，2023年，2月20日，星期二§6.1递推关系定义§6.1递推关系的建立定义6.1设{H(n)}为一序列，把该序列中H(n)和它前面几个H(i)(0≤i≤n-1)用等号（或大于、小于号）关联起来的方程称做一个递推关系（递归关系）。

如第3章的错排数Dn=(n-1)(Dn-1+Dn-2)，(n≥3)

和关系式an=3an-1，(n≥1)都是递推关系。如a0=d0

,a1=d1,…,ak=dk，di为常数(i=0,1,…,k)，称为递推关系的初值。

如D1=0,D2=1作为初值即可惟一的确定序列(D0,D1,…,Dn,…)，a0=1作为初值即可惟一的确定序列(1,3,32,…,3n,…)。将递推关系和初值结合起来称为带初值的递推关系。如第6页，共63页，2023年，2月20日，星期二§6.1递推关系建立例1-1§6.1递推关系的建立（Fibonacci数列）例题例1、在一个平面上有一个圆和n条直线，这些直线中的每一条在圆内都同其他的直线相交。如果没有多于三条的直线相交于一点，试问这些直线将圆分成多少个不同区域？第7页，共63页，2023年，2月20日，星期二§6.1递推关系建立例1-2§6.1递推关系的建立例题解：要求解这个问题，首先必须建立递推关系，然后求解递推关系即可。设这n条直线将圆分成的区域数为an，如果有n-1条直线将圆分成an-1个区域，那么再加入第n条直线与在圆内的其他n-1条直线相交。显然，这条直线在圆内被分成n条线段，而每条线段又将第n条直线在圆内经过的区域分成两个区域。这样，加入第n条直线后，圆内就增加了n个区域。而对于n=0，显然有a0=1，于是对于每个整数n，可以建立如下带初值的递推关系（求解方法以后几节再介绍）这就是问题的解答。第8页，共63页，2023年，2月20日，星期二§6.1递推关系建立例2§6.1递推关系的建立例题例2、在一个平面中，有n个圆两两相交，但任二个圆不相切，任三个圆无公共点，求这n个圆把平面分成多个区域？解：设这n个圆将平面分成an个区域。如图。易见，a1=2,a2=4。现在假设前n-1个圆将平面分成了an-1个区域，当加入第n个圆时，由题设这个圆与前面的n-1个圆一定交于2(n-1)个点，这2(n-1)个点把第n个圆分成2(n-1)条弧，而每条弧正好将前面的n-1个圆分成的区域中的其经过的每个区域分成2个区域，故新加入的第n个圆使所成的区域数增加了2(n-1)。因此可以建立如下带初值的递推关系：

求解这个递推关系可以得到问题的解答。第9页，共63页，2023年，2月20日，星期二§6.1递推关系建立例3-1§6.1递推关系的建立例题例3、“Fibonacci兔子问题”也是组合数学中的著名问题之一。这个问题是指：从某一年某一月开始，把雌雄各一的一对兔子放入养殖场中，从第二个月雌兔每月产雌雄各一的一对新兔。每对新兔也是从第二个月起每月产一对兔子。试问第n个月后养殖场中共有多少对兔子？第10页，共63页，2023年，2月20日，星期二§6.1递推关系建立例3-1

表示幼兔表示成兔实线表示成长虚线表示生殖1:12:13:24:35:56:87:13§6.1递推关系的建立第11页，共63页，2023年，2月20日，星期二§6.1递推关系建立例3-2§6.1递推关系的建立例题解：设第n个月时养殖场中兔子的对数为Fn。并定义F0=1，显然有，F1=1。由于在第n个月时，除了有第n-1个月时养殖场中的全部兔子Fn-1外，还应该有Fn-2对新兔子，这是因为在第n-2个月就已经有的每对兔子，在第n个月里都应生一对新的兔子。因此可以建立如下带初值的递推关系

求解上式可以得到我们所需的答案。注：利用该式我们可以推得(F0,F1,…,Fn,…)=(1,1,2,3,5,8,13,21,34,55,…)常称Fn为Fibonacci数，(F0,F1,…,Fn,…)为Fibonacci数列。Fibonacci数列在数学中是一个奇特而又常见的序列，它在算法分析中起着重要的作用。注：以上各例均为经典组合数学问题，在算法分析中常用；对普通的递推关系无一般规则可解。

第12页，共63页，2023年，2月20日，星期二§6.1Fibonacci数列应用及性质§6.1递推关系的建立Fibonacci数列在组合计数中的应用例：确定2×n棋盘用多米诺牌完美覆盖的方法数hn。规定h0=1.容易看到h1=1，h2=2，h3=3。

hn=hn1

满足斐波那契递推关系。hn是斐波那契数。

+hn2第13页，共63页，2023年，2月20日，星期二

再如，一个人站在“梯子格”的起点处向上跳，从格外只能进入第1格，从格中，每次可向上跳一格或两格，问：可以用多少种方法，跳到第n格？§6.1递推关系的建立Fibonacci数列在组合计数中的应用解：设跳到第n格的方法有种。由于他跳入第1格，只有一种方法；跳入第2格，必须先跳入第1格，所以也只有一种方法，从而第14页，共63页，2023年，2月20日，星期二

而能一次跳入第n格的，只有第和第两格，因此，跳入第格的方法数，是跳入第格的方法数，加上跳入第格的方法数之和。即。综合得递推公式

容易算出，跳格数列就是斐波那契数列

1，1，2，3，5，8，13，21，34，…§6.1递推关系的建立Fibonacci数列在组合计数中的应用第15页，共63页，2023年，2月20日，星期二§6.1Fibonacci数列应用及性质§6.1递推关系的建立类似的例子奇妙的斐波那契序列斐波那契螺旋线数第16页，共63页，2023年，2月20日，星期二6.1Fibonacci数列应用及性质树杈的数目13853211§6.1递推关系的建立类似的例子第17页，共63页，2023年，2月20日，星期二§6.1Fibonacci数列应用及性质（1）§6.1递推关系的建立Fibonacci数列性质1.Fibonacci数可以表示为二项式系数之和，即证明当时，有，即，所以只要证明下面的等式成立，即证用归纳法。当时，有成立。假设对等式都成立，则有第18页，共63页，2023年，2月20日，星期二§6.1Fibonacci数列应用及性质由归纳法，命题成立。§6.1递推关系的建立Fibonacci数列性质第19页，共63页，2023年，2月20日，星期二§6.1Fibonacci数列应用及性质（2）§6.1递推关系的建立Fibonacci数列性质2.Fibonacci数证明把以上各式的左边和右边分别相加，得第20页，共63页，2023年，2月20日，星期二§6.1Fibonacci数列应用及性质（3-4）§6.1递推关系的建立Fibonacci数列性质3.Fibonacci数证明把以上各式的左边和右边分别相加，得4.Fibonacci数证明由性质2和3即得.第21页，共63页，2023年，2月20日，星期二§6.1Fibonacci数列应用及性质（5）§6.1递推关系的建立Fibonacci数列性质5.证明把以上各式的左边和右边分别相加，得第22页，共63页，2023年，2月20日，星期二§6.1Fibonacci数列应用及性质（6）§6.1递推关系的建立Fibonacci数列性质6.证明由归纳法，等式成立。对进行归纳.当时，有成立，假设对一切有等式成立，则第23页，共63页，2023年，2月20日，星期二§6.1Fibonacci数列应用及性质§6.1递推关系的建立Fibonacci数列性质

关于Fibonacci数列的性质还有许多，习题上也列出了一部分，这里就不一一介绍。利用这些性质，我们可以将比较大的n的Fibonacci数化成较小的的Fibonacci数，从而使计算更为方便。第24页，共63页，2023年，2月20日，星期二§6.2常系数线递推关系次递推关系§6.2常系数线性齐次递推关系定义6.2

若{H(n)}中相邻k+1项满足H(n)=a1H(n-1)+a2H(n-2)+…+akH(n-k)，(n≥k)称之为{H(n)}的k阶常系数线性齐次递推关系。其中ai(i=1,2,…,k)是常数，且ak≠0。该递推关系还可以写作

H(n)-a1H(n-1)-a2H(n-2)-…-akH(n-k)=0.H(0)=d0,

H(1)=d1,

…,

H(k-1)=dk-1称为初始条件，其中di(i=0,2,…,k-1)是常数；定义6.3C(x)=xk-a1xk-1-a2xk-2-…-ak称为上述递推关系的特征多项式；

C(x)=0称为上述递推关系的特征方程；该方程的k个根q1,q2,…qk称为上述递推关系的特征根.其中qi(i=1,2,…,k)是复数.第25页，共63页，2023年，2月20日，星期二§6.2常系数线递推关系次递推关系定理6.1对此，有下面的定理定理6.1§6.2常系数线性齐次递推关系设k阶常系数线性齐次递推关系{H(n)}为若q≠0,H(n)=qn是上述递推关系的解，当且仅当q是上述特征方程的解。证明：若q0,H(n)=qn是递推关系的解

qn

=a1qn-1

+a2qn-2

+…+akqn-k(n≥k)qk

=a1qk-1

+a2qk-2

+…+ak

q是特征方程xk-a1xk-1-a2xk-2-…-ak=0的根。证毕。第26页，共63页，2023年，2月20日，星期二定理6.2

若都是齐次递推关系的解，那么也是齐次递推关系的解。证:由是齐次递推关系的解知§6.2常系数线递推关系次递推关系定理6.2§6.2常系数线性齐次递推关系第27页，共63页，2023年，2月20日，星期二§6.2常系数线性齐次相异特征根定理6.3§6.2常系数线性齐次递推关系6.2.1相异特征根的解法定理6.3若q1,q2,…,qk,为上述递推关系的特征根（相异），c1,

c2,…,ck为任意常数，则an=c1q1n+c2q2n+…+ckqkn为上述递推关系的解。证明：由于qi(i=1,2,…,k)是特征方程xk-b1xk-1-b2xk-2-…-bk=0的根，由定理6.1有qin

=b1qin-1

+b2qin-2

+…+bk

qin-k，i=1,2,…,k将上式两边同乘以ci

，然后从1到k求和有因此an=c1q1n+c2q2n+…+ckqkn是递推关系an=b1an-1+b2an-2+…+bkan-k的解。第28页，共63页，2023年，2月20日，星期二§6.2常系数线性齐次相异特征根定义6.4§6.2常系数线性齐次递推关系6.2.1相异特征根的解法定义6.4如果对于递推关系H(n)=b1H(n-1)+b2H(n-2)+…+bkH(n-k)的每个解h(n)都可以选择一组常数使得成立，则称是递推关系的通解，其中为任意常数。第29页，共63页，2023年，2月20日，星期二§6.2常系数线性齐次相异特征根定理6.4§6.2常系数线性齐次递推关系6.2.1相异特征根的解法定理6.4若q1,q2,…,qk为上述递推关系的特征根（相异），则an=c1q1n+c2q2n+…+ckqkn为上述递推关系的通解，其中ci由初始条件确定。证明：由定理6.2知，an=c1q1n+c2q2n+…+ckqkn是递推关系an=b1an-1+b2an-2+…+bkan-k的解。只需证明，若该式满足递推关系式an=b1an-1+b2an-2+…+bkan-k的任意初值条件式a0=d0,a1=d1,

…,

ak-1=dk-1所得到的关于c1,c2,…,ck的线性方程组有惟一解即可。由初值条件式a0=d0,a1=d1,…,ak-1=dk-1，我们得到因此，上述线性方程组关于c1,c2,…,ck有惟一的解。从而证明了an=c1q1n+c2q2n+…+ckqkn

是递推关系的an=b1an-1+b2an-2+…+bkan-k的通解。第30页，共63页，2023年，2月20日，星期二例1、求递归关系§6.2常系数线性齐次例1§6.2常系数线性齐次递推关系5.2.1相异特征根的解法例题第31页，共63页，2023年，2月20日，星期二§6.2常系数线性齐次例2§6.2常系数线性齐次递推关系6.2.1相异特征根的解法例题例2、求递归关系

第32页，共63页，2023年，2月20日，星期二§6.2常系数线性齐次例3-1§6.2常系数线性齐次递推关系6.2.1相异特征根的解法例题例3、用字母a,b和c组成长度是n的字，如果要求没有两个a相邻，问这样的字有多少个？解设h(n)是所求的字的个数，n≥1.易见，长为1的且没有两个a相邻的字有a,b和c，所以h(1)=3.长为2的没有两个a相邻的字有ab,ac,ba,bb,bc,ca,cb,cc.所以h(2)=8.

设n≥

3,如果字中的第一个字母是a，那么第二个字母只能是b或c,其余的字母可以有h(n-2)种方式来选择，因此以a开头的字有2h(n-2)个.如果字中的第一个字母是b,那么这样的字有h(n-1)个，同理以c开头的字也有h(n-1)个，由加法法则得第33页，共63页，2023年，2月20日，星期二§6.2常系数线性齐次例3-2§6.2常系数线性齐次递推关系6.2.1相异特征根的解法例题例3、用字母a,b和c组成长度是n的字，如果要求没有两个a相邻，问这样的字有多少个？第34页，共63页，2023年，2月20日，星期二§6.2常系数线性齐次相同特征根定理6.5§6.2常系数线性齐次递推关系6.2.2相同特征根的解法定理6.5若q为上述递推关系的特征方程C(x)=0的一个m重特征根，则qn,nqn,…,nm-1qn为该递推关系的解。证明：令P(x)=xk-b1xk-1-b2xk-2-…-bk，

Pn(x)=xn-kP(x)

=xn-b1xn-1-b2xn-2-…-bkxn-k。由于q是P(x)=0的m重根，故q也是Pn(x)=0的m重根，由高等代数的知识知，q也是P'n(x)=0的(m-1)重根，那么q也是xP'n(x)=0的(m-1)重根，即q是方程nxn-b1(n-1)xn-1-b2(n-2)

xn-2-…-bk(n-k)xn-k=0的(m-1)重根。类似地，q是方程n2xn-b1(n-1)2xn-1-b2(n-2)2xn-2-…-bk(n-k)2xn-k=0的(m-2)重根。…一般地，对任意的i,i＜m,q是方程nixn-b1(n-1)ixn-1-b2(n-2)ixn-2-…-bk(n-k)i

xn-k=0的(m-i)重根。即有niqn-b1(n-1)iqn-1-b2(n-2)iqn-2-…-bk(n-k)iqn-k=0。分别令i=1,2,…,m-1，知nqn,n2qn,…,nm-1qn都是递推关系an=b1an-1+b2an-2+…+bkan-k的解，而qn是递推关系an=b1an-1+b2an-2+…+bkan-k的解在定理6.1中已经证明。故定理得证。第35页，共63页，2023年，2月20日，星期二§6.2常系数线性齐次相同特征根定理6.6-1§6.2常系数线性齐次递推关系6.2.2相同特征根的解法定理6.6若q1,q2,…,qt分别为上述递推关系的特征方程C(x)=0相异的m1,m2,…,mt重特征根，

为该递推关系的通解，其中cij由初始条件确定。第36页，共63页，2023年，2月20日，星期二§6.2常系数线性齐次相同特征根定理6.6-2§6.2常系数线性齐次递推关系5.2.2相同特征根的解法证明：由定理6.4知，表达式的右端每一项都是递推关系an=b1an-1+b2an-2+…+bkan-k的解。故an也是该递推关系的解。现只需证明该式满足递推关系式an=b1an-1+b2an-2+…+bkan-k的任意初值条件式a0=d0,a1=d1,…,

ak-1=dk-1所得的线性方程组有惟一解即可。将初值条件式a0=d0,a1=d1,…,ak-1=dk-1代入式(A)得到下列方程组：这个方程组的系数行列式是Vandermonde行列式的一个推广。其行列式之值为故方程组有惟一解。即cij(i=1,2,…,t;j=1,2,…,mi)是由初值惟一确定，定理得证。第37页，共63页，2023年，2月20日，星期二例4、求递归关系

§6.2常系数线性齐次例4§6.2常系数线性齐次递推关系6.2.2相同特征根的解法例题第38页，共63页，2023年，2月20日，星期二例5、求递归关系

§6.2常系数线性齐次例5§6.2常系数线性齐次递推关系6.2.2相同特征根的解法例题第39页，共63页，2023年，2月20日，星期二§6.2常系数线性齐次例6§6.2常系数线性齐次递推关系6.2.2相同特征根的解法例题例6、求递归关系第40页，共63页，2023年，2月20日，星期二§6.2常系数线性齐次例7§6.2常系数线性齐次递推关系5.2.2相同特征根的解法例题例7、计算n阶行列式的值：解：设具有以上形式的n阶行列式的值为an，按第一列展开有

显然a1=2，a2=3，于是可建立递推关系如下这个递推关系就是例3所求解的递推关系，故由例3的结果可知第41页，共63页，2023年，2月20日，星期二§6.2常系数线性齐次注意事项§6.2常系数线性齐次递推关系6.2.2相同特征根的解法注意：

建立递推关系关系时可考虑某个特定数值，如第一个、最后一个等；

k次递推关系需要k个初值，一般从a0开始（不妨假设）；结果需要验证（n=k+1,k+2,…）。

第42页，共63页，2023年，2月20日，星期二§6.3常系数线性非齐次定义§6.3常系数线性非齐次递推关系定义6.4

若{H(n)}中相邻k+1项满足:H(n)=b1H(n-1)+b2H(n-2)+…+bkH(n-k)+f(n)，(n≥k)称之为{H(n)}的k阶常系数线性非齐次递推关系。其中bi(i=1,2,…,k)是常数，且bk≠0，f(n)≠0

。

若f(n)=0，称

=b1H(n-1)+b2H(n-2)+…+bkH(n-k)为上述递推关系导出的常系数线性齐次递推关系。第43页，共63页，2023年，2月20日，星期二§6.3常系数线性非齐次定理6.7-1§6.3常系数线性非齐次递推关系定理6.7若

为an=b1an-1+b2an-2+…+bkan-k+f(n)

的一个特解，

为=b1an-1+b2an-2+…+bkan-k的一个通解，则an=

+

为原非齐次递推关系的通解。证明：由于

是非齐次递推关系式导出的齐次线性递推关系式即 的通解，故有又由于是非齐次递推关系的一个特解，故有将以上两式的两边分别相加得由上式可见

是式 的解。设非线性齐次递推关系为：an=b1an-1+b2an-2+…+bkan-k+f(n)第44页，共63页，2023年，2月20日，星期二§6.3常系数线性非齐次定理6.7-2§6.3常系数线性非齐次递推关系定理6.7若

为an=b1an-1+b2an-2+…+bkan-k+f(n)

的一个特解，

为=b1an-1+b2an-2+…+bkan-k的一个通解，则an=

+

为原非齐次递推关系的通解。现只需证明

能满足式 的任意初值条件式所导出的关于c1,c2,…,ck为未知数的线性方程组有惟一解即可。式中 。而这是显然的。因为该方程组的系数矩阵是一个Verdermonde矩阵，其行列式的值不为0。故定理得证。第45页，共63页，2023年，2月20日，星期二§6.3常系数线性非齐次定理6.7-3§6.3常系数线性非齐次递推关系定理6.7若

为an=b1an-1+b2an-2+…+bkan-k+f(n)

的一个特解，

为=b1an-1+b2an-2+…+bkan-k的一个通解，则an=

+

为原非齐次递推关系的通解。

注：定理6.7指出，若要求一个常系数线性非齐次递推关系式的通解，必须先求出这个递推关系所导出的常系数线性齐次递推关系的通解，然后再求这个递推关系式的一个特解，将其相加即可。然而，求一个非齐次线性递推关系的特解，通常没有系统的方法，但当函数f(n)是某些特殊形式时，才有一些规范的求法。第46页，共63页，2023年，2月20日，星期二

若f(n)为n的k次多项式，则

=A0nk+A1nk-1+…+Ak，其中A0,

A1,…,Ak为待定系数；若导出的常系数线性齐次递推关系特征根为1的m重根，则

=(A0nk+A1nk-1+…+Ak)nm。§6.3常系数线性非齐次特殊形式§6.3常系数线性非齐次递推关系

可针对f(n)的某些特定形式，转化为齐次性。

若f(n)为βn的形式，如β不是导出的常系数线性齐次递推关系特征根，则

=Aβn，其中A为待定系数；若β是导出的常系数线性齐次递推关系的k重特征根根，则

=(A0nk+A1nk-1+…+Ak)βn。第47页，共63页，2023年，2月20日，星期二§6.3常系数线性非齐次例1§6.3常系数线性非齐次递推关系例题例1、求递归关系

第48页，共63页，2023年，2月20日，星期二§6.3常系数线性非齐次例2-1§6.3常系数线性非齐次递推关系例题例2、“Hanoi塔”问题：n个大小不一的圆盘依半径的大小，从下而上的套在柱子A上。如图所示。现要求将所有的圆盘从柱子A上全部移到柱子C上，每次只允许从一根柱子上转移一个圆盘到另一根柱子上，且在转移过程中不允许出现大圆盘放到小圆盘上。试问至少要转移多少次才能将柱子上的n个圆盘全部转移到柱子C上去？第49页，共63页，2023年，2月20日，星期二§6.3常系数线性非齐次例2-2§6.3常系数线性非齐次递推关系例题解：用an表示从一根柱子上的n个圆盘全部转移到另一根柱子上的转移次数。显然，a1=1,a2=3。当n≥3时，要将柱子A上的n个圆盘转移到柱子C上，可以这样设想。先把柱子A上的n-1个圆盘转移到柱子B上，这需要转移an-1次；然后把柱子A上最后一个圆盘转移到柱子C上，显然这需要转移一次；最后再把柱子B上的n-1个圆盘转移到柱子C上，这也需要转移an-1次。经过这些步骤后，所有A上的n个圆盘就全部转移到柱子C上。由加法法则，这一共转移了2an-1+1次。于是可以建立如下带初值的递推关系

这就是我们需要的结果。第50页，共63页，2023年，2月20日，星期二§6.3常系数线性非齐次例2-3§6.3常系数线性非齐次递推关系例题例2、求递归关系（Hanoi塔）

第51页，共63页，2023年，2月20日，星期二§6.3常系数线性非齐次例3§6.3常系数线性非齐次递推关系例题例3、求递归关系

第52页，共63页，2023年，2月20日，星期二§6.3常系数线性非齐次例4§6.3常系数线性非齐次递推关系例题例4、求递归关系

an+2an-1+an-2=2n的通解。第53页，共63页，2023年，2月20日，星期二§6.3常系数线性非齐次例5§6.3常系数线性非齐次递推关系例题例5、求递归关系

an-4an-1+4an-2=2n的通解。第54页，共63页，2023年，2月20日，星期二§6.3常系数线性非齐次例6§6.3常系数线性非齐次递推关系例题例6、求Sn=1+2+3+…+n。第55页，共63页，2023年，2月20日，星期二§6.3常系数线性非齐次例7§6.3常系数线性非齐次递推关系例题例7、求Sn=12+22+32+…+n2。第56页，共63页，2023年，2月20日，星期二§6.3常系数线性非齐次例8§6.3常系数线性非齐次递推关系