当前位置:首页 >> 学科竞赛 >>

高中数学竞赛专题讲座---递归数列


递归数列讲座
知识与方法
递归(推)数列 数列的表示方法大致有两类:一是通项公式;另一是递推公式.数列 ?a n ? 的相邻几项的关系式简称为 递推式.数学竞赛中遇到有关数列的问题不仅是等差、等比数列,许多是递归数列的问题. 在解递归数列的问题时,有时需要根据递推关系求数列的通项,常常用到叠加法:
a n ? a 1 ? ? a 2 ? a 1 ?

? ? a 3 ? a 2 ? ? ? ? ? a n ? a n ? 1 ? ;适当时需要进行代数换元转化为常见数列的通项;有

时需要用到从特殊到一般的、归纳-猜想证明方法(常常用到数学归纳法) . 但也有一些题目并不要把数列的通项公式求出,而往往可根据题设所给的递推关系,得到新的、更明 显的递推关系.而这时就需要综合运用其他数学知识.

范例选讲
1. 已知 a 1 ? 1 , a 2 ? 5 , a n ? 1 ?
a n a n ?1 a n ? a n ?1 ? 1
2 2

,求数列 ?a n ? 的通项公式.

解:定义 F1 ? 1 , F 2 ? 0 , F n ? F n ? 1 ? F n ? 2 , n ? 3 , 4 , ? 由所给关系式得
1? 1 a n ?1
2

? 1 ? ?1 ? 2 ? an ?

?? 1 ??1 ? 2 ?? a n ?1 ??
Fn ?1

? ? 1 1 ? ? ,由归纳法可得 1 ? ? ? ?1 ? 2 2 ? ? an a1 ? ? ? ?
F Fn ?1 ? 2 Fn ?1

Fn

? 1 ?1 ? 2 ? a2 ?

? ? ? ?
1 2

Fn ?1

, n ? 1, 2 , ?

从而 1 ?

1 an
2

? 2

Fn

? 26 ? ? ? ? 25 ?

? 2 n 13

5

,因此 a n ? ?2

Fn ? 2

13

Fn ?1

5

? 2 Fn ? 1

?1

?

?

, n ? 1, 2 , ?

其中 F n ?

1

n?2 n?2 ?? ? ?1? 5 ? 1? 5 ? ? ? ?? ? , n ? 1, 2 , ? ?? ? ? ? ? 2 2 ? 5 ?? ? ? ? ? ?

注:本题是今年冬令营的一个测试题.在解题时层层推进,比较容易找到思路. 2. 证明数列 a n ?

?C
k ?0

n

2 k ?1 2 n ?1

?2

3k

都不能被 5 整除.

解: a 0 ? 1 , a 1 ? 11 ,又 2

3k

? 2

?

2 k ?1

?

3 2

?2

?

3 2

? 2

1 2

?2

2

?

2 k ?1



所以 a n ?

1 4

? 2 ? 2 ?

?

2 ?1

?

2 n ?1

? 2

?

2 ?1

?

2 n ?1

? ? 1 ? 2 ? ? ? 4 2 ?

?

2 ?1 9 ? 4

??

2

?

n

? 2

?

2 ?1 9 ? 4

??

2

?

n

? . ? ?

c 1 ? x 1 ? x 2 ? 18 , c 2 ? ? x 1 x 2 ? ? 49 ,所以 a n ? 18 a n ? 1 ? 49 a n ? 2 ? 3 a n ? 1 ? a n ? 2 ? mod 5 ? .
a 0 , a 1 , ? 除以 5 的余数为 1,1, 4 , 3 , 3 , 2 , 4 , 4 ,1, 2 , 2 , 3 ,1,1, ? 形成周期数列. a n ? 12 ? a n ? mod 5 ? ,又前 12 项中没

