“九连环”中的数列递推关系
山西省原平市第一中学 任所怀
“九连环”是一个古老的中国智力游戏，对于它的结构和玩法在人教版普通高中课程标准实验教科书《数学5》第59页有详细介绍。为了让大家能更深入了了解这一游戏，我对这一游戏进行了进一步的深入剖析，写成这一篇文章与大家共享。
初见“九连环”可能会无从下手，按照我们从简单到复杂，从特殊到一般的归纳法思路，我们不妨先从“一连环”，“二连环”，“三连环”，„„入手，从中找出规律，从而得出“n 连环”的一般解法。
“一连环”解法简单，只需把圆环从上面的框架上取下，然后从框架中间穿过，就可把圆环从框架上解下。把这样的移动记为一次移动，则解“一连环”需要移动的次数为1次，记为f (1)=1。
“二连环”解法也简单，只需按照上面的移动规则，先把第2环解下，然后再解下第1环即可，则解“二连环”需要移动的次数为2次，记为f (2)=2。
“三连环”的解法为：先解下第1环，（记为：下1），再解下第3环（记为：下3），再套上第1环（记为：上1），接着解一个“二连环”，就可完成。所以解“三连环”需要移动的次数为f (3)=1+1+1+f (2)=5；
“四连环”的解法为：先解下前两环，（即下1，下2），再解下第4环（下
4），再套上前2环（上2，上1），接着解一个“三连环”，就可完成。所以解“四连环”需要移动的次数为f (4)=f (2)+1+f (2)+f (3)=2f (2)+f (3)+1=10；
由上归纳类比，可得
“n 连环”（n ≥3）的解法可分为四步：第一步：先解前n-2环，需要移动f (n -2) 次；第二步：解下第n 环，需要移动1次；第三步：套上前n-2环，解法就相当把解下过程倒过来，所以需要移动f (n -2) 次；第四步：解下前n-1环，需要移动的次数为f (n -1) 。于是解“n 连环”需要移动的次数为
f (n ) =f (n -2) +1+f (n -2) +f (n -1) =2f (n -2) +f (n -1) +1(n ≥3) ； 于是我们得到了一个数列的递推关系，即
n ≥3) 已知数列{f (n )}，其中f (1)=1, f (2)=2, f (n ) =2f (n -2) +f (n -1) +1,(，下
面我们共同探求，如何能求出该数列的通项公式？
解：由f (n ) =2f (n -2) +f (n -1) +1,(n ≥3) 得
-1) =2[f n (- f (n ) +f (n 2+) f n -(+1) ]n 1≥ ,
记a n =f (n +1) +f (n ) ，则a n =2a n -1+1(n ≥2) 且a 1=f (2)+f (1)=3 由a n =2a n -1+1(n ≥2) 得a n +1=2(a n -1+1)
于是数列{a n +1}为等比数列，公比为2，首项为a 1+1=4
所以a n +1=4⨯2n -1=2n +1，所以a n =2n +1-1。
即f (n +1) +f (n ) =2n +1-1 （1）
设f (n +1) +r 2n +1+p =(-1)[f (n ) +r 2n +p ]，则
f (n +1) +f (n ) =-3r 2n -2p （2）
21对比（1）（2）两式可知-3r =2且2p =1 于是r =-, p = 32
2121即f (n +1) -2n +1+=(-1)[f (n ) -2n +] 3232
21211于是有数列{f (n ) -2n +为等比数列，公比为-1，首项为f (1)-2+=。 32326
211所以f (n ) -2n +=(-1) n -1 326
121于是有f (n ) =(-1) n -1+2n -。 632
点评：有了这一结论，我们就可轻松计算出解“九连环”需要移动的次数为f (9)=341次。
另外在上面的研究过程中，我们两次构造数列来求数列的通项公式，这是由递推推导通项的重要方法。下面我们再来看一个例子：
（人教版普通高中课程标准实验教科书《数学5》第69页）
已知数列{a n }中，a 1=5, a 2=2, a n =2a n -1+3a n -2(n ≥3) ，对于这个数列的通项作一研究，能否写出它的通项公式？
解：由a n =2a n -1+3a n -2(n ≥3) 得
a n +a n 3) -1=3(a n -1+a n -2) (n ≥
设b n =a n +1+a n ，则上式可化为b n =3b n -1(n ≥2) ，且b 1=a 2+a 1=7 所以数列{b n }为等比数列，公比为3，且首项为7，所以b n =7⨯3n -1。 即 a n +1+a n =7⨯3n -1(n ∈N *) （3）
设a n +1+r ⨯3n =(-1)(a n +r ⨯3n -1) ，则a n +1+a n =-4r 3n -1 （4）
7对照（3）和（4）可知-4r =7，于是r =- 4
77即a n +1-3n =(-1)(a n -3n -1) 44
77713所以数列{a n -3n -1}为等比数列，公比为-1，首项为a 1-=5-=。 4444
713137所以a n -3n -1=(-1) n -1，于是a n =(-1) n -1+3n -1。 4444
点评：对于上面两个由递推推导通项的过程，你会发现它们的推导过程如出一辙。先构造一个数列把相邻三项的递推关系转化为相邻两项的递推关系，然后再构造数列把相邻两项的递推关系转化为通项公式。
举一反三，下面请读者自已动手，推导著名的数列斐波那契数列的通项公式; 已知数列{a n }，其中a 1=1, a 2=1, a n =a n -1+a n -2(n ≥3) ，求数列{a n }的通项公式。
答案为：a n =n n 。 作者简介：任所怀，山西省原平市第一中学一级教师。1996年毕业于山西师范大学数学系，在中学任教15年，一直从事高中数学教学与研究工作。在人教网发表论文6篇。
2006年度忻州市高中数学信息技术与学科课程整合教学能手；
2011年荣获忻州地区信息技术与课堂教学“十佳教师”称号；
2012年在参与“十一五”规划课题《提高课堂教学实效性的教学策略研究》工作中，被评为; 教育部课题研究先进工作者。
“九连环”中的数列递推关系
山西省原平市第一中学 任所怀
“九连环”是一个古老的中国智力游戏，对于它的结构和玩法在人教版普通高中课程标准实验教科书《数学5》第59页有详细介绍。为了让大家能更深入了了解这一游戏，我对这一游戏进行了进一步的深入剖析，写成这一篇文章与大家共享。
初见“九连环”可能会无从下手，按照我们从简单到复杂，从特殊到一般的归纳法思路，我们不妨先从“一连环”，“二连环”，“三连环”，„„入手，从中找出规律，从而得出“n 连环”的一般解法。
“一连环”解法简单，只需把圆环从上面的框架上取下，然后从框架中间穿过，就可把圆环从框架上解下。把这样的移动记为一次移动，则解“一连环”需要移动的次数为1次，记为f (1)=1。
“二连环”解法也简单，只需按照上面的移动规则，先把第2环解下，然后再解下第1环即可，则解“二连环”需要移动的次数为2次，记为f (2)=2。
“三连环”的解法为：先解下第1环，（记为：下1），再解下第3环（记为：下3），再套上第1环（记为：上1），接着解一个“二连环”，就可完成。所以解“三连环”需要移动的次数为f (3)=1+1+1+f (2)=5；
“四连环”的解法为：先解下前两环，（即下1，下2），再解下第4环（下
4），再套上前2环（上2，上1），接着解一个“三连环”，就可完成。所以解“四连环”需要移动的次数为f (4)=f (2)+1+f (2)+f (3)=2f (2)+f (3)+1=10；
由上归纳类比，可得
“n 连环”（n ≥3）的解法可分为四步：第一步：先解前n-2环，需要移动f (n -2) 次；第二步：解下第n 环，需要移动1次；第三步：套上前n-2环，解法就相当把解下过程倒过来，所以需要移动f (n -2) 次；第四步：解下前n-1环，需要移动的次数为f (n -1) 。于是解“n 连环”需要移动的次数为
f (n ) =f (n -2) +1+f (n -2) +f (n -1) =2f (n -2) +f (n -1) +1(n ≥3) ； 于是我们得到了一个数列的递推关系，即
n ≥3) 已知数列{f (n )}，其中f (1)=1, f (2)=2, f (n ) =2f (n -2) +f (n -1) +1,(，下
面我们共同探求，如何能求出该数列的通项公式？
解：由f (n ) =2f (n -2) +f (n -1) +1,(n ≥3) 得
-1) =2[f n (- f (n ) +f (n 2+) f n -(+1) ]n 1≥ ,
记a n =f (n +1) +f (n ) ，则a n =2a n -1+1(n ≥2) 且a 1=f (2)+f (1)=3 由a n =2a n -1+1(n ≥2) 得a n +1=2(a n -1+1)
于是数列{a n +1}为等比数列，公比为2，首项为a 1+1=4
所以a n +1=4⨯2n -1=2n +1，所以a n =2n +1-1。
即f (n +1) +f (n ) =2n +1-1 （1）
设f (n +1) +r 2n +1+p =(-1)[f (n ) +r 2n +p ]，则
f (n +1) +f (n ) =-3r 2n -2p （2）
21对比（1）（2）两式可知-3r =2且2p =1 于是r =-, p = 32
2121即f (n +1) -2n +1+=(-1)[f (n ) -2n +] 3232
21211于是有数列{f (n ) -2n +为等比数列，公比为-1，首项为f (1)-2+=。 32326
211所以f (n ) -2n +=(-1) n -1 326
121于是有f (n ) =(-1) n -1+2n -。 632
点评：有了这一结论，我们就可轻松计算出解“九连环”需要移动的次数为f (9)=341次。
另外在上面的研究过程中，我们两次构造数列来求数列的通项公式，这是由递推推导通项的重要方法。下面我们再来看一个例子：
（人教版普通高中课程标准实验教科书《数学5》第69页）
已知数列{a n }中，a 1=5, a 2=2, a n =2a n -1+3a n -2(n ≥3) ，对于这个数列的通项作一研究，能否写出它的通项公式？
解：由a n =2a n -1+3a n -2(n ≥3) 得
a n +a n 3) -1=3(a n -1+a n -2) (n ≥
设b n =a n +1+a n ，则上式可化为b n =3b n -1(n ≥2) ，且b 1=a 2+a 1=7 所以数列{b n }为等比数列，公比为3，且首项为7，所以b n =7⨯3n -1。 即 a n +1+a n =7⨯3n -1(n ∈N *) （3）
设a n +1+r ⨯3n =(-1)(a n +r ⨯3n -1) ，则a n +1+a n =-4r 3n -1 （4）
7对照（3）和（4）可知-4r =7，于是r =- 4
77即a n +1-3n =(-1)(a n -3n -1) 44
77713所以数列{a n -3n -1}为等比数列，公比为-1，首项为a 1-=5-=。 4444
713137所以a n -3n -1=(-1) n -1，于是a n =(-1) n -1+3n -1。 4444
点评：对于上面两个由递推推导通项的过程，你会发现它们的推导过程如出一辙。先构造一个数列把相邻三项的递推关系转化为相邻两项的递推关系，然后再构造数列把相邻两项的递推关系转化为通项公式。
举一反三，下面请读者自已动手，推导著名的数列斐波那契数列的通项公式; 已知数列{a n }，其中a 1=1, a 2=1, a n =a n -1+a n -2(n ≥3) ，求数列{a n }的通项公式。
答案为：a n =n n 。 作者简介：任所怀，山西省原平市第一中学一级教师。1996年毕业于山西师范大学数学系，在中学任教15年，一直从事高中数学教学与研究工作。在人教网发表论文6篇。
2006年度忻州市高中数学信息技术与学科课程整合教学能手；
2011年荣获忻州地区信息技术与课堂教学“十佳教师”称号；
2012年在参与“十一五”规划课题《提高课堂教学实效性的教学策略研究》工作中，被评为; 教育部课题研究先进工作者。