《组合数学》课程结课作业
题目 系 号 递推关系的求解及其应用
控制与计算机工程学院
2018年5月
院 专业班级学生姓名学
摘要
递推关系作为数学的一种思维，充分的展现了生活中许多事物现象变化所遵循的规律。所有的事物都不是单一存在的，而是和某些东西相互依存的。比如在求解排列组合、数列中都会用到递推关系的思想与方法。本论文将围绕着递推思维及求解在数列、排列组合上的应用展开讨论。本论文阐述递推关系不是单一的个体，它与生成函数、线性关系、数列组合综合使用，并到达解决问题的思想。也说明学科之间是一个统一的整体。
关键词：递推关系;求解方法;递推思维;应用
1 绪论
递推关系几乎在所有的数学领域中都占据着重要的比例和广泛应用,在物理学上也有着深刻的影响，是数学运算中的一个强有力的工具。因此不管是在教学中还是生活中，都可能要用递推关系来解决所碰到的问题，或与其他学科相结合形成性学科的过程中用递推关系，比如递推关系可和数列、线性规划与矩阵相结合形成要实现这一目的新学科，把所学的知识串连在一起，形成一种新的思维。首要的关键是用递推方法来探究这一过程，搭建一桥梁。在此基础上才能用所学的递推理论和方法进行分析和应用，从而才能解决实际理论的问题，是我们所学的知识更上一个台阶。
通常情况下递推关系的求解比较困难，仅局限于使用递推关系的一些定义很多问题是不能解决的，并且所涉及的领域也很广。递推关
系的研究还可以追溯到斐波纳契关系： 它是比萨的数学家Leonardo在1202年给出的。在他所著的《Liber baci》一书中，讨论一个一年之内能有多少对兔子的问题，都用到了递推关系的思想。比如常见的线性递推数列，生成函数都是数学中的重要概念,也是解决数学问题的重要工具之一。本文主要介绍线性递推数列通项公式的求解方法及利用生成函数来求解递推关系，以及递推关系的推广。
2 线性递推关系
数列an必须有连续个k项满足xn?k?f(xn?k?1,xn?k?2,?,xn)，满足此式的数列则叫它为数列xn的一个递推关系式。由递推关系式及满足k个
初始值可以确定的一个数列xn叫做递推数列。因此，无论是牵涉到递推数列的证明题，解析题，还是需要建立递推关系式的综合题，那么解决递推数列的核心是求通项公式，也是最基本的步骤。
2.1 线性递推数列的相关认识
定义1 如果已知数列an的第1项（或前几项），且数列an的任意
1一项与它的前一项an?（或前几项）间的关系可以用一个式子来表示，
对于任意的自然数n，由递推关系an?k?f(an?k?1,an?k?2,?,an)所确定的数列an则叫做递推数列。
?1?例2.1 求解递推关系an?7an?1其中n?1且a2?98。
解：这是an?1?7an其中n?0且a2?98的另一种描述形式。于是解具有形式
an?a0(7n).因为
a2?98?a0(72),于是
a0?2,而且
an?2(7n),是唯
一解。
定义2 若数列an从第k项以后的任意一项都是其前k项的线性组合，即
an?k?r1an?k?1?r2an?k?2???rkan （1）
其中,n是任意的自然数，r1,r2,?,rk是常数，且rk?0那么称an为k阶的线性递归数列，（1）则叫an的递归方程。
?2?例2.2 公比为q的等比数列是一阶线性递归数列它的递归方程是
an?1?qann?1,2,3?,，q?0并且a1?1,a2?1.
例2.3 斐波那契数列（Fibonacci sequence）是二阶线性递归数列，它的递归方程为
an?2?an?1?an?)且a1?a2?1。 ，(n?1,2,3,4，2.2 线性递推数列通项公式的求解分类
我们探究线性递推数列目的就是要求出线性递推数列通项公式，然后用它来解决数学与生活中的一些问题，下面列出一些我们常见的求通项公式的方法:公式法、叠加法、叠乘法、待定系数法、迭代法、换元法、不动点法、转换法、数学归纳法等。
2.3 利用线性递推数列通项公式解决问题
递推关系在数学这个庞大的领域，有很多问题我们是无法解决的，那么需要我们运用所学的知识，把各个知识点串联起来形成一种新的思想，达到解决问题的目的。比如在解决递推关系时我们通常利用线性递推数列的通项公式来解决一些比较复杂的问题。接下来介绍几种常见的方法。
1）数学归纳法
所谓数学归纳法，令S(n)代表含有一次或多次出现变元n的一个开放数学语句，其中n表示一个整正数。
?如果S(1)为真；并且等式成立。
?若一旦S(k)为真，则有S(k?1)为真；那么对于所有n?N都有
?S(n)为真。
它常用在数学上证明与自然数N有关的命题的一种特殊方法，它主要用来探究与整正数有关的数学问题，在高中数学中常用来证明等式的成立和数列通向公式的成立，接下来就用它来证明此数列是成立的。
例2.4 已知数列?a?中，an1?0,a2?1,an?2?an?1?an(n?N?),求证：数
???a??项能被整除。 4t?1t?Nn列的第
证 (1)当t?1时，因为a3?a2?a1?1?0?1,a?a3?a2?1?1?2，得
a5?a4?a3?2?1?3，能被3整除。
（2）假设t?k(k?1)时。a4k?1能被3整除， 当t?k?1时，
a4(k?1)?1?a4k?5?a4k?3?a4k?4 ?(a4k?2?a4k?1)?(a4k?3?a4k?2) ?2a4k?2?a4k?1?(a4k?2?a4k?1) =3a4k?2?2a4k?1
由于a4k?1能被3整除，故a4(k?1)?1也能被3整除，由（1）和（2）可知道对于一切的
t?N?,a4k?1能被3整除。