有被 5 整除的.∴命题得证. 注:这是一个逆向运用二阶递推的例子.已知数列的通项公式无法证明所要求证的.反过来通过将数 列的二阶递推关系找到,结合数列的周期性加以证明.

1

3. 数列 ?a n ? 满足 a 0 ? 1 , a 1 ? 5 , a n ?
2

2 a n ?1 ? 3 a n ?1 ? 9 2a n?2

2

?n

? 2 , 3 , ? ? ,证明 a n 都是整数.

解:由题意知 2 a n ? 2 a n ? 2 a n ? 1 ? 3 a n ? 1 ? 9 , 2 a n ? 1 a n ? 1 ? 2 a n ? 3 a n ? 9 .两式相减, 有 2 a n ? 1 a n ? 1 ? 2 a n ? 2 a n ? 2 a n ? 3 a n ? 2 a n ? 1 ? 3 a n ? 1 .整理,得
2 a n ?1 ? 2 a n ?1 ? 3 2a2 ? 2a0 ? 3
2 2

2

an a n ?1

?

2 a n ?1 ? 2 a n ?1 ? 3 2a n ? 2a n?2 ? 3

?n

? 2 ,3 , ? ? ,

将 n ? 1 个式子联乘得

an a1

?

,

又 a 2 ? 13 .所以 5 a n ? 2 a n ? 1 ? 2 a n ? 1 ? 3

(*) ,

可得 a n ? 1 ? 2 a n ? 3 ?

1 2

?a n

? 2 a n ? 1 ? 3 ? ,又 a 1 ? 2 a 0 ? 3 ? 0 ,所以 a n ? 2 a n ? 1 ? 3 ? 0

(1) ,

由此可推知 a n ? Z .又由(*)式推知 2 a n ? 1 ? a n ? 3 ? 2 ? 2 a n ? a n ? 1 ? 3 ? ,又 2 a 1 ? a 0 ? 3 ? 12 所以 2 a n ? a n ? 1 ? 3 ? 12 ? 2
n ?1

? 6 ? 2 .与(1)联立可解得 a n ? 2
n

n?2

? 3.

注:本题已知数列的一个递推关系是分式形式的,证明" a n 都是整数"有一定的难度.因此通过整理 变形得到数列的另一个递推公式: a n ? 2 a n ? 1 ? 3 ? 0 .这样证明起来变得容易了. 另外本题也可通过先求数列的前几项, 再根据结果猜测数列满足 a n ? 2 a n ? 1 ? 3 ? 0 ,再用数学归纳法 加以证明. 4. 求证:由 a 1 ? 3 , a 2 ? 5 及不等式 a n ? 1 a n ? 1 ? n ? a n ? 整数列 ?a n ? . 解: (1)先证明 a n ? F n ? 3 是满足条件的. ?F n ? 为斐波那契数列) a 1 ? 3 ? F 4 , a 1 ? 3 ? F 4 均成立. ( ∵ F 3 F1 ? F 2 ? 1 .当 k ? 3 时, F k ? 1 F k ? 11 ? F k ? ? F k ? F k ? 1 ? F k ? 1 ? F k ? F k ? 1 ? F k ? 2 ? ? ? ?F k F k ? 2 ? F k ? 1
2 2 2

a n ?1 a n ? 1 ? n

?n

? 2 , n ? N ? 可唯一确定正

?,

因 为 F n ? 1 F n ? 1 ? F n ? ? ? 1 ??F n F n ? 2 ? F n ? 1
2

2

? ? ? ? ? ? 1 ? ?F
n?2 2

3

F1 ? F 2

2

? ? ?? 1?

n?2

.若对所有 n ? N , ,

a n ? Fn?3 .

则验证 n ? k ? 2 时, a k ? 1 a k ? 1 ? a k ? F k ? 4 F k ? 2 ? F k ? 3 ? ? ? 1 ?
2
2

k ?1

所以 ? k ? ? 1 ? a k ? 1 a k ? 1 ? a k ? 1 ? k , a k ? 1 a k ? 1 ? n ? a k ? 中每个 a i ? F i ? 3 )

