竞赛数学典型问题解决-数列与递推关系(新)讲诉

数列与递推关系第三节数列是定义在自然数集上的函数.数列的有关问题往往围绕通项与求和问题展开,数列问题涉及数列的通项、求和、数列的性质(如单调性、周期性、整除性、取值范围等等);另外,还常与函数迭代、集合分拆、初等数论等其它知识交织成综合题.由于其中不少问题可以转化归结为递推数列问题,因此这里主要介绍递推数列.一.递推数列的通项公式例1

已知求的表达式.解一

(辅助数列法)

令则是首项且公比为2的等比数列,故叠加得因此,解二

(特征方程法)

解特征方程得可设有由得解得所以解三

(母函数法)设的母函数为则三式相加,并注意到得即由于故因此,例2

设函数记则(2003年,“希望杯”高一第1试)解

(不动点法)令得不动点于是相比得即由及等比数列通项公式得所以例3

已知求表达式.分析对非齐次递推式,有时可采用齐次化方法简化递推关系,达到解决问题的目的.解∵∴两式相加,并整理得令上式说明的奇数项相等,偶数项也相等.而故即解特征方程得可设由得解得于是例4

已知数列满足则的值为

.(2004年全国高中)解

显然于是由易见及归纳法从而因此∴

“九连环”是中国先人创造的智力游戏.在2002年北京世界数学家大会期间,这个古老的游戏引起了与会数学家们的浓厚兴趣.该游戏依赖以下两个原则:(1)第1个环任何情况下,可下也可上;(2)如果某一环在上,而它前面所有环都在下,则这个环的后一个环可上也可下.记上“连环”总共需要步；当“连环”完成后接着完成“连环”个环需要步,由原则(2)知先卸下前再上第个环要1步,再装上前个环要步,所以,新增加的步骤数为注意第n个环可上也可下又因此“象为数学问题就是连环”问题抽[九连环]设数列前已知例5

项之和为求解

因为所以由等比数列通项公式,有整理得整理得由等比数列通项公式,有故注：

时,(次).若每秒完成１次,每天做12小时,则７亿多次需要90.8年.多么惊人的数字！和例6

函数定义在正整数集上,且满足则的值是.(2002年,上海市高中)解

依题意,有相减得故所以,二.利用递推数列的性质解题1.求值问题且解设实数满足求的值.(第6届美国数学邀请赛试题改编)例7

[好邻居]

记则为求注意到有相邻系数关系,设展开并比较系数得故所以解特征方程得(三重).可设其中由得解得所以故注：时即为第6届美国数学邀请赛试题.例8

已知若时的值都能被9整除,求南省高中)的最小值.(2002年湖解一

(先特殊后一般)计算知数列前几项为1,3,9,33,153,873,…,注意到是9的倍数,由递推关系知第5项后各项都是9的倍数,故的最小值为5．解二

(先求通项公式,再考察其规律)由条件得反复使用此式可得于是注意时而计算知前5项只有倍数,是9的故的最小值为5.例9

已知求证:对一切非零自然数总有为整数.(1963年,莫斯科)解∵∴两式相减,并整理得令上式说明为常数列.而故即至此,用数学归纳法不难证明结论成立.2.考察数列的性质例10

求证:满足的数列是整数数列.(2001年,英国(第2轮))重新整理递推关系,化为易应用的形式.分析证明由条件可得平方得①②∴削去常数项,得所以或由此可见,若是整数,则也是整数.由用数学归纳法不难证明结论成立.3.证明不等式例11求证:时,(1996年,世界城市数学竞赛)分析

用递推关系简化通项,最后说明设解

设则变形,得(构造辅助数列),故所以易见,时,得证.即4.组合计数

(1)青蛙每次跳时有2种不同的选择方法，解所以跳k-1

2k-1

种不同的方法．次共有又从A出发的2k-1种不同的跳法分为两类：例12[荷塘月色]池塘里有3张荷叶A、B、C，

一只青蛙在这3张荷叶上跳来跳去．若青蛙从A

开始，跳k(k≥2)次后又回到A,

不同跳法种数为并设所有可能的

(1)k>2时,与的递推关系式；间(2)求的值．求

(2)

(1)青蛙每次跳时有2种不同的选择方法，解所以跳k-1

2k-1

种不同的方法．次共有又从A出发的2k-1种不同的跳法分为两类：一类是第k-1次跳回到A的,有种；第k-1次跳回到B或C的,另一类是再跳一次可跳回到A,有种.所以易知k=3时有两种不同的跳法：

(2)

(1)解易知k=3时有两种不同的跳法：由(1)可得附：分组数列将数列按一定的规律分组,以组为单位的新数列称为原数列的分组数列(又叫分群数列).用数列的有关知识考察分组数列,是中学数学的一种新题型.例12

删去正整数数列1,2,3,…中的所有完全平方数,得到一个新数列,这个新数列的第2003项是()(A)2046(B)2047(C)2048(D)2049(2003年全国高中)例12删去正整数数列1,2,3,…中的所有完全平方数,得到一个新数列,这个新数列的第2003项是()(A)2046(B)2047(C)2048(D)2049(2003年全国高中)解

(利用平方数特征及选择支提供的信息解决)故待选项之前删去的最大完全平方数是2003+45=2048知选(C).由为第4组,对正偶数进行“理想配数”：为第1组,例13

为第2组,为第3组,…,那么2004为第

组的第个数.(2006年启东中学高一测试题)解

考察各组第1个数构成的数列记(差分法)其前n项和为于是由知,2004在第45组.则易知公差为2的等差数列,是以2为首项且设2004为第45组的第可k个数,解得k=12.2004=1982+(k-1)×2,所以,2004为第45组的第12个数.由通项公式得例14已知一个数列的各项是1或2,首项为1,且在第k个1和第k+1个1之间有个2,即1,2,1,2,2,1,2,2,2,2,1,2,2,2,2,2,2,2,2,1,…(1)求该;(2)是否存在正整数n,数列前1998项的和使前n项的和?若存在,求n的值;若不存在,请证明你的结论.(1998年,湖南省高中)分析第(1)小题先确定第1998项在第几组,再求和就不难了;第(2)小题先假设存在,再研究其性质.解

(1)将数列分组：第i个1和它后面个2这个数称为第i组.设第1998项在第k组,则k是满足的最小正整数,即估算：故k=11.将前11组的各组数首项1先换成2