谈递推法的几种应用方法.doc

谈递推法的几种应用方法
摘要:利用递推法关系解决数学问题的方法,成为递推法.
所谓递推关系,通常是指一个数列的第项与前面个项,(为正整数,)之间的关系:
( )
这里,是关于的元函数,通常称为递归函数;递推关系,也常称为阶递归方程.
关键字:递推法,组合数,列举累乘法,列举累加法,列举归纳猜想法,不动点法和换元法.
递推法的应用及证明步骤:
递推法也常用以处理正整数为状态函数的数学问题,诸如递归数列的通项问题,与数列有关的计算问题,证明问题,等等.
应用递推法解答数学问题,一般包括两个步骤:
第一步:,通过观察,试验,归纳,猜想等思维活动,寻求递推关系.
第二步:,求得所需的结论.
例1:计算两类带组合数和的幂和,.
解:[1]建立如下两个递推关系:
此后,有些读者仍沿着这个途径做相关问题的探讨,如文[2].
事实上,利用上面的递推公式,计算与时,我们需要用到与的表达式,计算量是非常大的.
本文给出两个简单的递推关系,利用他们计算出与时,我们反需用到与的表达式.
定理1:设为任意的自然数,为大于1的任意整数,则,
.
证明:对任意自然数,是显然的.
利用组合恒等式,我们有
由上式即推出.
注意到。由定理1,我们很容易计算出
.
定理2:设为任意自然数,为任意正整数,则
.
证明:利用组合恒等式,我们有


由上式即推出.
注意到,由定理2,我们不难计算出
,
.
例2:设,求的通项公式.
解:令,则递推关系式变为
.
变形后得
同理有
又由可得
把以上各式逐次向上迭代,有
消去,即得
注意到为方程的两根,有
,,.
所以,的通项是
上式表达式通常称为斐波那契数列通项的封闭型表达式,有称比内公式.
例3(插针问题):在一块木板上,插有甲,乙,丙三根针,已知其中一根针上,由小到大放着片大小不同的圆薄片,最大的一片在最底下;,且移动时需遵守下列规则:一次只能移动一片;?
思考方法:不妨设甲针放着由小到大的片圆薄片,现在要将这些薄片按题设规则移到乙针上去.
设移动片圆薄片至少需要次,那么当时,只要把甲针上的圆薄片直接移动乙针上就可以了,所以.
当时,需要先将甲针上较小的圆薄片移动到丙针上,再将甲针上较大的圆薄片移动到乙针上,,.
当时,为了叙述的方便,我们把甲针上的圆薄片编号,最小的为I号,中间的为II号,.
I号圆薄片由甲针移到乙针;
II号圆薄片由甲针移到丙针;
I号圆薄片由乙针移到丙针;
III号圆薄片由甲针移到乙针;
I号圆薄片由丙针移到甲针;
II号圆薄片由丙针移到乙针;
I号圆薄片由甲针移到乙针;
这样,.
通过考察时等特殊情形,我们不难发现,当甲针上有片圆薄片时,我们必须先把上面的片移到丙针上,再把最大的一片移到乙针上,,有递推关系
所以㈠
令,则
且㈠式变为㈡
㈡式表明,是首项为2,公