递推方法

2024-07-03

递推方法（共11篇）

递推方法篇1

递推数列求通项问题, 主要是运用转化思想化归为两类基本数列:等差数列和等比数列.如果问题涉及的数列不能转化为基本数列, 可通过对递推式的拼, 拆, 凑等变形, 寻求规律, 然后通过构造辅助数列等手段解决问题.

常见题型和方法有:

an+1=an+f (n) 型, 此类问题可利用公式an=a1+ (a2-a1) + (a3-a2) +…+ (an-an-1) 求其通项

例2已知数列{an}中, a1=3且nan+1= (n+2) an+n, 求an.

解两边同时除以n (n+1) (n+2) , 得

an+1=anf (n) 型, 此类型可利用公式求通项

例3已知数列{an}中, a1=1, 且an+1=2Nan (n≥2) , 求an.

3.an+1=pan+rqn型

例4 在数列{an}中, a1=1, an+1=2an+2n, 求an.

解 ∵an+1=2an+2n,

则数列{bn}为等差数列, 且b1=1, d=1, bn=n,

∴an=n·2n-1.

4.Sn=f (an) 型

例5 已知数列{bn}中, b1=1, Sn为数列{bn}的前n项和, 且满足求bn.

解由已知, 当n≥2时,

又Sn=b1+b2+b3+…+bn,

又S1=b1=1,

∴数列是以1为首项, 公差为的等差数列.

∴当n≥2时,

5.an+1=can+d型 (c≠0, d≠0, c, d为常数)

例6 已知数列{an}中, 且an+1=3an-1, 求an.

解法1 (阶差法)

(1) - (2) , 得an+1-an=3 (an-an-1) ,

∴{an+1-an}是以a2-a1=2为首项, 3为公比的等比数列.

将 (1) 代入 (3) , 得

解法2 (待定系数法)

由an+1=3an-1, 则有

6.an+2=p1an+1+p2an型

此类型用常规方法解决很难, 可两次应用待定系数法.下面是特征方程法:

如果特征方程x2=p1x+p2有两个不等根α, β, 则an+2=p1an+1+p2an的通项为an=λ1αn+λ2βn, 如果有两个等根α, 则an=λ1αn+λ2nαn, 其中λ1, λ2由已知可求得.

例7已知数列{an}中, a1=1, a2=4, an+2=5an+1-6an, 求an.

解因为特征方程x2=5x-6的根为2和3,

∴an=λ12n+λ23n.

又a1=1, a2=4, 则有

递推数列是一类广泛而复杂的数列问题, 在近几年全国各地的高考题中屡见不鲜, 是一类考查思维能力的好题.只要掌握其规律, 很多问题将迎刃而解.

递推数列初探篇2

1.累加法

例1已知数列{an},a1=1，n∈N*，an=an-1+1n2-n（n≥2，n∈N*），求通项公式an．

解：∵ an-an-1=1n2-n=1n(n-1)=1n-1-1n（n≥2）．

∴ an=a1+(a2-a1)+(a3-a2)+…+(an-an-1)

=1+1-12+12-13+…+1n-1-1n=2-1n．

评注：形如an=an-1+f(n)的递推数列，其中数列{f(n)}可求和，则可通过恒等式an=a1+(a2-a1)+(a2-a2)+…+(an-an-1)累加求通项．

2. 累乘法

例2已知数列{an}，a1=1，an＞0，(n+1)a2n-na2n-1+anan-1=0（n≥2，n∈N*），求数列an通项公式．解：∵ na2n-(n-1)a2n-1+anan-1=0，∴ ［nan-(n-1)an-1］(an+an-1)=0．

∵ an＞0，∴ an+an-1＞0，∴ nan-(n-1)an-1=0，∴ anan-1=n-1n．

∴ an=a1•a2a1•a3a2…anan-1=1•12•23…n-1n=1n．

评注：形如anan-1=f(n)的递推数列，其中数列{f(n)}可求积，则可通过恒等式an=a1•a2a1•a3a2…anan-1累乘求通项．

3.构造法

① 待定系数法

例3已知数列{an}，a1=1，an=3an-1+2（n≥2，n∈N*），求数列{an}通项公式．

解：∵ an=3an-1+2，令an+x=3(an+x)，

∴ x=1，∴ an+1=3(an+1)，∴ {an+1}为等比数列，首项为a1+1=2，公比q=3，∴ an+1=2•3n-1，∴ an=2•3n-1-1．

