WORD格式可编辑

奥数专题之递推

递推法专题

递推法是组合数学中的一个重要解题方法，许多问题通过递推法来解决就显得精巧简捷．鉴于这一方法在学习中的应用越来越广泛，掌握和运用这种方法，就显得更加重要． 递推方法问题主要有两类：一是问题中有明显的递推关系，重点在于递推关系的应用；二是问题中没有明显的递推关系，需要对已有条件进行变形或改变问题的有关形式而建立递推关系，将问题转化为第一类问题。本文重点探索第二类问题。

通过建立、研究递推关系Sk+1=f(Sk)，使问题得以解决的方法称为递推方法。

例1 平面上有n条直线，它们中任意两条都不平行，且任意三条都不交于一点。这n条直线可以把平面分割成多少个部分？

请看一个引起普遍关注的关于世界末日的问题。

例2 有这样一段关于“世界末日”的传说。在印度北部的一个佛教的圣庙里，桌上的黄铜板上，放着三根宝石针，每根长约0.5米。据说印度教的主神梵天在创造世界时，在其中的一根针上，自上而下由小到大放了六十四片金片。每天二十四小时内，都有僧侣值班，按照以下的规律，不停地把这些金片在三根宝石针上移来移去：每次只准移动一片，且不论在那根针上，较小的金片只能放在较大的金片上。当所有六十四片金片都从梵天创造世界时所放的那根针上移到另一根针上时，世界的末日就要到来。这虽是一个传说，但却引起人们的重视，大家都想知道僧侣移动完毕这六十四片金片需要多少时间。也就是说，人类在这个世界上还可以生存多少时间。

例3 有10级台阶，小王从下向上走，若每次只能跨一级或两级，他走上去共有多少种不同的走法？

追问：10级的情况可以一一列出，台阶数比较多的情况，怎么办？ 提示：此即为斐波那契数列{ an}求通项的问题。

例4 同室4人各写一张贺年卡，先集中起来，然后每人从中拿一张别人送出的贺年卡，则4张贺年卡不同的分配方式共有( )

（A）6种 （B）9种 （C）11种 （D）23种 这里，我们引进一个概念：

设a1,a2,a3,…，an 是1，2，3，…，n的一个排列,如果ai?i,(i=1,2,…，n),则称这种排列为一个错位排列（也称为更列）。

专业知识 整理分享

WORD格式可编辑

更列问题也可以形象地理解为：将1，2，3，…，n看成已经排好对的n个人，重新站队时，各人都不站在原来的位置上。

例5 A、B二人拿两颗骰子做抛掷游戏，规则如下：若掷出的点数之和为3的倍数时，原掷骰子的人再继续掷；若掷出的点数不是3的倍数时就由对方接着掷，第一次由A开始掷，求第5次仍由A掷的概率。

例6 将一个四棱锥的每个顶点染上一种颜色，并使每一条棱的两端异色。如果只有5种颜色可供使用，那么不同的染色方法总数有多少种？

?ax?by?3?22?ax?by?755例7 设实数a,b,x,y满足方程组?3，求的值。 ax?by3?ax?by?16?ax4?by4?42?

例8 设an为下列自然数N的个数：N的各位数字之和为n，且每位数字只能是1，3或4. 求证a2n是一个完全平方数。

例9 过平面上两点A、B分别有m、n条直线，问这m+n条直线最多可以把平面分成多少部分？（m和n均为正整数）

专业知识 整理分享

WORD格式可编辑

递推数列求通项问题

一、 引例——斐波那契数列

假定一对兔子每隔一个月生一对一雌一雄的小兔子，每对小兔在两个月以后也开始生一对一雌一雄的小兔子，隔月一次。年初时兔房里有一对小兔（一雌一雄），问一年以后，兔房里有多少对兔子？

解：设第n个月初时兔房里有兔子fn对。易知

f1?1,f2?1,f3?2 ………(1)

第n?2个月初时兔房里的兔子可分为两部分：一部分是第n?1个月初时已经在兔房里的兔子，共有fn?1对，另一部分是第n?2个月初时新出生的小兔，共有fn对，于是

fn?2?fn?1?fn………………..(2)

这就是为广大中小学生所熟悉的斐波那契数列，它是递推数列的一个典型代表。 二、递推数列

（一）.递推数列的定义

斐波那契数列是递推数列的典型代表，其中(2)式称为递推式，也称递推关系，(1)式是初始条件，这二者是递推数列的必要构成条件。

一般地，我们把满足

fn?k?F(fn,fn?1,...,fn?k?1)……………………….. (6)

和初始值的数列{fn}称为k阶递推数列。当递推关系的形式为

fn?k?c1fn?k?1?c2fn?k?2?...?ckfn?F(n)…………………………(7)

时，数列{fn}称为k阶常系数线性递推数列，其中c1,c2,...,ck为常数，且ck?0。若函数

F(n)?0，则递推关系(7)所确定的数列{fn}称为k阶常系数齐次线性递推数列；否则，称

递推关系(7)所确定的数列{fn}为k阶常系数非齐次线性递推数列。因此，斐波那契数列是一个2阶常系数齐次线性递推数列。

递推数列是数列中的一个重要类型，数学竞赛中的数列问题多与递推数列尤其是其通项有关，且问题多以递推式、不等式等形式出现，本文主要探讨递推数列通项的求法。

（二）递推数列求通项的常用方法 常见的求递推数列通项的方法有：

（1）迭代法：对所给的递推式进行适当的变形，以便能连续使用下标较小的项代替某些下标较大的项，最后在一般项与初始项之间建立某种练习，从而求通项。

专业知识 整理分享