数学竞赛中的代数问题3.doc

816449362516941816449362516941 看过之后记住看过之后记住2-3 数学竞赛中的代数问题（再续）数学竞赛中的代数问题（再续）五．递推数列五．递推数列1 1．基本内容（．基本内容（2 2 个定义、两条定理）个定义、两条定理）（（1 1）递推数列）递推数列定义定义 1 对于正整数对于正整数由递推关系由递推关系, ,n k12,,,n kn kn knaf aaa  L所确定的数列所确定的数列称为递推数列．称为递推数列． na（（2 2））递归数列递归数列、特征方程、特征方程定义定义 2 若数列若数列从第从第 项以后任一项都是其前项以后任一项都是其前 项项 nakk的线性组合，的线性组合，，， ①①1122n kn kn kknaaaa  L其中其中 为正整数，为正整数，为常数，为常数，，则称，则称为为 阶线阶线n12,,,k L0k nak性递归数列，称性递归数列，称①①为为的的递归方程递归方程，与递归方程相对应的，与递归方程相对应的 na代数方程代数方程②②12 121,kkk kxxxx L称为称为 阶线性递归数列阶线性递归数列的的特征方程特征方程．． k na例例 1 1 等差数列等差数列 ：：，是，是 2 2 阶线性递归数列；阶线性递归数列；212nnnaaa等比数列：等比数列：，是，是 1 1 阶线性递归数列阶线性递归数列.1nnaqa调和数列：调和数列：，不是线性递归数列，但是，不是线性递归数列，但是111n n naada递推数列递推数列.（（3 3）递归方程的求解（定理）递归方程的求解（定理 3535，定理，定理 3636））定理定理 1 若特征方程若特征方程②②有有 个相异根个相异根，则对应，则对应k12,,,kx xxL递归方程递归方程①①所确定的数列所确定的数列的通项公式为的通项公式为 na.1 122nnn nkkac xc xc xL其中其中是下列方程组的唯一解：是下列方程组的唯一解：12,,,kc ccL1 1221222 1 12221 122,,.kkkkkkk kkkc xc xc xac xc xc xac xc xc xa   LLLL定理定理 2 若特征方程若特征方程②②有有 重根重根 ，则对应递归方，则对应递归方①①所所k确定的数列确定的数列的通项公式为：的通项公式为： na1 12.kn nkacc nc nL其中其中是下列方程组的唯一解：是下列方程组的唯一解：12,,,kc ccL 12112 1221 12,22,.kk kkk kkcccacccackckca    LLLL2 2．数学竞赛中递推数列的主要类型．数学竞赛中递推数列的主要类型（（1 1）求数值）求数值（（2 2）求通项）求通项（（3 3）论证数列的性质）论证数列的性质（（4 4）数列应用题（如）数列应用题（如 p．．133,2-55））9 6IMO例例 2 （（2-55, p．．133）运动会连续开了）运动会连续开了 天天9 6IMOn（（）） ，一共发了，一共发了枚奖章．第一天发枚奖章．第一天发 1 枚以及剩下枚以及剩下1n m（（）枚的）枚的 ，第二天发，第二天发 2 枚以及发后剩下的枚以及发后剩下的 ，以后每，以后每1m1 71 7天均按此规律发奖章．在最后一天即第天均按此规律发奖章．在最后一天即第 天发了剩下的天发了剩下的 枚枚nn奖章，问运动会开了多少天，一共发了多少枚奖章？奖章，问运动会开了多少天，一共发了多少枚奖章？ 讲解讲解 ““运动会连续开了运动会连续开了 天（天（）） ，一共发了，一共发了枚奖枚奖n1n m章章””是题目为了叙述方便给我们设出的未知数，现在的问是题目为了叙述方便给我们设出的未知数，现在的问题是要解出在两个未知数．所以要去找联系两个未知数的题是要解出在两个未知数．所以要去找联系两个未知数的等量关系．等量关系．题目给出的、反映题目给出的、反映，， 之间联系的最本质关系是发奖之间联系的最本质关系是发奖mn方式：第方式：第 天发天发 枚以及发后剩下的枚以及发后剩下的 （昨天剩下、及发（昨天剩下、及发 枚枚kk1 7k后剩下）后剩下） ，这又涉及今天与昨天奖章的关系，所以，我们还，这又涉及今天与昨天奖章的关系，所以，我们还要设一个体现前后关系的未知数要设一个体现前后关系的未知数：运动会开了：运动会开了 天后还剩天后还剩kak下下枚奖章，它与中小学时设的常量未知数的不同之处在枚奖章，它与中小学时设的常量未知数的不同之处在ka于，于，是一个变量（关于是一个变量（关于 的函数）的函数） ，因此，题目最本质的，因此，题目最本质的kak等量关系是反映等量关系是反映的等量关系（递推方程）的等量关系（递推方程） ．首先有．首先有ka．．0,0nam a又，第又，第 天发了天发了枚奖章，还剩下枚奖章，还剩下k11 7kkak，，111 7kkakak得等量关系得等量关系．． ①①11116 77kkkkaakakak下面是解这个递推方程，基本思路是化归为等比数列下面是解这个递推方程，基本思路是化归为等比数列来处理．先视来处理．先视 为常量，找它的迭代不动点为常量，找它的迭代不动点k，， （（））6 7xxk 6 7f xxk得得 ，，6xk 把把①①化为了化为了．． ②②16667kkakak但但 为变量，且左、右两边要保持下标一致才能成为等为变量，且左、右两边要保持下标一致才能成为等k比数列，所以继续将比数列，所以继续将②②，， ③③1666167kkakak这又变成这又变成①①的形式，再求迭代不动点的形式，再求迭代不动点．．66 ,367xxx于是，于是，③③或说或说①①可变为可变为．． ④④1663661367kkakak这表明，这表明，是一个等比数列，有是一个等比数列，有636kkbak，，0636,636,7nbmbnq由等比数列的通项公式得由等比数列的通项公式得．．06636367n n nbb qnm得得 ．． ⑤⑤176366nnnm这就是这就是，， 所满足的等量关系或方程（不定方程）所满足的等量关系或方程（不定方程） ，，mn因为因为，， 为整数，所以为整数，所以为整数，但为整数，但，只有，只有mn176 6nnn6,71整除整除，由于，由于16n6n，， （（））1101 1161 16nn nnCCnn 1n 得得=0，代入，代入⑤⑤得得．．6n36m 说明说明 1：可以算出每天发的奖章：可以算出每天发的奖章第第 1 天：天：．．35167第第 2 天：天：．．366222467第第 3 天：天：．．36 12333367第第 4 天：天：．．36 18444267第第 5 天：天：．．3624555 167 第第 6 天：天： ．．6其实是每天其实是每天 6 枚枚.说明说明 2 古典名题背景：古典名题背景：例例 1-2 一位老人把积蓄的一位老人把积蓄的 m 枚金币分给枚金币分给 n 个儿女（个儿女（m,n是大于是大于 1 的正整数）的正整数） ，首先，给老大，首先，给老大 1 枚金币和剩下枚金币和剩下 ；然；然1 7 后，从余下枚的金币中给老二分后，从余下枚的金币中给老二分 2 枚金币和剩下枚金币和剩下 ；依此类；依此类1 7 推，第推，第 个孩子就分个孩子就分 枚金币和剩下的枚金币和剩下的 ,直到最小的孩子分直到最小的孩子分kk1 7到最后剩下的到最后剩下的 枚金币．问老人分给每个孩子的金币是否一枚金币．问老人分给每个孩子的金币是否一n样多？样多？说明说明 3 既有运算又有推理，是运算与论证的综合，还既有运算又有推理，是运算与论证的综合，还与数论交叉与数论交叉.例例 3 （斐波那契兔子问题）兔子出生以后两个月就能（斐波那契兔子问题）兔子出生以后两个月就能 生小兔子，每次不多不少恰好生一对（一雌一雄）生小兔子，每次不多不少恰好生一对（一雌一雄） ．假如养．假如养 了初生的小兔一对，试问：一年以后共可有多少对兔子了初生的小兔一对，试问：一年以后共可有多少对兔子 （如果生下的小兔都不死的话）（如果生下的小兔都不死的话） ．． 解解 更一般地，设第更一般地，设第 个月有个月有对兔子，因为第对兔子，因为第 1 个月个月nna 只有原有的只有原有的 1 对小兔子，故对小兔子，故；到第；到第 2 个月小兔子长大但个月小兔子长大但11a  还不会生育，仍是一对兔子，故还不会生育，仍是一对兔子，故．．21a 对对，易知第，易知第 个月的兔子数个月的兔子数可由两部分兔子组成，可由两部分兔子组成，3n nna 一部分是上一个月转来的兔子数一部分是上一个月转来的兔子数，另一部分是当月新出，另一部分是当月新出1na 生的小兔子，它的数量是前一个月（上生的小兔子，它的数量是前一个月（上 2 个月）的兔子数个月）的兔子数 ，故有，故有2na（（）） ①①12,nnnaaa2n  其中其中，，．．11a 21a  这个式子叫做斐波那契递推方程．它反映了一个状态这个式子叫做斐波那契递推方程．它反映了一个状态 与前面两个状态与前面两个状态，，的联系．由此可以求得：的联系．由此可以求得：，，na1na2na11a  ，，，，，，，，21a 342,3aa565,8aa7813,21,aa91034,55aa ，即年后有兔子，即年后有兔子 144 对．对．111289,144aa 通过递推关系通过递推关系①①可以解出可以解出．由．由①①有有na（递推方程（递推方程））11,nnnaaa210xx 即即 1115151515,2222nnnaaa 变形并递推（也可以直接用等比数列的通项公式）变形并递推（也可以直接用等比数列的通项公式）11212121151515 2221515 221515 2215,2nnnnnnnnaaaaaaaa     L同理同理 11515.22nnnaa消去消去得得1na．． ②②11515 225nnna另解另解 ，，121515 22nnnacc121215151223535122cccc，，121 5cc.11515 225nnna说明说明 2009 年全国高考数学陕西卷（理科）年全国高考数学陕西卷（理科）22 题（题（12分）：分）： 已知数列已知数列满足满足，，．．}nx11 2x＝* 11,1n nxnNx。