资源描述：
《_九连环_游戏所给出的递推数列研究》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。
1、第24卷第6期德州学院学报Vol.24,No.62008年12月JournalofDezhouUniversityDec.,2008“九连环”游戏所给出的递推数列研究刘耀斌(德州学院数学系,山东德州253023)摘要:九连环是我国从古至今广泛流传的一种益智游戏,其玩法多种多样,给出了根据“九连环”游戏的解决所得到的一类线性递推数列,并且给出其通项公式的三种证明方法.关键词:九连环;递推数列;特征多项式中图分类号:O15112文献标识码:A文章编号:100429444(2008)06200302031n+2n-1文献[1]给出了解开九连环的一个数学公
2、式:Sn=2-3+(-1),根据笔者玩九连环的做法,6提出不同的见解.首先了解九连环的构造:九连环的设计原理是数学上的拓扑学,它主要有九个圆环及框架组成,每个圆环都连有一个直杆,各直杆在后一个圆环内穿过,九个直杆的另一端用平板或者圆环相对固定,圆环在框架上可以解下或者套上,玩九连环就是要把这九个环全部从框架上解下来或者全部套在框架上(如图1a)).九连环的玩法比较复杂,但是不管怎么玩,无论解下环还是套上环都要遵循一定的规则.文献[1]中的通项公式是按照以下三个规则给出的:(1)每次只能解下或者套上一个环;(2)第一个环任何情况下,可自由上下(图1b
3、));(3)如果某一个环在上,而它前面所有的环都在下,那么这个环的后一个可上也可下(图1c)).在玩九连环的过程中发现,如果把游戏规则改变,可以得到另外一个计算解环的通项公式,而且这个公式简单易记,得到的步数也大为减少.图1九连环示意图把游戏规则改为以下三条:(1)每次可以解下或者套上一个或者两个环;(2)第一个环可自由上下以及前两个环可一起自由上下;(3)从第二个环开始,如果某一个环在上,而它前面所有的环都在下,那么这个环的后一个可上也可下.实际上在玩九连环的过程中,发现只有前两个环可以一起自由上下,其它的环每次只能上下一个,另外还要知道解下n个
4、环和套上n个环需要的步数是一样的.遵循这样的规则,给出解下全部的n个环需要的步数.设解下全部的n个环需要的步数为Sn,那么要解下第一个环只需要一步,即S1=1,要解下前两个环也只需要一步,即S2=1,而当nE3时,要全部解下这n个环,就需要先解下第n个环,而要解下第n个环就只能保留其前面的第n-1个环,也就是要先把前面的n-2个环全部解下,这需要Sn-2步,这时再需要一步就可以把第n个环解下,这时为了把第n-1个环解下,还需要把前面的n-2个环全部套上又需要Sn-2步,这时问题就变成了n-1个环的情形,要全部解下这n-1个环还需要Sn-1步.于是有
5、收稿日期:2008202215作者简介:刘耀斌(19682),男,山东平原人,讲师,硕士,主要从事代数学方面的研究.第6期刘耀斌“:九连环”游戏所给出的递推数列研究31Sn=Sn-2+1+Sn-2+Sn-1如在图1c)的状况下,就可以解下第6个环,然后要解下第5个环还需要把前面的4个环全部套上才可以.通过分析可以得到以下具有初值条件的递推关系S1=1,S2=1,Sn=Sn-1+2Sn-2+1,(nE3)(1)利用递推关系(1)式给出求Sn的通项公式的三种方法.[2]1应用归纳法求解由递推关系(1)式,可以知道S1=1,S2=1,S3=4,S4=7,
6、S5=16,S6=31于是猜测得到下列公式n-12n为奇数Sn=(2)n-12-1n为偶数下面用数学归纳法给出其证明1)显然n=1,2时,公式(2)式是成立的.2)假设对于小于n的自然数,公式(2)式都是成立的,那么对于n的情形,当n为奇数时,则有n-2n-3n-2n-2n-1Sn=Sn-1+2Sn-2+1=2-1+2×2+1=2+2=2当n为偶数时,则有n-2n-3n-2n-2n-1Sn=Sn-1+2Sn-2+1=2+2(2-1)+1=2+2-1=2-1即公式对于n也成立.因此对于所有的正整数n,都有n-12n为奇数Sn=n-12-1n为偶数2应
7、用等比数列求解由Sn=Sn-1+2Sn-2+1得到Sn+Sn-1+1=2(Sn-1+Sn-2+1),(nE3)因为S1=1,S2=1,于是数列{Sn+Sn-1+1}是以S2+S1=3为首项,2为公比的等比数列,于是得到n-2n-2Sn+Sn-1+1=(S2+S1+1)2=3×2,(nE3)即n-2n-1n-2Sn+Sn-1=3×2-1=2+2-1n-11n-21又得到Sn-2+=-(Sn-1-2+),(nE3)22n-113-2111因此数列{Sn-2+}是以S3-1-2+=1-2+=-为首项,以-1为公比的等比数列,于2222是又可以得到n-11
8、1n-2Sn-2+=(-)×(-1)22因此有n-111n-2n-111n-1n-11n-1Sn=2-+(-)×(-1)=