评注：形如an=qan-1+d（q，d为常数，q≠0，q≠1），可通过待定系数法凑配成an+dq-1=qan+dq-1，构造等比数列an+dq-1求通项，特别的，当q=1时{an}为等差数列．

② 取倒数法

例4已知f(x)=2x2x+1，数列an=f(an-1)(n≥2，n∈N*)，且a1=f(1)，求数列{an}的通项公式．

解：∵ an=f(an-1)，∴ an=2an-12an-1+1，∴ 1an=2an-1+12an-1，∴ 1an=12an-1+1，令1an+x=121an-1+x，∴ x=-2，∴ 1an-2是等比数列，首项为1a1-2=1f(2)-2=-12，公比q=12，∴ 1an-2=1a1-2•qn-1=-12•12n-1，∴ 1an=-2-n+2，∴ an=2n2n+1-1．

评注：形如an=can-1an-1+d（c,d为常数，c≠d,c≠0,d≠0）的递推数列，可通过取倒数1an=dc•1an-1+1c，再通过待定系数法构造等比数列求通项，特别的，当c=d时数列1an为等差数列．

③ 取对数法

例5已知数列{an}，a1=10，an=10a2n-1，(n≥2，n∈N*)，an＞0求数列{an}的通项公式．

解：∵ an=10a2n-1，∴ lgan=2lgan-1+1，令(lgan+x)=2(lgan-1+x)，∴ x=1，∴ {lgan+1}为等比数列，首项为lga1+1=2，公比q=2，∴ lgan+1=2n，∴ an=102n-1．

评注：形如an=can-1p（c，p为常数，an＞0，c＞0,p＞0，p≠1），两边取对数lgan=plgan-1+lgc，再通过待定系数法构造等比数列求通项，当p=1时，数列{lgan}为等差数列．

④ 换元法

例6已知数列{an}，a1=1，an=2an-1+3n（n≥2，n∈N*），求数列{an}的通项公式．

解：∵ an=2an-1+3n，∴ an3n=2an-13n+1，

∴ an3n=23•an-13n-1+1，令bn=an3n，bn+x=23（bn-1+x），

∴ x=-3，∴ {bn-3}为等比数列，首项为b1-3=-83，公比q=23，∴ bn-3=an3n-3=-83•23n-1=-2n+23n，∴ an=3n+1-2n+2．

评注：形如an=qan-1+dn（q，d为常数，q≠0，d≠0，q≠1，d≠1，d≠q）的递推数列，可变换成andn=qd•an-1dn-1+1，令bn=andn，转化为bn=qdbn-1+1，通过待定系数法求通项．特别的，q=d时，bn为等差数列．

4.数学归纳法

例7已知数列{an}满足a1=1，且4an+1-anan+1+2an=9（n∈N*），求数列{an}的通项公式．

解：∵ a1=1，4an+1-anan+1+2an=9(n∈N*)，∴ a2=73，a3=135，a4=197．

猜想： an=1+6(n-1)2n-1．

下证：当n=1时，猜想成立．当n=k（k∈N*）时，猜想成立，即ak=1+6(k-1)2k-1则当n=k+1时，有ak+1=2-1ak-4=2-16k-52k-1-4=6k+12k+1=1+6［(k+1)-1］2(k+1)-1．

∴ 当n=k+1时也成立．综上可知an=1+6（n-1）2n-1成立．

评注：数学归纳法求通项公式遵循“归纳，猜想，证明”，三步曲．

从数列的递推关系式求出数列通项的过程中，有时需要构造一个全新的数列，有时需要从特殊归纳到一般结论，这实际上是一次思维的整理，和创新的过程．

递推数列求通项的几种常见方法篇3

一、型如an+1=an+f (n) 可用迭加法求通项

例1已知数列满足, 求通项an.

解:由递推公式得an-an-1=2 (n-1)

an-an-2=2 (n-2) ……

a3-a2=2·2

a2-a1=2·1

以上 (n-1) 个等式相加得

又a1=1∴an=1+n (n-1) =n2-n+1

注:一般地, f (n) 可分解成等差数列、等比数列求和 (或常用的数列和公式, 如12+22+32+…+n2=n (n+1) (2n+1) 等) 。

二、型如an+1=f (n) an (f (n) 不是常数) 可用迭乘法求通相

解:当n≥2时, an=Sn-Sn-1=n2an- (n-1) 2an-1

以上 (n-1) 个等式相乘得:

注:一般地, 数列an+1=f (n) an, f (n) 是分式的形式, 且是n的关系式。

