组合数学期中论文

  本文关键词：组合数学论文，由笔耕文化传播整理发布。

常系数递归数列的简单推广及其应用
摘 要：本文利用 k 阶级线性差分方程及常系数非齐次微分方程特解的设解规 律对 k 阶常系数线性递归数列进行简单推广到了 k 阶常系数非齐次线性递归数列， 并 进行了多类型的设解及其应用总结， 又引进矩阵理论增加了 k 阶线性递归数列通项公 式的求法，拓宽其应用范围。 关键词：递归数列；差分方程；设解；矩阵

本学期

， 在吴克俭老师的指导下我们进行了组合数学课程的学习探究，主要 的内容包括了排列与组合，二项式系数，调和数 Fibonacci 数和 Catalan 数，第二 类 Stirling 数和 Bell 数，第一类 Stirling 数，正整数的分拆，Bernoulli 数与 Euler 数，递归数列，形式幂级数等知识内容，而在本文当中，我选取了吴老师课堂上 没有深入探讨的关于递归数列的部分知识内容进行了简单的推广与应用， 即有对 常系数递归数列进行简单的推广及其应用。 第一部分：递归数列的知识回顾： 1、递归关系 2、齐次常系数线性递归关系：1）k 阶常系数齐次线性递归关系 2）k 阶齐 次线性递归关系 3、其他递归关系：1）非齐次常系数线性递归关系 2）卷积型递归关系 3） 双下标递归关系 第二部分：推广与应用 一、 对于常系数齐次线性递归关系的简单推广，即 k 阶常系数非齐次线性递 归关系。 为 了 方 便 ，我 们 可 以 设 k 阶 常 系数 非 齐 次线 性 递 归 数列 的 一 般形 式 为
p 0 a n ? k ? p 1 a n ? k ?1 ? ? ? p k a n ? f ( n ), ( p 0 ? 0 )

（1）其中

f (n)

，(n=O，1，2，...)

是一给定的数列， p 0 , p1 , ? , p k 是给定的常数。显然，我们可以得到与(1)所对应 的k阶常系数齐次线性递归数列是 p 0 a n ? k ? p1 a n ? k ?1 ? ? ? p k a n ? 0 , ( p 0 ? 0 ) （2）

由吴老师课堂笔记中 3、其他递归数列关系1）非齐次常系数线性递归关系 的部分内容可以了解到，(1)的通解等于(2)的通解加上(1)的一个特解。而对于 常系数齐次线性递归数列(2)的通解，我们可以用定理8.1至定理8.4中的特征方 程与特征根及待定系数的方法进行解答从而求出（2）的通解，或者通过母函数、 矩阵等方法也求出，不管怎样，求(1)的通解关键就在于求出(1)的一个特解。 若仅仅局限于特征方程与特征根及待定系数法是不能对一般的常系数非齐 次线性递归数列进行求解的，只有当
f (n)

是具有某些特殊形式的函数时，例如：

① f ( n ) 是n的t次多项式时，此时1便是常系数齐次线性递归数列（2）的 l 重特征

根 (l

? 0 ) ，那么（1）的特解可以通过待定系数的方法求出。② f ( n )

= a n 时，a便

是常系数齐次线性递归数列（2）的 l 重特征根 ( l

? 0 ) ，那么（1）的特解可以通

过待定系数法求出。 然而，在一般情况下，若没有上述的特殊条件，我们在进行常系数非齐次线 性递归数列的就显得有点困难，那么下面利用差分的概念将(1)转化为常系数非 齐次线性差分方程，从而得到(1)的特解。 首先，对于数列 a
n?0

? ?a n ?n

?

可看成是定义在非负整数集上的函数，而其与整数

之值便是 a n ，差分算子 ? 是一个在这些函数组成集合上的变换，定义其为 ；高阶差分算子 ? k ，(k=2，3，....)，定义其为 ? k a n ? ? ( ? k ?1 a n ) ，
? I

? a n ? a n ?1 ? a n

同时我们规定 ? 0

，记I是恒等算子，即有 Ia n

? an

，(n=0，1，2，...)。

其次，与差分算子有密切关系的是位移算子E，定义其为 Ea n ? a n ? 1 ；高阶位 移算子 E k ，(k=2，3，...)；定义其为 E k a n ? E ( E k ?1 a n ) ? a n ? k ，并规定 E 0
? I

。

显然可得，E ? ? ? I ， 从而有 E k ? ( ? ? I ) k ? C k0 ? C k1 ? ? ? ? C kk ? k 。 利用位移算子， (1)可记为 ( c 0 E k ? c1 E k ?1 ? ? ? c k ?1 E ? c k I ) a n ? f ( n )
?

（3）