a k ?1 a k ? 1 ? n

.存在数列 ?a n ? . ?a n ? (使

(2)下证: ?a n ? 唯一确定.用数学归纳法证明 a n ? F n ? 3 且 a n ? 2 n ? 2
n ? 3 时,7 ?

(*) .
ak
2

23 3

?

a2 ? 2 a1

2

? a3 ?

a2 ? 2 a1

2

? 9 .事实上由已知不等式可推得

? k

a k ?1

? a k ?1 ?

ak

2

? k



a k ?1

2

因为 a 3 ? N ,所以 a 3 ? 8 ,同时 a 3 ? 2 ? 3 ? 2 .所以(*)成立.
n ? 4 时, 12 ?

61 5

?

a3 ? 3 a2

2

? a4 ?

a3 ? 3 a2

2

?

67 5

? 14 ,又 a 4 ? N ,所以 a 4 ? 13 .另外,

a 4 ? 2 ? 4 ? 2 ,所以(*)成立.

设 n ? k ? 1 及 n ? k ? k ? 4 ? 时(*)成立.则 n ? k ? 1 时,
ak
2

因为

? k

?

ak

2

? k

?

2k a k ?1

?

a k ?1 ak

a k ?1
2

? ak 2 ? k ak 2 ? k ? ? 中至多只有一个整数. ? 1 ,又 ? , ? a 2 ?k ? 1? ? 2 a k ?1 ? k ?1 ? ?

2k

a k ?1 ? N ,且

? k

a k ?1

? a k ?1 ?

ak

2

? k

a k ?1

,所以 a k ? 1 确定为 F k ? 4 .

且 a k ?1 ? F k ? 4 ? F k ? 3 ? F k ? 2 ? a k ? a k ?1 ? ?2 k ? 2 ? ? 2 k ? 2 ?k ? 1? ? 2 . 所以 n ? k ? 1 时, *) ( 成立. 因 此 ?a n ? 唯一确定.证毕. 综合(1) (2) ,可发现 a n ? F n ? 3 ?
1
n?3 n?3 ?? ? ?1? 5 ? 1? 5 ? ? ? ?? ?. ?? ? ? ? ? 2 2 ? 5 ?? ? ? ? ? ?

注:本题用同一法证明.在证明过程中用到了数学归纳法. 5. 数列 ?a n ? 定义如下: a 1 ? 0 , a 2 ? 1 , a n ?
1 2 na
n ?1

?

1

n? n ? n ? n ? 1 ?a n ? 2 ? ? ? 1 ? ? 1 ? ? 2 2? ?
n ?1 n

?n

? 3? .

1 2 n?2 试求 f n ? a n ? 2 C n a n ? 1 ? 3 C n a n ? 2 ? ? ? ? n ? 1 ?C n a 2 ? nC

a 1 的最简表达式.

解:由题意知 2 a n ? na n ? 1 ? n ? n ? 1 ?a n ? 2 ? ? ? 1 ?
2an n! ? a n ?1 ? a n?2 ? ?? 1?
n ?1

n ?1

? n ? 2 ? ,所以
1 2

?n ? 2 ?
n!

? n ? 1 ?!

? n ? 2 ?!

,令 b n ?

an n!

, b1 ? 0 , b 2 ?



则 2 b n ? b n ?1 ? b n ? 2 ? ? ? 1 ? 令 c n ? b n ? b n ?1 ? ? ? 1 ?
n
n

n ?1

?n ? 2 ?
n!

,所以 2 b n ? 2 b n ? 1 ? ? ? 1 ?
1 2

n

? ? 1 n ?1 ? ? ? b n ?1 ? b n ? 2 ? ? ? 1 ? , ? n ? 1 ?! ? n! ? ? 2
n

1 n!

,则 c n ? ?

c n ? 1 ,又 c 2 ? 0 ,所以 b n ? b n ? 1 ? ? ? 1 ?

1 n!

.
n ?1? k

另一方面, f n ?
n ?1

n?k ? ? n ? 1 ? k ?C n a k k ?1

?

? n ? 1 ? k ? ? n! ? ? n ? k ?! k ! a k .令 g n k ?1
n

?

fn n!

?

? ? n ? k ?!
k ?1

n

bk ,

g n ?1 ? g n ?

? ? n ? 1 ? k ?!
k ?1

n? 2?k

? bk ?

? ? n ? k ?!
k ?1

n

n ?1? k

? bk

3

?

? ? n ? 1 ? k ?!
k ?2

n ?1

n? 2?k

? bk ?

? ?n ? k
k ?2
n

n

n? 2?k ? 1 ?!

? b k ?1 ?

? ? n ? k ?! ? ?b
k ?2

n ?1

n? 2?k

k

? b k ?1 ?

?

? ?n ? k
k ?2

n ?1

n? 2?k ? 1 ?!

?

?? 1? k
k!
1

?

n ?1 ?? 1? k ?? 1? k ? ? ? ? n ? k ?! k ! k ?2 k ? 2 ? n ? k ? 1 ?! k !

?

? C ?? 1? n!
k n k ?2

1

n

k

?

?C ? n ? 1 ?!
k ?2

n ?1

k n ?1

?? 1? k
?

? ?

1 n!

?1 ? n ? ?
1 1

1

? n ? 1 ?!
1

?1 ? ? n ? 1 ?? ?
?

1

? n ? 1 ?!

?

1

? n ? 1 ?!

又 g 3 ? 2b2 ? b3 ?

4

? ? 2 ? n !? ? n ? 1 ? . ? ? ? ,所以 f n ? n ! ? g 3 ? ? ? 2! 3! n ! ? n ? 1 ?! ? 3 ?

1

注:这是 2000 年冬令营的测试题.由已知条件比较容易根据题设的条件想到将数列 ?a n ? 的递推关系 除以 n ! ,从而得到 ?b n ? 的递推关系: b n ? b n ? 1 ? ? ? 1 ?
g n ? 1 的关系.
2
n
n

1 n!

.同时也应将 f n 的两边同除以 n ! ,先求出 g n 与

6. 设数列 ?a n ? 的通项公式为 a n ?
b n ? 1 ? b n b n ?1 ? 2 ? b1

? ?? 1? 3

n

?n ?

N

? ;数列 ?b n ? 的定义如下: b 0
an

? 2 , b1 ?

5 2



?

2

?

?n ?

N ? .求证:对一切自然数 n ,都有 ?b n ? ? 2
an


2

证:我们证明更强的命题: b n ? 2

?2

? an

, n ? N ,易知数列 ?a n ? 的特征方程是 x

? x?2 ? 0,

所以 ?a n ? 的递推公式是 a n ? 2 ? a n ? 1 ? 2 a n , n ? N ,故 a n ? N .下面用数学归纳法证明加强的命题. (1) 当 n ? 1 时, a 1 ? 1 , b 1 ?
5 2
ak

? 2? 2

?1

,命题成立.
? 2
? ak

(2) 假设当 n ? k 时,命题成立,都有 b k ? 2
b k ? 1 ? b k b k ?1 ? 2 ? b1 ? 2

.当 n ? k ? 1 时,

?

2

?

?

ak

? 2

? ak

???2

a k ?1

? 2

? a k ?1

?

2

? 2 ? b1 ? 2

?

?

ak

? 2

? ak

??2

2 ak

? 2

?2 ak

?? b

1

? 2

a k ? 2 a k ?1

? 2

? ( a k ? 2 a k ?1 )

? 2

a k ? 2 a k ?1

? 2
k

? a k ? 2 a k ?1

? b1 ? 2
k

a k ?1

? 2

? a k ?1

? 2

a k ? 2 a k ?1

? 2

? a k ? 2 a k ?1

? b1 ,

而 a k ? 2 a k ?1 ?
2
a k ? 2 a k ?1

1 3

?2

k

? ?? 1? ? 2 ? 2
k

? 2 ? ?? 1?

? ? 1 ?3 ? ? ? 1 ? ? ? ? ? 1 ?
k ?1

k ?1

3

.所以 a k ? 2 a k ? 1 ? 1 ,

? 2

? a k ? 2 a k ?1

? 2? 2

?1

?

5 2

? b 1 .所以 b k ? 1 ? 2

a k ?1

? 2

? a k ?1

, 当 n ? k ? 1 时命题也成立.
an

由(1) (2)可知,加强命题成立.同时,又因为 a n ? N ,所以 ?b n ? ? 2 注:本题的关键在于加强命题 b n ? 2 可通过计算数列的前几项找到规律.
an

,原命题得证.

? 2

? an

, n ? N .然后用数学归纳法加以证明.在加强命题之前

7. 设 A ? ? a 1 , a 2 , ? , a m ? 是 由 m 个 数 a i ? ?0 ,1? , i ? 1, 2 , ? , m 组 成 的 数 组 . 定 义 运 算 S 如 下 :
4

S ? A ? ? ?b1 , b 2 , b 3 , b 4 , ? , b 2 m ? 1 , b 2 m ? , b b 其中当 a i ? 1 时, 2 i ? 1 ? 0 , 2 i ? 1 ; a i ? 0 时, 2 i ? 1 ? 1 , 2 i ? 0 , 当 b b

i ? 1, 2 , ? , m .用 S

n

? A ? 表示 S ? S ?? S ? A ?? ?? ( n 个 S ) A .取

? ?1 ? .问在 S

n

? A ? ? ?a 1 , a 2 , ? , a 2 ? 有多
n

少对由连续两项组成的数对 ? a i , a i ? 1 ? ,满足 a i ? a i ? 1 ? 0 ? 解: A ? ?1 ? 时, S ? A ? ? ?a 1 , a 2 , ? , a 2
n
n

? 中满足 a

i

? a i ? 1 ? 0 的数对 ? a i , a i ? 1 ? 的个数记为 f n ,满足
n

a i ? 0 , a i ? 1 ? 1 的数对 ? a i , a i ? 1 ? 的个数记为 g n .由题意知, S

? A ? 中数对 ? 0 , 0 ? 必由 S n ? 1 ? A ? 中的数对

?0 ,1 ? 经运算 S 而得到,而 S n ? 1 ? A ? 中的数对 ?0 ,1 ? 必由 S n ? 2 ? A ? 中的 1 或数对 ? 0 , 0 ? 经运算 S 而得到.由于
S
n?2

? A ? 是 2 n ? 2 数组,其中有一半的项(即 2 n ? 3 )为1 ,所以可得如下递归关系: f n
n?3

? g n ?1 ? 2

n?3

? f n?2 .
2
n ?1

∴当 n 为奇数时, f n ? 2

? f n?2 ? 2

n?3

? 2

n?5

? f n?4 ? ? ? 2

n?3

? 2

n?5

?? ? 2

2

? 2 ? f1 ?
0

?1

3

当 n 为偶数时, f n ? 2

n?3

? 2

n?5

? ? ? 2 ? f2 ?
1

2

n ?1

?1



3
n

n ∴ S ? ?1 ? ? 中,连续两项是 0 的数对有

1 3

?2

n ?1

? ?? 1?

? 个.

注:本题是个应用题,关键在于通过题意找到递归关系.

训练题
1. 设 ?a n ? 中的每一项都是正整数,并有 a 1 ? 2 , a 2 ? 7 , ? 二项开始,数列的各项都是奇数. 2. 已知 a 0 ? 0 , a 1 ? 1 , a n ? 2 a n ? 1 ? a n ? 2 ? n ? 1 ? .证明: 2 3. 已知数列 ?a n ? 满足: a 1 ? 1 , a 2 ? 2 ,且 a 2 n ? 1 ? 数列的通项公式. 4. 设 d 为正整数,求 x 1 ? x 2 ? ? x n ? 0 ? mod d ? , 0 ? x i ? d ?1 ? i ? n ? 的解 ? x 1 , x 2 , ? , x n ? 的个数.
k

1 2

? an ?

a n ?1

2

?

1 2

?n

? 3 ? .证明:自第

a n?2

an ? 2

k

n.

a 2 n ? a 2 n ?1 2

,a 2n? 2 ?

a 2 n ?1 a 2 n

?n

? 1, 2 , ? ? ,试求

5


相关文章:
高中数学竞赛专题讲座之数列
高中数学竞赛专题讲座数列_学科竞赛_高中教育_教育专区。高中数学竞赛专题讲座之一、选择题部分 1. (2006 年江苏)已知数列 ?an ? 的通项公式 an ? 2 数列 ...
高中数学竞赛专题讲座之数列
高中数学竞赛专题讲座数列高中数学竞赛专题讲座之一、选择题部分 1. (2006 年江苏)已知数列 ?an ? 的通项公式 an ? 2 数列 ? A? a1 ? B ? a2 2 ...
高中数学竞赛专题讲座——数列
高中数学竞赛专题讲座——数列_高三数学_数学_高中教育_教育专区。数学竞赛专题练习 高考资源网(www.ks5u.com) ,您身边的高考专家高中数学竞赛专题试题讲座——数列...
高中数学竞赛专题讲座---复数
高中数学竞赛专题讲座---复数_学科竞赛_高中教育_教育专区。复 数 专题一 复数与数列 复数数列的题目主要体现对复数运算的规律性的把握.例 1 设数列 z1 , z ...
高中数学竞赛辅导讲座-数列(一)
高中数学竞赛辅导讲座-数列(一)_学科竞赛_高中教育_教育专区。高中数学校本课程 竞赛课程 高中数学竞赛辅导讲座---数列一、学习目标 数列是高中数学的重要内容之一,...
高中数学竞赛专题讲座---数学归纳法在高考及竞赛中的应用
高中数学竞赛专题讲座---数学归纳法在高考及竞赛中的应用_学科竞赛_高中教育_...常 常运用数学归纳法来解题;在竞赛数学,数学归纳法更是在数列、组合等多方面...
高中数学竞赛辅导讲座-数列(二)
高中数学竞赛辅导讲座-数列(二)_学科竞赛_高中教育_教育专区。高中数学竞赛辅导讲座数列(二)【基础知识】 1、概念:① 、递归式:一个数列{an}中的第 n 项 ...
高中数学竞赛专题讲座——解析几何
高中数学竞赛专题讲座——解析几何一、选择题部分 1.(集训试题)过椭圆 C: x2...D ,如果线段 AB, BC , CD 的长按此顺序构成一个等差数列,求直线 l 的方程...
高中数学专题讲座 数列
高中数学专题讲座 数列_高三数学_数学_高中教育_教育专区。数列高三复习高中数学专题讲座 数列 数列,一直是安徽省高考中的重点内容之一。自实行自主命题以来,我省数学...
高中数学竞赛专题讲座之五《解析几何》各类
高中数学竞赛专题讲座之五: 《解析几何》各类竞赛试题选讲一、选择题 1. (04...P2 A 、…、 Pn A 成等差数列且公差 d >0,(1). 试将 d 表示为 n ...
更多相关标签:
高中数学竞赛专题讲座 | 初中数学竞赛专题讲座 | 递归数列 | 斐波那契数列递归算法 | 斐波那契数列递归 | fibonacci数列递归 | 斐波那契数列非递归 | 递归求斐波那契数列 |