递推公式法

组合的计算方法

组合是数学中的一个重要概念，它是指从n个不同元素中取出m个元素的不同组合数。组合的计算方法有很多种，下面我们来介绍一些常用的方法。

1. 公式法

组合的计算公式为C(n,m)=n!/m!(n-m)!，其中n表示元素总数，m表示要取出的元素个数。这个公式可以直接计算出组合数，但是当n和m比较大时，计算量会非常大，不太适合手算。

2. 递推法

递推法是一种比较简单的计算组合数的方法。我们可以通过递推公式C(n,m)=C(n-1,m-1)+C(n-1,m)来计算组合数。这个公式的意思是，要么选第n个元素，然后从前n-1个元素中选m-1个元素，要么不选第n个元素，然后从前n-1个元素中选m个元素。这样就可以递推出所有的组合数。

3. 杨辉三角法

杨辉三角是一种非常有趣的数学工具，它可以用来计算组合数。我们可以把杨辉三角的每个数都看成一个组合数，然后通过递推公式C(n,m)=C(n-1,m-1)+C(n-1,m)来计算出所有的组合数。这种方法比较直观，也比较容易理解。

4. 位运算法

位运算法是一种比较高效的计算组合数的方法。我们可以用一个二进制数来表示一个组合，其中每一位表示一个元素是否被选中。例如，如果有4个元素，我们可以用0001表示第一个元素被选中，用0010表示第二个元素被选中，以此类推。这样，我们就可以用位运算来计算组合数，而且速度非常快。

组合的计算方法有很多种，每种方法都有其优缺点。在实际应用中，我们可以根据具体情况选择合适的方法来计算组合数。

递推问题

1.裴波那锲数列：1、1、2、3、5、8、13、21、34……第20项是多少？

2.有一楼梯共10级，如果规定每步只能跨上一级或2级，从地面登上第十级有多少种不同的走法？

3.有一串数排成一行，其中第一个是3，第二个是10，从第三个数开始，每个数恰好是前两个数的和，那么第1999个书被3除余几？

4.将一圆形制片用直线划分成大小不限的若干小纸片，如果要分成不少于50个小纸片，至少要用多少条线段。

5.给定第一个数是1，第二个数起，每个数都是前面所有数之和，问第100个数是什么？并求这100个数之和。

6. 1 2 3 4 2 3 4 5 3 4 5 6 4 5 6 7求第102个数是多少？

7.将自然数1，2，3，……按图排列，在2处拐第一个弯，在3处拐第二个弯…..问第20个拐弯发生在哪个数的地方？

7 → 8 →9 → 10

↑ ↓

6 1 → 2 11

↑ ↓ ↓

5← 4 ← 3 12

8.小兔子出生以后两个月就能生小兔，如果一对长大的兔子每月恰好生一对（一雌一雄）小兔子，那么一对初生的小兔经过一年共有多少对兔子

9.求12边形的内角和。

10.已知n棱柱有14个顶点，那么，它有多少条棱？

11.n条直线最多有多少个交点？

12.5个四边形最多把平面分成几部分？

13.10个小朋友围坐一圈做传手巾游戏，规定每个人得到手巾后只能往右边第一个或第二个人手中传，问手巾从小强手中传出，传递一圈后又回到小强手中，共有多少种不同传法？

14.将2/13写成一个循环小数，在这个循环小数的小数部分中截取连续的一段，使得这一段中的所有数字之和是2009，那么这一段数字中共有多少个数字

15.数列1、5、14、30、55、91……中第九个数是多少

1.某年的三月有五个星期三，四个星期二，这一年的十月一日是星期几？

2.有一列数1、3、4、7、11、18、29……这列数的第2009个数被6除的余数是多少？

求递推数列的通项公式的九种方法

利用递推数列求通项公式，在理论上和实践中均有较高的价值.自从二十世纪八十年代以来，这一直是全国高考和

高中数学联赛的热点之一.

一、作差求和法

例1在数列{na}中，3

1a,)1(1

1nnaa

nn，求通项公式na.解：原递推式可化为：111

1nnaa

nn则,21

11

12aa31

21

23aa

41

31

34aa，……，nnaa

nn1

11

1

逐项相加得：naa

n11

1.故na

n14.

二、作商求和法

例2设数列{na}是首项为1的正项数列，且0)1(

122

1nnnnaanaan（n=1,2,3…），则它的通项公式是

na=▁▁▁（2000年高考15题）

解：原递推式可化为：

)]()1[(

11nnnnaanaan

=0∵nnaa

1＞0，11



nn

aa

nn则,43,

32,

21

34

23

12aa

aa

aa……，nn

aa

nn1

1

逐项相乘得：naa

n1

1，即na=

n1

.

三、换元法

例3已知数列{na}，其中

913,

34

21aa，且当n≥3时，)(31

211nnnnaaaa，求通项公式na（1986

年高考文科第八题改编）.

解：设11nnnaab，原递推式可化为：

}{,

31

21nnnbbb

是一个等比数列，91

34

913

121aab，公比为31.故nnn

nbb)

31()

31(

91)

31(22

11

.故n

nnaa)

31(

1.由逐差法可得：n

na)

31(

21

23

.

例4已知数列{na}，其中2,1

21aa，且当n≥3时，1221nnnaaa，求通项公式na。解由

12

21nnnaaa得：1)()(

211nnnnaaaa，令11nnnaab，则上式为1

21nnbb，因此}{

nb

是一个等差数列，1121aab，公差为1.故nbn.。

二、数列的递推公式与通项公式、前n项和公式

一、知识点回顾：

1、递推公式定义：如果已知数列na的第1项（或前几项），且任一项na与它的前一项1na（或前几项）间的关系可以用一个公式来表示，那么这个公式就叫做这个数列的递推公式。

2、数列前n项和Sn与通项an的关系式：an=11sssnn 12nn。

在数列｛an｝中，前n 项和Sn 与通项公式an 的关系，是本讲内容一个重点，要认真掌握之。

注意：（1）用1nnnSSa求数列的通项公式时，你注意到此等式成立的条件了吗？（2n，当1n时，11Sa）；若a1 适合由an的表达式，则an 不必表达成分段形式，可化统一为一个式子。

（2）一般地当已知条件中含有na与nS的混合关系时，常需运用关系式1nnnSSa，先将已知条件转化为只含na或nS的关系式，然后再求解。

3、数列的通项的求法：

⑴公式法：①等差数列通项公式；②等比数列通项公式。

⑵已知nS（即12()naaafn）求na，用作差法：11,(1),(2)nnnSnaSSn。一般地当已知条件中含有na与nS的混合关系时，常需运用关系式1nnnSSa，先将已知条件转化为只含na或nS的关系式，然后再求解。

⑶已知12()naaafn求na，用作商法：(1),(1)(),(2)(1)nfnfnanfn。

⑷若1()nnaafn求na用累加法：11221()()()nnnnnaaaaaaa

1a(2)n。

⑸已知1()nnafna求na，用累乘法：121121nnnnnaaaaaaaa(2)n。

⑹已知递推关系求na，有时也可以用构造法（构造等差、等比数列）。特别地有

①形如1nnakab、1nnnakab（,kb为常数）的递推数列都可以用待定系数法转化为公比为k的等比数列后，再求na。