其中 ? f ( n ) ?n 是一给定的数列， c 0 , c1 , ? , c k ?1 , c k 是给定的常数，如果有k个相 连的值为给出，成为边界条件，此时（3）将有唯一的解。然而，由位移算子与 差分算子的关系，(3)又可以进一步化为
( c ' 0 ? ? c '1 ?
k k ?1

? ? ? c 'k I ) a n ? f ( n )

（4） 其中 c ' 0 , c '1 , ? , c ' k ?1 , c ' k 是已知常数。

这样(1)就转化为常系数非齐次线性差分方程(4)。 对（4）两边去 l 次差分，得
( c '0 ? ( c '0 ?
k ?1

? c '1 ? ? ? ? c ' k ?1 ? ? c ' k ? ) a n ? ? f ( n )
k 2

k?2

? c '1 ?

k ?1

? ? ? c ' k ?1 ? ? c ' k ? ) a n ? ? f ( n )
3 2 2

............
( c '0 ? ( c '0 ?
k ? l ?1

? c '1 ?

k ?l?2

? ? ? c ' k ?1 ?

l ?1

)an ? ?
l

l ?1

f (n)
l

k ?l

? c '1 ?

k ? l ?1

? ? ? c ' k ?1 ?

l ?1

? c 'k ? ) a n ? ? f ( n )
l

若 ?l 有 解

f ( n ) 是一个与n无关的常量，不妨设 ? f ( n ) ? M ，则最后一个方程显然

? an ?
l

M c 'k

，

此

时

?

l ?1

an ? ? ? ?

k ? l ?1

an ? ?

k ?l

an ? 0

。

将

?

l ?1

an ? ? ? ?

k ? l ?1

an ? ?

k ?l

an ? 0

，? l a n ?

M c 'k

代入倒数第二个方程可求得 ? l ? 1 a n 。 依

次往上推，一直到(4)即可求得(1)的一个特解 a n? 。 通过上述利用k阶线性差分方程的方法进行常系数齐次线性递归数列的推广 过程，我们可以清楚地明白到，对于求(1)的特解，关键在于求差分方程(4)的特 解。 易得(4)的特解可求，而其最简单的情形就是当将令 ? l
f ( n ) 成为一个与n无关

的常量。 二、 对于利用差分方程进行对常系数非齐次线性递归数列进行求通解的方法 的常见应用类型。 由（一）中的推广过程中，我们若想保证 ? l
f ( n ) 是一个与n无关的常量，那么常

见的方式就是使得f(n)成为n次多项式 Pm ( n ) 或指数函数 Pm ( n ) e an 或余弦线性函 数 Pm ( n ) e an cos ? n 或正弦线性函数 Pm ( n ) e an sin ? n 或几个简单函数之和中一种情 况。又根据常系数非齐次线性方程的特解的设解规律，即“是什么设什么，含于 Y乘于x”的规律，指的是“f(n)是什么函数，方程的特解就设成什么函数；如果 上面所设的特解含于对应的齐次方程的通解Y(即所设特解可以完全或部分地与 对应的齐次方程的通解合并)，，则用x乘以前面所设的特解，作为新设特解；若仍 含于对应的齐次方程的通解，再乘以x，直到不含于对应的齐次方程的通解Y为 止。 ”我们可以知道，常系数非齐次线性微分方程的特解的规律，即可以引申到 常系数非齐次线性递归数列中去。 为了方便论证，我们将取二阶常系数非齐次线性递归数列为例。 首先，我们设定二阶常系数非齐次线性递归数列为
p 0 a n ? 2 ? p 1 a n ? 1 ? p 2 a n ? f ( n ), ( p 0 ? 0 )

（5）

由1.1的推导过程，我们可以很快得出对应于(5)的差分方程为
( p 0 E ? p1 E ? p 2 I ) a n ? f ( n ) 或 ( q 0 ? ? q 1 ? ? q 2 I ) a n ? f ( n )
2 2

（6）

其中 q 0 ? p 0 , q1 ? 2 p 0 ? p1 , q 2 ? p 0 ? p1 ? p 2
①
f ( n ) ? Pk ( n ) ，当 f ( n ) 为n次多项式时，其特解应为n次多项式。

设 p k ( n ) ? a 0 ? a1 n ? ? ? a k n k 是n的k次多项式。 由于 p k ( n ) 求k次差分后成为常 数，所以对（6）两边取k次差分后可求得 ? k a n ?
②
f ( n ) ? e Pk ( n )
an

ak k! q2

? 常量（ q 2 ? 0）

，当

f ( n ) 为指数函数时，其特解应为同类指数函数。

此时，作通项变换 a n ? e an b n ，代入（5）得

e

2a

p 0 b n ? 2 ? e p 1b n ? 1 ? p 2 b n ? Pk ( n )
a

进一步化为
( q 0 ? ? q 1 ? ? q 2 I ) b n ? Pk ( n )
2

（7）

其中， q o , q 1 , q 2 仍是常数。 （7）式已具有①的形式，故可求出数列 ?b n ? 的一
* 个特解 b n* ，从而由 a n ? e an b n 可得数列 ?a n ? 的一个特解 a n ? e an b n* 。

③

f ( n ) ? e Pk ( n ) cos ? n
an

或 f ( n ) ? e an Pk ( n ) sin ? n ，当

f (n)

为正、余弦的线

性函数，其特解应为设为同类正、余弦的线性函数。 构造新的差分方程
( q 0 ? ? q1 ? ? q 2 I ) a n ? e
2 (? ? ? i ) n

Pk ( n ) ? e

?n

Pk ( n ), ( ? ? ? ? ? i )

（8）

* 此时（8）具有②的形式，因此可求出数列 ?a n ? 的一个特解 a n

* 又Re a n 是差分方程

( q 0 ? ? q 1 ? ? q 2 I ) a n ? e Pk ( n ) cos ? n
2 an
* 的特解。Im a n 是差分方程

( q 0 ? ? q 1 ? ? q 2 I ) a n ? e Pk ( n ) sin ? n
2 an

的特解。
④ f ( n ) ? f 1 ( n ) ? f 2 ( n ) ，当 f ( n ) 为几个简单函数之和，其特解应为同类型

简单函数之和。 其中 f 1 ( n ) ? e ? n Q 1 ( n ), f 2 ( n ) ? e an Pk ( n ) cos ? n ( 或 e an Pk ( n ) sin ? n ) ，Q 1 ( n ), Pk ( n ) 分 别 是 n 的 l 次 和 k 次 多 项 式 。 由 p 0 a n ? 2 ? p1 a n ?1 ? p 2 a n ? f ( n ) ? f 1 ( n ) ? f 2 ( n ) (9) 可得两个常系数非齐次线性递归数列
p 0 a n ? 2 ? p1 a n ?1 ? p 2 a n ? f 1 ( n ) p 0 a n ? 2 ? p1 a n ?1 ? p 2 a n ? f 2 ( n )

（10） （11）

根据线性递归数列解的叠加原理知（9）的特解等于（10）与（11）的特解 之和。而（10）具有②的形式， （11）具有③的形式。从而（9）的特解可求。 从以上讨论可见，通过对
f (n)

特解的设解规律“是什么设什么，含于Y乘

于x”的规律引申到特解的求解规律，验证了我们前期的求解思路，则通过差分

方程的求解方法得到我们所求常系数非齐次线性递归数列需要的特解。 三、 k 阶齐次线性递归数列的简单推广，即利用矩阵判断 k 阶齐次线性递 对 归数列其敛散性，并求出其通项公式。 1）k 阶齐次递归数列敛散性的判断 设 k 阶齐次递归数列 ? f n ? 的递推公式为
f n ? k ? a 1 f n ? k ?1 ? a 2 f n ? k ? 2 ? ? ? ? ? a k ?1 f n ? 1 ? a k f n

，

（1）

其中 n=1,2,...,令
? f n?k ? ? a1 ? ? ? ? f n ? k ?1 ? ? 1 ?? ?, A ? ?? ? ? ? ? ? 0 ? f ? ? ? n ?1 ? a2 0 ? 0 ? ? ? ? a k ?1 0 ? 1 ak ? ? 0 ? , ?? ? 0 ? k?k ?

M

n?k

则
M
n?k

? AM

n ? k ?1

?? ? A M
n

k

。

（2）

由(2)式易得 定理 1

? f n ? 收敛 ?

lim M
n? ?

n?k

存在 ?

lim A
n? ?

n

存在.

若 f 1 ? f 2 ? ? ? f k ? 0 则 f n ? 0 .下设 f 1 , f 2 , ? , f k 不全为零. 定理 2 (1)设矩阵 A 有 k 个不同的特征根 ? 1 , ? 2 , ? , ? k , 则 lim f n 存在当且仅当
n? ?

? i ? 1, i ? 1, 2 , ? , k ;

（2）若矩阵 A 的特征根有重根 ? i ，则 lim f n 存在当且仅当 ? i
n? ?

? 1.

证 （1）若矩阵的 k 个不同的特征根 ? 1 , ? 2 , ? , ? k , 则存在可逆矩阵 T（T 的 第 i 列恰是 A 的对应于 ? i 的特征向量）使得
? ?1 ? ? A ?T? ? ? ?
n? ?

?2
?

? ? ? ?T ? ?k ? ?
n? ?

?1

,M

n?k

? a ? A M
n

k

? ?1 n ? ? ?T? ? ? ?
n? ?

?2

n

?

?k
n

n

? ? ? ?T ? ? ?

?1

M k,

所以 lim f n 存在 ? lim f n ? k 存在 ?
? ? i ? 1, i ? 1, 2 , ? , k ;

lim A
n? ?

n

存在 ?

lim ? i

存在

（2）若矩阵 A 的全部特征根为 ? 1 , ? 2 , ? , ? ? , 且 k 1 ? k 2 ? ? ? k ? ? k , 则

M

n?k

? J 1n ? ? ?T? ? ? ?

J

n 2

?

? ? ? ?T ? n J? ? ?

?1

M k,

??j ? ? 其中 J j ? ? ? ? ? ?
? ?n ? j ? ? ? ? ? ? ? ?
n a
k n

1

?j

1 ? ?

? ? ? ? 是 k j ? k j 级若当块.因 ? 1 ? ? ?j?
Cn j ? j ? ? C ?j
1 n n ?1 k ?1 n ? k j ?1

C n? j
1

n ?1

? ? ?

?

?

J

n j

? ?

?j
n

? ? ? ? , ? ? ? ? ?

lim

n? ?

? 0 （k

为大于 1 的自然数） ，于是 lim f n 存在 ? lim M n ? k 存在 ?
n? ? n? ?

lim A
n? ?

n

存

在? ? j

? 1，?

j

是重根.

2）递归数列通项式的求法 由矩阵 A 的表达式算出 A 的特征多项式
f ( ? ) ? ? E ? A ? ? ? a1 ?
k k ?1

? ? ? a k ?1 ? ? a k ,

求出上述定理 2 证明中的可逆矩阵 T，

即得 A n 的关于 n 的表达式，从而得出 ? f n ? 的通项公式。 参考文献： [1]邓 勇.常系数非齐次线性递归数列求特解的简易方法.达县师范高等专 科学校学报.2006(9） ：25-26. [2]喻德生 王敏.浅谈常系数非齐次线性方程特解的设解规律与教学.高等 数学研究.2004(5):41-44. [3]周立仁.k 阶线性递归数列的通项公式的矩阵求法.湖南理工学院院报 （自然科学报）.2011(9):24-25. [4]夏宗汇.生成函数与差分方程.数学传媒第二卷第四期.



更多相关文档:

组合数学论文

. . . . . 5 6 参考文献 1 主要内容摘要: 介绍了组合数学的概念、 起源...组合数学论文 10页 7下载券 组合数学论文 7页 1下载券 组合数学期中论文 6页...

组合数学课程论文

组合数学课程论文_理学_高等教育_教育专区。组合数学课程论文简论幻方 摘要:通过...期刊论文,信息技术与小学... 15页 免费 组合数学期中论文 6页 1下载券 ...

组合数学 课程论文

信息技术与数学的整合 4页 免费如要投诉违规内容,请到百度文库投诉中心;如要提出功能问题或意见建议,请点击此处进行反馈。 组合数学 课程论文 组合数学 课程论文组合...

组合数学论文

3.组合数学在生活中的应用举例组合数学是十分贴近于人们的生活的,因此组合问题在...组合数学期中论文 6页 1下载券 组合数学学习心得 2页 免费 组合数学课程论文 ...

组合数学论文

组合数学浅谈 组合数学浅谈组合数学是一门既古老又年轻的数学分支。我国古人在《...论文,信息技术与数学整合... 27页 免费 组合数学期中论文 6页 1下载券喜欢...

排列组合论文

排列组合论文_高三数学_数学_高中教育_教育专区。针对高中的排列组合问题,提出一个全新的角度来研究,从而给出快捷有效的解题方案和路径,可以称的上是排列组合版块的...

组合数学论文

组合数学论文_理学_高等教育_教育专区。组合数学抽屉世界——从小抽屉中看大组合 ——从小抽屉中看大组合 从小抽屉中看大 作者: 作者:厦门大学漳州校区 软件学院一...

数学专业毕业论文题目大全

数学专业毕业论文题目大全_教育学_高等教育_教育专区。假设检验与统计推断 简单平面...“中间点”的渐近性 中值定理逆问题及其内在联系 组合数学在生活中的应用 组合...

数学论文题目

数学论文题目_数学_小学教育_教育专区。A、 1、极限思想的产生和发展; 2、利用...《组合数学》的读书报告; 41、学习《离散数学》的读书报告; 42、论数学史的...

数学专业论文题目

《组合数学》的读书报告; 41、学习《离散数学》的读书报告; 42、论数学史的...应用中学数学知识解决某个实际问题,完成一篇数学建模论文 就当前我国高中数学知识...

更多相关标签:

  本文关键词：组合数学论文，由笔耕文化传播整理发布。