递推方法及其应用.pdf

维普资讯 · 高中数学竞赛中常用的思想方法 · 递推方法及苴一’■辟 陕西省西安市铁一 中 刘康宁 通过建立递推关系解决问题的方法称之为递推 正整数数列{a}满足条件 ：对于任意正整数 ，从集合 方法．在某些与 自然数有关 的问题解决过程 中，如果 {n ，“，…，n}中不重复地任取若干个数，这些数之 能根据题设条件建立恰 当的递推关系式 ，往往能使问 间经过加减运算后所得的数 的绝对值为互不相 同的 题得到顺利地解决． 正整数 ，且这些正整数与 n ，n。，…，a 一起恰好是 1 利用递推方法解题的一般步骤是 ： 至 S 全体 自然数组成的集合，其 中S 为数列 {a}的 (1)用 a 表示所求 问题 的个数，并求 出初始值 前 项和． al、a2等； (1)求a1，a2的值 ； (2)建立n 与a 、a一等之间的递推关系式 ； (2)求数列 {a}的通项公式． (3)求解所得的递推数列 {a}． 讲解 ：(1)记 A 一 {1，2，3，…，S }，显然 n 一S 递推方法与数学归纳法 、无穷递降法有着密切的 一 1． 关系，主要用于解决计数问题． 对于 S2一a+n 一1+n2，有 A 一 {1，2，…，S2} 例 1 (2OO5年北方数学奥林 匹克邀请赛试题) 一 {1，a2，1+ “2，f1一a2f}一{1，2，3，4}． 已知 位数的各位数字只能取集合 {1，2，3，4，5}中的 故 1+n2—4，即a2—3． 元素 ，设含有数字 5且在 5的前面不含 3的 位数的 (2)由题设知，集合 {a，a ，…，a}按上述规则 ， 个数为厂()．求 厂()． 共产生 S 个正整数． 讲解 ：显然 ，．厂(1)一1． 而集合 {a ，a。，…，a，n }按上述规则产生 的 对于满足条件的 +1位数 的个数 厂(+1)的计 S 个正整数 中，除 1，2，…，S 个正整数外 ，还有 算 ，可分如下两种情况 ： a+ ，n++i，fa+l—if(i=1，2，… ，S)，共 2S+1 情形 1 当个位数字不是 5时，则前 位数 中一 个数． 于是，得 S+一S +(2S+1)一3S +1． 定含有数字5，它是满足条件的一个 位数，其个数为 ． 厂()．对于每一个这样的 位数 ，从 1，2，3，4中任取 上式可化为Sn4-1+丢：3(s+丢)． 一 个放在它 的最右端，可得到一个 +1位数．因此 ， 个位数字不是 5的 +1位数有 4f()个． 所以{Sn+专}是首项为S+1一3，公比为3 情形 2 当个位数字是 5时，由于在 5的前面不 的等 比数列，于是，有 s +寺 一昔 ×3一， 能含有 3，则前 位数的每一位数字均有 4种取法．因 此 ，个位数字是 5的 +1位数有 4个． 即S一÷×3一寺． 于是，得 f(n+1)一4f()+4(EN )． 当 ≥2时 ，a一S～S l一3一 ． 两边 同除以4，得 一 一1． 而 n一1也满足上式．