三、型如an+1=pan+f (n) (p为常数且p≠0, p≠1可用转化为等比数列等

(1) f (n) =q (q为常数) , 可转化为an+1+k=p (an+k) , 得{an+k}是以a1+k为首项, P为公比的等差数列。

例3已知数列{an}中, a1=1, an+1=3an+2, 求通项an.

解:设an+1+k=3 (an+k) , 得an+1=3an+2k与an+1=3an+2比较得k=1∴原递推式可变为an+1+1=3 (an+1)

∴{an+1}是一个以a1+1=2为首项, 以3为公比的等比数列

∴a1+1=2·3n-1∴an=2·3n-1-1

注:一般地, 对递推关系式an+1=pan+q (p、q为常数, 且p≠0, p≠1) , 可等价地改写成

则成等比数列, 实际上, 这里的是特征方程x=px+q的根。

(2) f (n) 为等比数列, 如f (n) =qn (q为常数) , 两边同除以qn, 得:

注:一般地, 这类数列是递推数列的重点与难点内容, 要理解掌握。

注:一般地, 设α、β是递推关系的 (p、q、r、s为常数) 的特征方程 (p≠0、rq-ps≠0) 的两根。 (1) 若α=β可令则{bn}成等比数列; (2) 可令则{bn}成等差数列。

五、型如an+2=pan+1+qan (p、q为常数) 变形为an+2-αan+1=β (an+1-αan) 可转化为等比数列

解法略。

递推方法篇4

严老师的课堂最大的亮点就是师生互动如行云流水，如春风拂面，如鱼翔浅底，轻松活泼，而又不乏智慧的光芒，学生参与热情高，学习氛围好。这节课的教学重点就是让学生通过对例题及其变式的思考，体会“利用递推关系求数列的通项公式”的方法 (如定义法、累加法、待定系数法等)和化归思想。其实，此类问题既是数列教学中的难点问题，也是江苏高考的.热点问题。总体而言，在严老师的引导下，学生基本达成了教学目标，高一学生能做到这一点已经难能可贵了。笔者建议，是不是可以突破例题和练习的界限，进行如下的教学设计：

在数列中，已知，其前项和为，根据下列条件，分别求数列的通项公式。

数列递推思想的应用篇5

在归纳推理中应用

例1 如图，一白珠下面挂一黑珠，每一黑珠下挂一黑珠与一白珠，则第11行黑珠的个数为________.

[…第一行][…第二行][…第三行][…第四行][…第五行][…第六行]

解析设第行黑珠的个数为个，则，则第行黑珠的个数为等于第行黑珠的个数为与第行白珠的个数之和，由于第行白珠的个数即为第行中黑珠个数，故有.

点拨此题通过运用递推思想得到一个递推关系，正是著名的“斐波拉契数列”. 在一些数列归纳通项的推理中，利用递推思想，构建递推公式，使有限拓展到无限，由特殊变成一般规律，这是解决此类问题常见思路与方法，同理这也体现了合理推理的精髓所在.

构建“递推公式”，巧证数列不等式

例2 已知函数设满足，，数列满足，.证明：.

解析本题可不用数学归纳法证，直接应用递推公式证更加简洁，简证如下.

时，显然成立.

时，由题意得，，且，

综上所述，.

点拨此题由两边结构中都有，故联想递推关系，类比“已知等比数列递推关系求通项方法”，适当放缩使问题得以解决.在中学阶段某些压轴数列不等式的证明中，常利用此递推思想结合放缩法进行转化与化归.

构建递推数列模型，求无限往复数学问题

例3 设是正三角形的边上的任意一点，从向边引垂线，垂足为，再从向边引垂线，垂足为；再从向边引垂线，垂足为，再从重复以上操作，得当时，能否无限趋近于某一点？若能，请指出这一点的位置；若不能，请说明理由.

解析此题为典型的无限往复问题，其本质为求极限点，看似很复杂，我们先不妨构建递推关系，如图.

不妨设，正三角形边长设为1，

故当时，无限趋近于的距的等分处.

点拨在无限反复问题中，过程较繁琐. 这类问题通过构建相邻过程的二元数量的递推关系，由“理不断”的无限反复变成相对固定的数列递推模型来解决，问题解答顺利而流畅！

用递推思想解决一些浓度混合应用题

例4 现有流量均为300m3/s的两条河流汇合于某处后，不断混合，它们的含沙量分别为2kg/m3和0.2kg/m3. 假设从汇合处开始，沿岸设有若干观测点，两股水流在流经相邻两个观测点的过程中，其混合效果相当于两股水流在1秒钟内交换100m3的水量，即从股流入股100m3水，经混合后，又从股流入股100m3的水量并混合.问：从第个观测开始，两股河水的含沙量之差小于0.01kg/m3（不考虑泥沙沉淀）.

解析设第个观测点两股水流含沙量分别为kg/m3与kg/m3，

则，

且 =①，

=②.

①-②得， =.

故从第9个观测点开始，两股水流含沙量之差小于0.01kg/m3.

点拨在浓度混合问题中，不断地“混合”，使问题变得较为“混沌”，此类问题可通过构建交叉递推数列，再利用递推数列的解法去化“混沌”为“清晰”，使思路明了而清晰.

递推思想在计数方面的应用

例5 将一个圆分成个扇形部分，依次为，每一扇形分别用种不同颜色中任一种涂色，其中相邻部分涂不同颜色，则不同的染色方案有多少种？

解析设有种涂色方案，则表示用这种不同的颜色按同样的规则填涂类似的块区域.

显然，先涂区域有种；再涂区域，不能与区域同色，有种，再涂区域，不能与区域同色，也有种，按照这种方式一直涂到区域.

我们不妨只考虑区域与区域不同色，则共有种.

但其中包含区域与区域同色的情形，当区域与区域同色时，可将此二区域视为一个区域来涂色，这种情形下的涂色方法恰为于是就得出了一个递推关系：

上式可改写成：.

即数列（）是一个公比为-1的等比数列.

综上所述，

点拨在一些复杂的计数问题中，运用数列递推思维组建递推关系可起到“疱丁解牛”的作用，使问题清晰而明了.需要说明的是，此题涉及到计数中的染色问题，通过递归关系得到一个一般化的通式，此式在染色问题中应用相当广泛.

递推思想在某些概率问题方面的应用

例6 已知，正四面体中，一枚棋子从一个顶点出发，选任何一条棱移动的概率都相等，每次移动前，掷一次骰子，出现偶数点，则棋子原地不动；若出现奇数点，则移动. 一枚棋子从点开始移动到点，求掷次骰子，才到达点的概率.

解析设掷次骰子时到达点的概率为，由题意知，在点选择任一条棱的概率均为，向前移动一次概率为，则分二类：（1）掷第次时不在点，则到达必顺掷奇数点且从该点移动到，则其概率为；（2）掷第次时在点，则第次必顺掷偶数点且不移动，则其概率为.

故由（1）（2）知，

则有，

故数列构成首项为

公比为的等比数列.

则有，即即掷次骰子，才到达点的概率.

点拨此题位置不确定，掷点奇偶不定，关系复杂，利用递推思想是最有郊的方法，通过构建递推数列，问题迎刃而解.一般存在相互依存关系问题的概率都可运用递推思路去解决.

综上所述，灵活运用递推思维，构造递推数列解决某些问题，可以起到化繁为简、化抽象为具体的奇效. 其运用过程中，融高度的逻辑性于一体，是数学中化归思想的深度体现，因此在平时高考复习中，应引起我们足够的重视.

利用递推关系求数列通项的方法篇6

一、形如an+1=an+f (n) 的递推式

利用叠加法.

a2=a1+f (1) ,

a3=a2+f (2) ,

…

an=an-1+f (n-1) ,

以上各式相加得

$a_{n} = a_{1} + \sum_{i = 1}^{n - 1} f (i) (n \geq 2$ 且n∈N*) .

【例1】已知数列{an}满足 $a_{1} = \frac{1}{2} ‚ a_{n} = a_{n - 1} + \frac{1}{n^{2} - 1} (n \geq 2)$ , 求数列{an}的通项公式.

二、形如an+1=f (n) an的递推式

因为 $\frac{a_{n + 1}}{a_{n}} = f (n)$ , 所以

$\begin{array}{l} a_{n} = \frac{a_{n}}{a_{n - 1}} \cdot \frac{a_{n - 1}}{a_{n - 2}} \dots \frac{a_{2}}{a_{1}} \cdot a_{1} \\ = a_{1} f (1) f (2) \dots f (n - 1) \\ (n \geq 2 \end{array}$ 且n∈N*) .

【例2】数列{an}满足nan+1=2 (a1+a2+…+an) , n∈N*且a1=1, 求数列{an}的通项公式.

三、形如an+1=pan+q (p≠1) 的递推式

方法1:an+1=pan+q,

an=pan-1+q (n≥2) ,

∴an+1-an=p (an-an-1) ,

∴{an-an-1}是以 (a2-a1) 为首项, p为公比的等比数列,

$\begin{array}{l} ∴ a_{n} - a_{n - 1} = (a_{2} - a_{1}) \cdot p^{n - 1} ‚ \\ ∴ a_{n} = a_{1} + \frac{(a_{2} - a_{1}) (1 - p_{n - 1})}{1 - p} \\ (n \geq 2 \end{array}$ 且n∈N*) .

方法2:令an+1+m=p (an+m) ,

则an+1=pan+pm-m, 与原式比较, 得

$m = \frac{q}{p - 1}$ ,

所以 $a_{n + 1} + \frac{q}{p - 1} = p (a_{n} + \frac{q}{p - 1})$ ,

即 ${a_{n + 1} + \frac{q}{p - 1}}$ 为公比是q的等比数列.

【例3】已知数列{an}:3, 5, 7, 9, …, 2n+1, …另作一数列{bn}, 使b1=a1, 且当n≥2时, bn=abn-1, 求数列{bn}的通项公式.

四、形如an+1=pa $_{n}^{q}$ (p>0, an>0) 的递推式

两边取对数, 得lgan+1=qlgan+lgp, 令bn=lgan, 则bn+1=qbn+lgp, 仿“类型三”可求解.

【例4】数列{an}中, 设an>0, a1=1, 且an·a $_{n + 1}^{2}$ =36, 求数列{an}的通项公式.

五、形如an+1=pan+f (n) (p≠1) 的递推式

变形得 $\frac{a_{n + 1}}{p^{n + 1}} = \frac{a_{n}}{p^{n}} + \frac{f (n)}{p^{n + 1}}$ , 令 $b_{n} = \frac{a_{n}}{p^{n}}$ , 得 $b_{n + 1} = b_{n} + \frac{f (n)}{p^{n + 1}}$ , 仿“类型一”, 用叠加法可求解.

【例5】数列{an}的前n项和为Sn, 且满足a1=1, an+1=2Sn+n2-n+1, 求数列{an}的通项公式.

六、形如an+1=f (n) an+g (n) 的递推式

设辅助数列{h (n) }, 使 $f (n) = \frac{h (n)}{h (n + 1)}$ , 则 $a_{n + 1} = \frac{h (n)}{h (n + 1)} a_{n} + g (n)$ ,

即an+1h (n+1) =anh (n) +g (n) h (n+1) .

令bn=anh (n) ,

则bn+1=bn+g (n) h (n+1) ,

仿“类型一”可解决.

【例6】已知数列{an}满足nan+1= (n+2) an+n, 且a1=1, 求数列{an}的通项公式.

自然数幂和的一种递推方法篇7

如此一个倒三角排列, 可以对其进行简单的研究, 发现其中的一些规律. 易知第二行空缺的数列为1p-1, 第三行空缺的数列为1p-1 2p-1, 第四行空缺的数列为1p-1 2p-1 3p-1, 第五行空缺的数列为1p-1 2p-1 3p-1 4p-1, 第六行空缺的数列为1p-12p-13p-14p-15p-1, 第七行空缺的数列为1p-1 2p-1 3p-1 4p-15p-16p-1, 第八行空缺的数为1p-1 2p-1 3p-1 4p-1 5p-1 6p-1 7p-1.如此类推可得到如下正三角排列:

假设的求和公式存在, 且为p+1次多项式.那么其中每一行数的和可以通过代入sxp-1求得, 这里x=1~ (n-1) .

设, 且假定的表达式都已知.可得上述正三角形行列式中, 第一行的和为, 第二行的和为, 第三行的和为, 依次类推, 最后一行和为.易知上述倒直角三角行列式中, 第一行中所有数之和为, 第二行中所有数之和为, 第三行中所有数之和为, 依次类推最后一行的所有数之和为.则得到.其中

将以上各式竖向相加则可得到

其中, 依次类推, 代入上式

整理可得到以下结果:

其中a1, a2, a3, …, ap-1为自然数幂和公式的相应各次幂项的系数.为幂≤p - 2 次的自然数的幂之和.

摘要：研究自然数幂和的目的不仅仅是要找到公式, 更应该深入了解数字间的巧妙联系, 能够找到公式的实质, 利用排列组合的知识固然简便, 但是理解起来相对抽象.笔者探讨这个问题的时候, 利用sn1snp-1的表达式, 通过建立行列式发现了一个求snp的递推关系式.即把若干次幂的自然数按照数列的形式排列, 每一行出现的数字呈等差排列, 成倒三角的形式, 仔细观察可以发现自然数p次幂和与自然数p-1次幂的关系.通过对假设的证明, 得到一个相对简洁的递推公式, 并用该公式推导出了p≤9次幂的自然数幂和.

递推方法篇8

类型1、递推公式为an+1-an=f (n) 型。

(1) 若f (n) 为常数, 即:an+1-an=d, 此时数列为等差数列, 则an=a1+ (n-1) d;

类型3、递推公式为an+1+an=f (n) 型。

(1) 若an+1+an=d (d为常数) , 则数列{an}为“等和数列”, 它是一个周期数列, 周期为2, 其通项分奇数项和偶数项来讨论;

(2) 若f (n) 为n的函数 (非常数) 时, 可通过构造转化为an+1-an=f (n) 型, 通过累加来求出通项;或用逐差法 (两式相减) 得an+1-an-1=f (n) -f (n-1) , 分奇偶项来分求通项。

类型4、递推公式为an+1·an=f (n) 型。

(1) 若an+1·an=p (p为常数) , 则数列{an}为“等积数列”, 它是一个周期数列, 周期为2, 其通项分奇数项和偶数项来讨论;

(2) 若f (n) 为n的函数 (非常数) 时, 可通过逐差法得an·an-1=f (n-1) , 两式相除后, 分奇偶项来分求通项。

类型5、形如an+1=can+d, (c≠0, 其中a1=a) 型。

(1) 若c=1时, 数列{an}为等差数列; (2) 若d=0时, 数列{an}为等比数列;

(3) 若c≠1?d≠0时, 数列{an}为线性递推数列, 其通项可通过待定系数法构造辅助数列来求。此时数列{an}为线性递推数列。运用待定系数法, 构造新数列, 把原递推公式转化为:an+1-t=c (an-t) , 其中再利用换元法转化为等比数列求解。

类型6、形如an+1=pan+f (n) 型。

(1) 若f (n) =kn+b (其中k, b是常数, 且k≠0) , 则依递推式写出an=pan-1+f (n-1) 用相减法构造新数列, 运用类型5的方法来进行解决。

(2) 若f (n) =qn (其中q是常数, 且n≠0, 1。

(2) 当p2+4q≥0时, 用待定系数法, 可设an+2-xan+1=y (an+1-xan) , 而后构造新数列, 利用辅助数列求出数列通项。

类型9、形如an+1=panr (其中p, r为常数) 型。 (1) 当p>0, an>0, 两边取以p为底的对数; (2) 当p<0时, 用迭代法。

类型10、递推公式为f (Sn, an) =0型。

利用an=Sn-Sn-1, (n≥2) 转化为g (an, an-1) =0型, 或h (Sn, Sn-1) =0型, 即混合型的转化为纯粹型的。

递推方法篇9

递归作为一种算法在程序设计语言中广泛应用。它是调用一个函数的过程中又出现直接或者间接地调用该函数本身。递归是计算机科学的一个重要概念, 递归的方法是程序设计中有效的方法, 采用递归编写程序能使程序变得简洁和清晰。

递推算法是一种用若干步可重复的简运算 (规律) 来描述复杂问题的方法。递推是序列计算机中的一种常用算法。递推法的特点是从一个已知的事实出发, 按照一定规律推出下一个事实, 再从这个新的已知事实出发, 再向下推出一个新的事实。

2 问题提出

一场球赛开始前, 售票工作正在紧张进行中, 每张球票为50元, 现有m+n个人排队等待购票, 其中有m个人手持50元的钞票, 另外n个人手持100元的钞票。假设开始售票时售票处没有零钱, 求出这m+n个人排队购票, 使售票处不至出现找不开钱的局面的不同排队种数 (这里正整数m、n从键盘输入) 。

这个问题用一般的解决方法非常麻烦, 下面用递归和递推方法解决。

3 购票问题分析

这是一道组合计数问题。令f (m, n) 表示有m个人手持50元的钞票, n个人手持100元的钞票时共有的方案总数。

(1) n=0。

n=0意味着排队购票的所有人手中拿的都是50元的钞票, 那么这m个人的排队总数为1, 即f (m, 0) =1。

(2) m

当m

(3) 其它情况。

m+n个人排队购票, 第m+n个人站在第m+n-1个人的后面, 则第m+n个人的排队方式可由两种情况获得:①第m+n个人手持100元的钞票, 则在他之前的m+n-1个人中有m个人手持50元的钞票, 有n-1个人手持100元的钞票, 此种情况共有f (m, n-1) ;②第m+n个人手持50元的钞票, 则在他之前的m+n-1个人中有m-1个人手持50元的钞票, 有n个人手持100元的钞票, 此种情况共有f (m-1, n) 。

由加法原理得到f (m, n) 的递推关系:

f (m, n) =f (m, n-1) +f (m-1, n)

初始条件:

当m

当n=0时, f (m, n) =1

4 购票排队递归程序实现

5购票排队递推程序实现

6结语

递归和递推算法解决问题结构清晰、可读性强, 而且容易用数学归纳法来证明算法的正确性, 为设计算法、调试程序带来很大方便。且递推程序的运行速度要快于递归程序。

参考文献

[1]卢开澄, 卢华明.组合数学[M].第4版.北京:清华大学出版社, 2006.

几种递推数列通项的求法篇10

摘要：本文主要介绍了几种典型、常见的递推数列通项公式的求法.

关键词：数列；递推公式；通项公式；待定系数法；类型

递推数列通项公式的求法在近几年的高考试题中屡见不鲜. 解题时，常将数列的递推公式进行一系列变换，构造出等差型、等比型、累加型、累积型等简单数列，从而达到解决问题的目的. 下面介绍几类常见的递推数列的通项公式的求法.

[⇩]类型1：an+1=an+f（n）

由于an+1－an=f（n），所以用“累加相消法”即可解决. 即an=（an－an-1）+（an-1－an-2）+…+（a2－由于=f（n），所以用“累乘相约法”即可解决. 即an=·…·a1.

例2已知a1=5，an+1=5n+1an，求an.

解析由=5k+1，可得an=·…·a1=5n·5n-1…52·5=5.

[⇩]类型3：an+1=ban+c（b≠1，bc≠0）

这种类型采用待定系数法求解. 即设an+1－k=b（an－k），其中k=，故an

－成等比数列.

例3已知a1=1，an+1=2an+1，求an.

解析设an+1－k=2（an－k），则易得k=－1，所以an+1+1=2（an+1）.

即｛an+1｝是首项为2，公比为2的等比数列，所以an+1=2×2n-1=2n. 所以an=2n－1.

[⇩]类型4：an+1=pan+an+b

这种类型可采用待定系数法求解. 即设an+1－［A（n+1）+B］=p·［an－（An+B）］，其中A=，B=，则｛an－（An+B）｝成等比数列.

例4已知a1=－，an+1=3an+2n+1，求an.

解析设an+1-［A（n+1）+B］=3［an-（An+B）］，则an+1=3an－2An+A－2B，

故2n+1=－2An+A－2B对正整数n恒成立.

于上得A=－1，B=－1.

所以｛an+n+1｝成等比数列.

[⇩]类型5：an+1=ban+p·qn（b≠q）

这种类型可采用待定系数法求解. 即设an+1－A·qn+1=b（an－A·qn），则A=，且｛an－A·qn｝成等比数列.

例5已知a1=－1，an+1=3an+2n+1，求an.

解析设an+1－A·2n+1=3·（an－A·2n），则an+1=3an－A·2n.

所以2n+1=－A·2n恒成立. 于是可得A=－2，即｛an+2n+1｝成等比数列.

[⇩]类型6：an+1=b（n）a（k≠1，b（n）>0，an>0）

两边取对数，转化为lgan+1=klgan+lgb（n），再用待定系数法即可求解.

例6已知a1=4，an+1=10na，求an .

解析显然an>0，故两边取对数得lgan＋1=2lgan+n，

设bn=lgan，则bn+1=2bn+n，这就转化为类型4了.

[⇩]类型7：an+1=（pq≠0）

对这种类型，两边取倒数得=·+，

设bn=，则bn+1=·bn+.

这就转化为类型3了.

例7已知a1=，an+1=，求an.

解析由an+1=两边取倒数得=-1，设bn=，

则bn+1=2bn－1.

从而转化为类型3（以下略）.

[⇩]类型8：an+1=（an≠0，pq≠0，pc≠qb，b≠0）

对这种类型可用待定系数法构造新数列，即设an+1+x=，与已知条件比较，求得x，y，再设bn=an+x，得bn+1=，从而转化为类型7.

例8已知数列｛an｝中，a1=2，且an+1=，n∈N+，求数列｛an｝的通项公式.

（1）若Sn结构简单，则消去Sn，转化为递推式f（an，an-1），再化为上述几种类型求解.

例9已知Sn=2an+（－1）n，n∈N+，求an .

解析（1）因为an+1=Sn+1－Sn=［2an+1+（－1）n+1］－［2an+（－1）n］=2an+1－2an－2（－1）n，

所以an+1=2an+2·（－1）n. 这就转化为类型5的情形了.

（2）若Sn相对复杂，则消去an，转化为递推式f（Sn，Sn－1）=0，再化为上述几种类型求解.

例10已知2S=2anSn-an+2，n∈N+，求an .

解析当n≥2时，an=Sn－Sn-1，故2S=2（Sn－Sn-1）·Sn-（Sn－Sn-1）+2 .

所以Sn=. 将Sn看成an，就转化为类型8的情形了.

[⇩]类型10：an+2=pan+1+qan

用待定系数法构造新数列，即设an+2－xan+1=y（an+1－xan），其中x+y=p且xy=－q，则数列｛an+1－xan｝是以y为公比的等比数列.

例11已知a1=2，a2=3，an+2=3an+1－2an，求an .

解析设an+2－xan+1=y（an+1－xan），则

y=2 中的一组解，即可转化为类型5求解.

递推方法篇11

类型1 an+1=an+f (n) .

解析把原递推公式转化为an+1-an=f (n) , 利用累加法 (逐差相加法) 求解.通常f (n) 是一次函数、指数函数, 或者说是易掌握的能够求和的类型.

例1 (2011年高考四川卷理科8) 数列{an}的首项为3, {bn}为等差数列且bn=an+1-an (n∈N*) .若b3=-2, b10=12, 则a8等于 ( ) .

A.0 B.3 C.8 D.11

解析选B.由已知得bn=2n-8, an+1-an=2n-8, 由累加法得 (a2-a1) + (a3-a2) +…+ (a8-a7) =-6+ (-4) + (-2) +0+2+4+6=0⇒a8=a1=3.

例2 (2010年辽宁理数16) 已知数列{an}满足a1=33, an+1-an=2n, 则undefined的最小值为____.

答案:undefined

undefined

设undefined, 令undefined,

则f (n) 在undefined上是单调递增, 在undefined上是递减的.

∵n∈N+, ∴当n=5或6时f (n) 有最小值.

又undefined,

undefined的最小值为undefined

类型2an+1=f (n) an.

解法把原递推公式转化为undefined, 利用累乘法求解, 其中f (n) 多为分式结构.

例3 (2000年全国卷) 设数列{an}是首项为1的正项数列, 且 (n+1) aundefined-naundefined+anan+1=0 (n=1, 2, 3, …) , 则它的通项公式是____.

解析对上式因式分解, 得

undefined

类型3an+1=pan+q (其中p, q均为常数, pq (p-1) ≠0) .

此类数列解决的常用办法是用待定系数法将其构造成一个新的等比数列, 再利用等比数列的性质进行求解.设an+1+m=p (an+m) , 展开整理an+1=pan+pm-m, 比较系数有pm-m=b, 所以undefined, 所以undefined是等比数列, 公比为p, 首项为undefined

例4 (2010年上海文数21) 已知数列{an}的前n项和为Sn, 且Sn=n-5an-85, n∈N*.证明:{an-1}是等比数列.

解析由已知Sn+1= (n+1) -5an+1-85, ①

Sn=n-5an-85, ②

①-②, 得undefined

由类型3, 得undefined

又 ∵a1-1=-15≠0, ∴数列{an-1}是等比数列.

类型4an+1=pan+qn (其中p, q均为常数, pq (p-1) · (q-1) ≠0) . (或an+1=pan+rqn, 其中p, q, r均为常数)

解法一般地, 对于an+1=pan+qn可以采取两种思路, 等式两边除以pn+1或者qn+1, 分别得到undefined或者undefined.前者用累加法, 后者回到了类型3.

对于an+1=pan+rqn推荐用第二种思路.

摘要：数列在高中数学学习中占有相当重要的一部分, 不仅在高考中占有很大的比例, 而且有些涉及数列的高考题难度也很大.其中根据数列的递推关系求数列的通项公式是很多同学学习的一个难点, 也是高考中的一个考点.为了帮助大家突破这一难点, 在这里对常见的由递推数列求通项的类型及方法作一归纳, 并就近几年高考中涉及由数列递推公式求通项公式的题目做一介绍.

关键词：数列,通项公式,求法,应用

参考文献

[1]汤润梅.浅析递推数列的通项公式的求法.学习方法报 (语数教研周刊) , 2011 (12) .

【递推方法】推荐阅读：