实用算法(基础算法-递推法)

实用算法(基础算法-递推法-01)

有一类试题，每相邻两项数之间的变化有一定的规律性，我们可将这种规律归纳成如下简捷的递推关系式：

F n=g(F n-1)

这就在数的序列中，建立起后项和前项之间的关系，然后从初始条件(或最终结果)入手，一步步地按递推关系递推，直至求出最终结果(或初始值)。很多程序就是按这样的方法逐步求解的。如果对一个试题，我们要是能找到后一项与前一项的关系并清楚其起始条件(最终结果)，问题就好解决，让计算机一步步算就是了，让高速的计算机做这种重复运算，可真正起到“物尽其用”的效果。

递推分倒推法和顺推法两种形式。一般分析思路：

if求解条件F1

then begin{倒推}

由题意(或递推关系)确定最终结果Fa；

求出倒推关系式F i-1=g'(F i);

i=n;{从最终结果Fn出发进行倒推}

while 当前结果F i非初始值F1 do由F i-1=g(F1)倒推前项；

输出倒推结果F1和倒推过程；

end {then}

else begin{顺推}

由题意(或顺推关系)确定初始值F1(边界条件)；

求出顺推关系式F1=g(Fi-1);

i=1;{由边界条件F1出发进行顺推}

while 当前结果Fi非最终结果Fn do由Fi=g(Fi-1)顺推后项；

输出顺推结果Fn和顺推过程；

end; {else}

一、倒推法

所谓倒推法，就是在不知初始值的情况下，经某种递推关系而获知问题的解或目标，再倒推过来，推知它的初始条件。因为这类问题的运算过程是一一映射的，故可分析得其递推公式。然后再从这个解或目标出发，采用倒推手段，一步步地倒推到这个问题的初始陈述。

下面举例说明。

[例1] 贮油点

一辆重型卡车欲穿过1000公里的沙漠，卡车耗油为1升/公里，卡车总载油能力为500公升。显然卡车一次是过不了沙漠的。因此司机必须设法在沿途建立几个储油点，使卡车能顺利穿越沙漠，试问司机如何建立这些储油点？每一储油点应存多

少油，才能使卡车以消耗最少油的代价通过沙漠？

算法分析：

编程计算及打印建立的贮油点序号，各贮油点距沙漠边沿出发的距离以及存油量。

No. Distance(k.m.) oil(litre)

1 X X X X

2 X X X X

3 X X X X

... ..... ......

设dis[i] 为第i个贮油点至终点(i=0)的距离；

oil[i] 为第i个贮油点的存贮油量；

我们可以用倒推法来解决这个问题。从终点向始点倒推，逐一求出每个贮油点的位置及存油量。

下图表示倒推时的返回点：

从贮油点i向贮油点i+1倒推的策略是，卡车在点i和点i+1间往返若干次。卡车每次返回i+1处时正好耗尽500公升汽油，而每次从i+1出发时又必须装足500公升汽油。两点之间的距离必须满足在耗油最少的条件下使i点贮足i*500分升汽油的要求(0<=i<=n-1)。具体地讲，第一个贮油点i=1应距终点i=0处500km且在该处贮藏500公升汽油，这样才能保证卡车能由i=1处到达终点i=0处，这就是说dis[1]=500 oil[1]=500;

为了在i=1处贮藏500公升汽油，卡车至少从i=2处开两趟满载油的车至i=1处。所以i=2处至少贮有2*500公升汽油，即oil[2]=500*2=1000。另外，再加上从i=1返回至i=2处的一趟空载，合计往返3次。三次往返路程的耗油量按最省要求只能为500公升。即d12=500/3km

dis[2]=dis[1]+d12=dis[1]+500/3

为了在i=2处贮存1000公升汽油，卡车至少从i=3处开三趟满载油的车至i=2处。报以i=3处至少贮有3*500公升汽油，即oil[3]=500*3=1500。加上i=2至i=3处的二趟返程空车，合计5次。路途耗油量也应为500公升，即d23=500/5, dis[3]=dis[2]+d23=dis[2]+500/5;

依此类推，为了在i=k处贮藏k*500公升汽油，卡车至少从i=k+1处开k趟满载车至i=k处，即

oil[k+1]=[k+1]*500=oil[k]+500，加上从i=k处返回i=k+1的k-1趟返程空间，合计2k-1次。这2k-1次总耗油量按最省要求为500公升，即

d k,k+1=500/(2k-1)

dis[k+1]=dis[k]+d k,k+1

=dis[k]+500/(2k-1);

最后，i=n至始点的距离为1000-dis[n],oil[n]=500*n。为了在i=n处取得n*500公升汽油，卡车至少从始点开n+1次满载车至i=n，加上从i=n返回始点的n趟返程空车，合计2n+1次，2n+1趟的总耗油量应正好为(1000-dis[n])*(2n+1)，即始点藏油为oil[n]+(1000-dis[n])*(2n+1)。

下面为程序代码：

program oil_lib;

var

k:integer; {贮油点位置序号}

d, {累计终点至当前贮油点的距离}

d1:real; {i=n至始点的距离}

oil,dis:array[1..10] of real;

i:integer; {辅助变量}

begin

writeln('NO.','distance(k.m)':30,'oil(1.)':80);

k:=1;

d:=500; { 从i=1处开始向始点倒推}

dis[1]:=500;

oil[1]:=500;

repeat

k:=k+1;

d:=d+500/(2*k-1);

dis[k]:=d;

oil[k]:=oil[k-1]+500;

until d>=1000;

dis[k]:=1000; {置始点至终点的距离值}

d1:=1000-dis[k-1]; {求i=n处至始点的距离}

oil[k]:=d1*(2*k+1)+oil[k-1]; {求始点藏油量}

for i:=0 to k do {由始点开始，逐一打印始点至当前贮油点的距离和藏油量} writeln(i,1000-dis[k-i]:30,oil[k-i]:80);

end. {main}

转换为C语言程序如下：

#include

void main()

{

int k; /*贮油点位置序号*/

float d,d1; /*d:累计终点至当前贮油点的距离,d1:i=n至始点的距离*/

float oil[10],dis[10];

int i;

printf("NO. distance(k.m.)\toil(l.)\n");

k=1;

d=500; /*从i=1处开始向始点倒推*/

dis[1]=500;

oil[1]=500;

do{

k=k+1;

d=d+500/(2*k-1);

dis[k]=d;

oil[k]=oil[k-1]+500;

}while(!(d>=1000));

dis[k]=1000; /*置始点至终点的距离值*/

d1=1000-dis[k-1]; /*求i=n处至始点的距离*/

oil[k]=d1*(2*k+1)+oil[k-1]; /*求始点藏油量*/

for(i=0;i

}

实用算法(基础算法-递推法-02)

发表日期：2003年4月10日出处：实用算法的分析和程序设计作者：C语言之家整理已经有1317位

读者读过此文

顺推法

倒推法的逆过程就是顺推法，即由边界条件出发，通过递推关系式推出后项值，再由后项值按递推关系式推出再后项值......，依次递推，直至从问题初始陈述向前推进到这个问题的解为止。

实数数列：一个实数数列共有N项，已知

ai=(a i-1-a i+1)/2+d, (1

键盘输入N,d,a1,a n,m,输出a m

输入数据均不需判错。

算法分析：

分析该题，对公式：

A i=(A i-1-A i+1)/2+d (1

作一翻推敲，探讨其数字变换规律。不然的话会无从下手。

令X=A2s2[i]=(p i,Q i,R i)表示A i=P i X+Q i D+R i A1

我们可以根据

A i=A i-2-2A i-1+2D

=P i X+Q i D+R i A1

推出公式

P i X+Q i D+R i A1=(P i-2-2P i-1)X+(Q i-2-2Q i-1+2)D+(R i-2-2R i-1)A1

比较等号两端X,D和A1的系数项，可得

P i=P i-2-2P i-1

Q i=Q i-2-2Q i-1+2

R i=R i-2-2R i-1

加上两个边界条件

P1=0 Q1=0 R1=1 (A1=A1)

P2=1 Q2=0 R2=0 (A2=A2)

根据Pi、Qi、Ri的递推式，可以计算出

S2[1]=(0,0,1);

S2[3]=(-2,2,1);

S2[4]=(5,-2,-2);

S2[5]=(-12,8,5);

...................

S2[i]=(P i,Q i,R i);

...................

S2[N]=(P N,Q N,R N);

有了上述基础，AM便不难求得。有两种方法：

1、由于A N、A1和P N、Q N、R N已知，因此可以先根据公式：

A2=A N-Q N D-R N A1/P N

求出A2。然后将A2代入公式

A3=A1-2A2+2D

求出A3。然后将A3代入公式

A4=A2-2A3+2D

求出A4。然后将A4代入公式

............................

求出A i-1。然后将A i-1代入公式

A i=A i-2-2A i-1+2D

求出A i。依此类推，直至递推至A M为止。

上述算法的缺陷是由于A2是两数相除的结果，而除数PN递增，因此精度误差在所难免，以后的递推过程又不断地将误差扩大，以至当M超过40时，求出的AM明显徧离正确值。显然这种方法简单但不可靠。

2、我们令A2=A2,A3=X，由S3[i]=(P i,Q i,R i)表示A i=P i X+Q i D+R i A2(i>=2) 可计算出：

S3[2]=(0,0,1)=S2[1];

S3[3]=(1,0,0)=S2[2];

S3[4]=(-2,2,1)=S2[3];

S3[5]=(5,-2-2)=S2[4];

......................

S3[i]=(..........)=S2[i-1];

.....................

S3[N]=(..........)=S2[N-1];

再令A3=A3,A4=X,由S4[i]=(p i,Q i,R i)表示A i=P i X+Q i D+R i A3(i>=3) 可计算得出：S4[3]=(0,0,1)=S3[2]=S2[1];

S4[4]=(1,0,0)=S3[3]=S2[2];

S4[5]=(-22,1)=S3[4]=S2[3];

..........................

S4[i]=(...........)=S3[i-1]=S2[i-2];

.......................

S4[N]=(...........)=S3[N-1]=S2[N-2];

依此类推，我们可以发现一个有趣的式子：

A N=P N-i+2*A i+Q N-i+2*D+R N-i+2*A i-1, 即

A i=(A N-Q N-i+2*D-R N-i+2*A i-1)/P N-i+2

我们从已知量A1和A N出发，依据上述公式顺序递推A2、A3、...、A M.由于P N-i+2递减，因此最后得出的A M要比第一种算法趋于精确。

程序代码如下：

program ND1P4;

const

maxn =60;

var

n,m,i :integer;

d :real;

list :array[1..maxn] of real; {list[i]-------对应ai}

s :array[1..maxn,1..3] of real; {s[i,1]--------对应Pi}

{s[i,2]--------对应Qi}

{s[i,3]--------对应Ri}

procedure init;

begin

write('n m d =');

readln(n,m,d); {输入项数，输出项序号和常数}

write('a1 a',n,'=');

readln(list[1],list[n]); {输入a1和an}

end; {init}

procedure solve;

begin

s[1,1]:=0;s[1,2]:=0;s[1,3]:=1; {求递推边界(P1,Q1,R1)和(P2,Q2,R2)} s[2,1]:=1;s[2,2]:=0;s[2,3]:=0; {根据公式Pi<---Pi-2 - 2*Pi-1}

{Qi<---Qi-2 - 2*Qi-1}

{Ri<---Ri-2 - 2*Ri-1}

{递推(P3,Q3,R3)......Pn,Qn,Rn)}

for i:=3 to n do

begin

s[i,1]:=s[i-2,1]-2*s[i-1,1];

s[i,2]:=s[i-2,2]-2*s[i-1,2]+2;

s[i,3]:=s[i-2,3]-2*s[i-1,3];

end; {for}

end;{solve}

procedure main;

begin

solve; {求(P1,Q1,R1)..(Pn,Qn,Rn)}

{根据公式Ai=(An-Qn-i+2 * d-Rn-i+2 * Ai-1)/Pn-i+2}

{递推A2..Am}

for i:=2 to m do

list[i]:=(list[n]-s[n-i+2,2]*d-s[n-i+2,3]*list[i-1])/s[n-i+2,1];

writeln('a',m,'=',list[m]:20:10); {输出Am}

end; {main}

begin

init; {输入数据}

main; {递推和输出Am} readln;

end. {main}

(完整版)已知数列递推公式求通项公式的几种方法

求数列通项公式的方法 一、公式法 例1 已知数列{}n a 满足1232n n n a a +=+?，12a =，求数列{}n a 的通项公式。 解：1232n n n a a +=+?两边除以12n +，得 113222n n n n a a ++=+，则113222n n n n a a ++-=，故数列{}2 n n a 是以1222 a 1 1==为首项，以23 为公差的等差数列，由等差数列的通项公式，得31(1)22n n a n =+-，所以数列{}n a 的通项公式为31()222 n n a n =-。 评注：本题解题的关键是把递推关系式1232n n n a a +=+?转化为 11 3 222 n n n n a a ++-=，说明数列{}2n n a 是等差数列，再直接利用等差数列的通项公式求出31(1)22 n n a n =+-，进而求出数列{}n a 的通项公式。 二、累加法 例2 已知数列{}n a 满足1121 1n n a a n a +=++=，，求数列{}n a 的通项公式。 解：由121n n a a n +=++得121n n a a n +-=+则 11232211 2 ()()()()[2(1)1][2(2)1](221)(211)1 2[(1)(2)21](1)1 (1)2(1)1 2 (1)(1)1n n n n n a a a a a a a a a a n n n n n n n n n n n ---=-+-++-+-+=-++-+++?++?++=-+-++++-+-=+-+=-++=L L L 所以数列{}n a 的通项公式为2 n a n =。 评注：本题解题的关键是把递推关系式121n n a a n +=++转化为121n n a a n +-=+，进而求出11232211()()()()n n n n a a a a a a a a a ----+-++-+-+L ，即得数列{}n a 的通项公式。

九类常见递推数列求通项公式方法

递推数列通项求解方法举隅 类型一：1n n a pa q +=+（1p ≠） 思路1（递推法）：()123()n n n n a pa q p pa q q p p pa q q q ---??=+=++=+++=?? ……121(1n p a q p p -=++++…211)11n n q q p a p p p --??+=+ ?+ ? --??。 思路2（构造法）：设()1n n a p a μμ++=+，即()1p q μ-=得1 q p μ= -，数列{}n a μ+是以1a μ+为首项、p 为公比的等比数列，则1 111n n q q a a p p p -??+ =+ ?--?? ，即1111n n q q a a p p p -??=++ ? --?? 。 例1 已知数列{}n a 满足123n n a a -=+且11a =，求数列{}n a 的通项公式。 解：方法1（递推法）： ()123232(23)3222333n n n n a a a a ---??=+=++=+++=??…… 1223(122n -=++++ (211) 332)12232112n n n --+??+=+?+=- ? --?? 。 方法2（构造法）：设()12n n a a μμ++=+，即3μ=，∴数列{}3n a +是以134a +=为首项、2为公比的等比数列，则1 1342 2n n n a -++=?=，即123n n a +=-。 类型二：1()n n a a f n +=+ 思路1（递推法）： 123(1)(2)(1)(3)(2)(1)n n n n a a f n a f n f n a f n f n f n ---=+-=+-+-=+-+-+-= …1 11 ()n i a f n -==+ ∑。

由递推公式求通项公式的方法

由递推公式求通项公式的方法 已知数列的递推公式，求取其通项公式是数列中一类常见的题型，这类题型如果单纯的看某一个具体的题目，它的求解方法灵活是灵活多变的，构造的技巧性也很强，但是此类题目也有很强的规律性，存在着解决问题的通法，本文就高中数学中常见的几类题型从解决通法上做一总结，方便于学生学习和老师的教学，不涉及具体某一题目的独特解法与技巧。 一、1()n n a a f n +=+型数列，（其中()f n 不是常值函数) 此类数列解决的办法是累加法，具体做法是将通项变形为1()n n a a f n +-=，从而就有 21321(1),(2),,(1).n n a a f a a f a a f n --=-=-=- 将上述1n -个式子累加，变成1(1)(2)(1)n a a f f f n -=+++- ，进而求解。 例1. 在数列{}n a 中,112,21,.n n n a a a n a +==+-求 解：依题意有 213211,3,,23n n a a a a a a n --=-=-=- 逐项累加有221(123)(1)1323(1)212n n n a a n n n n +---=+++-= =-=-+ ，从而223n a n n =-+。 注：在运用累加法时,要特别注意项数,计算时项数容易出错. 变式练习：已知{}n a 满足11=a ,) 1(11+=-+n n a a n n ,求}{n a 的通项公式。 二、)(1n f a a n n ?=+型数列，（其中()f n 不是常值函数) 此类数列解决的办法是累积法，具体做法是将通项变形为1()n n a f n a +=，从而就有 32121 (1),(2),,(1)n n a a a f f f n a a a -===- 将上述1n -个式子累乘，变成1 (1)(2)(1)n a f f f n a =???- ，进而求解。 例2. 已知数列{}n a 中11123,(2)321 n n n a a a n n --==?≥+，求数列{}n a 的通项公式。

由递推公式求通项公式的三种方法

由递推公式求通项公式的三种方法 递推公式和通项公式是数列的两种表示方法，它们都可以确定数列中的任意一项，只是由递推公式确定数列中的项时，不如通项公式直接，下面介绍由递推公式求通项公式的几种方法． 1．累加法 [典例1] 数列{a n }的首项为3，{b n }为等差数列且b n ＝a n ＋1－a n (n ∈N * )．若b 3＝－2，b 10＝12，则a 8＝( ) A ．0 B ．3 C ．8 D ．11 [解析] 由已知得b n ＝2n －8，a n ＋1－a n ＝2n －8，所以a 2－a 1＝－6，a 3－a 2＝－4，…，a 8－a 7＝6，由累加法得a 8－a 1＝－6＋(－4)＋(－2)＋0＋2＋4＋6＝0，所以a 8＝a 1＝3. [答案] B [题后悟道] 对形如a n ＋1＝a n ＋f (n )(f (n )是可以求和的)的递推公式求通项公式时，常用累加法，巧妙求出a n －a 1与n 的关系式． 2．累乘法 [典例2] 已知数列{a n }中，a 1＝1，前n 项和S n ＝ n ＋23a n . (1)求a 2，a 3； (2)求{a n }的通项公式． [解] (1)由S 2＝43 a 2得3(a 1＋a 2)＝4a 2， 解得a 2＝3a 1＝3. 由S 3＝53 a 3得3(a 1＋a 2＋a 3)＝5a 3， 解得a 3＝32 (a 1＋a 2)＝6. (2)由题设知a 1＝1. 当n >1时，有a n ＝S n －S n －1＝n ＋23a n －n ＋13 a n －1，

整理得a n ＝n ＋1n －1 a n －1. 于是a 2＝31a 1，a 3＝42a 2，…，a n －1＝n n －2a n －2，a n ＝n ＋1n －1 a n －1. 将以上n －1个等式中等号两端分别相乘，整理得a n ＝ n n ＋1 2. 综上可知，{a n }的通项公式a n ＝ n n ＋1 2. [题后悟道] 对形如a n ＋1＝a n f (n )(f (n )是可以求积的)的递推公式求通项公式时，常用累乘法，巧妙求出a n a 1与n 的关系式． 3．构造新数列 [典例3] 已知数列{a n }满足a 1＝1，a n ＋1＝3a n ＋2；则a n ＝________. [解析] ∵a n ＋1＝3a n ＋2，∴a n ＋1＋1＝3(a n ＋1)， ∴a n ＋1＋1a n ＋1 ＝3，∴数列{a n ＋1}为等比数列，公比q ＝3， 又a 1＋1＝2，∴a n ＋1＝2·3 n －1， ∴a n ＝2·3n －1－1. [答案] 2×3 n －1－1 [题后悟道] 对于形如“a n ＋1＝Aa n ＋B (A ≠0且A ≠1)”的递推公式求通项公式，可用迭代法或构造等比数列法． 上面是三种常见的由递推公式求通项公式的题型和对应解法，从这些题型及解法中可以发现，很多题型及方法都是相通的，如果能够真正理解其内在的联系及区别，也就真正做到了举一反三、触类旁通，使自己的学习游刃有余，真正成为学习的主人．

九类常见递推数列求通项公式方法

递推数列通项求解方法 类型一：1n n a pa q += +（1p ≠） 思路1（递推法）：()123()n n n n a pa q p pa q q p p pa q q q ---??=+=++=+++=?? ......121(1n p a q p p -=++++ (2) 1 1)11n n q q p a p p p --??+=+?+ ? --?? 。 思路2（构造法）：设()1n n a p a μμ++=+，即()1p q μ-=得1 q p μ= -，数列 {}n a μ+是以1a μ+为首项、p 为公比的等比数列，则1 111n n q q a a p p p -??+ =+ ?--??，即1111n n q q a a p p p -??=++ ? --?? 。 例1 已知数列{}n a 满足123n n a a -=+且11a =，求数列{}n a 的通项公式。 解：方法1（递推法）： ()123232(23)3222333n n n n a a a a ---??=+=++=+++=?? (1) 22 3(122n -=++++ (2) 11 332 )12232112n n n --+??+=+?+=- ? --? ?。 方法2（构造法）：设()12n n a a μμ++=+，即3μ=，∴数列{}3n a +是以134 a +=为首项、2为公比的等比数列，则113422n n n a -++=?=，即1 23n n a +=-。

1n n +思路1（递推法）： 123(1)(2)(1)(3)(2)(1)n n n n a a f n a f n f n a f n f n f n ---=+-=+-+-=+-+-+-= …1 11 ()n i a f n -==+∑。 思路2（叠加法）：1(1)n n a a f n --=-，依次类推有：12(2)n n a a f n ---=-、 23(3)n n a a f n ---=-、…、21(1)a a f -=，将各式叠加并整理得1 11 ()n n i a a f n -=-= ∑ ，即 1 11 ()n n i a a f n -==+ ∑ 。 例2 已知11a =，1n n a a n -=+，求n a 。 解：方法1（递推法）：123(1)(2)(1)n n n n a a n a n n a n n n ---=+=+-+=+-+-+= ......1[23a =+++ (1) (1)(2)(1)]2 n i n n n n n n =++-+-+= = ∑ 。 方法2（叠加法）：1n n a a n --=，依次类推有：121n n a a n ---=-、232n n a a n ---=-、…、 212a a -=，将各式叠加并整理得12 n n i a a n =-= ∑ ，12 1 (1)2 n n n i i n n a a n n ==+=+ = = ∑ ∑ 。

递推公式求通项公式的几种方

由递推公式求通项公式的常用方法 由数列的递推公式求通项公式是高中数学的重点问题，也是难点问题，它是历年高考命题的热点题。对于递推公式确定的数列的求解，通常可以通过递推公式的变换，转化为等差数列或等比数列问题，有时也用到一些特殊的转化方法与特殊数列。 方法一：累加法 形如a n +1－a n ＝f (n )（n ＝2,3,4,…）,且f (1)＋f (2)＋…＋f (n -1)可求，则用累加法求a n 。有时若不能直接用，可变形成这种形式，然后利用这种方法求解。 例1：（07年北京理工农医类）已知数列{a n }中，a 1＝2,a n ＋1＝a n ＋cn (c 是常数，n ＝1,2,3,…)且a 1,a 2,a 3成公比不为1的等比数列 （1）求c 的值 （2）求{a n }的通项公式 解：（1）a1,a2,a3成公比不为1的等比数列 2 022)2(2)() ,3,2,1(111113 12 2===++?=+∴=+=?=∴+c c a c c a a c a n cn a a a a a n n 因此（舍去）或解得又 （2）由（1）知n a a n a a n n n n 2,211=-+=++即，将n ＝1,2, …,n －1,分别代入 ) 1(2322 2121342312-=-?=-?=-?=--n a a a a a a a a n n 将上面n －1个式子相加得a n －a 1＝2(1＋2＋3＋…＋n －1)＝n 2 －n 又a 1＝2,a n ＝n 2 －n ＋2 方法二：累乘法 形如 a n +1 a n ＝g (n )（n ＝2,3,4…），且f (1)f(2)…f (n －1)可求，则用累乘法求a n .有时若不能直接用，可变形成这种形式，然后用这种方法求解。

递推关系求通项公式教案

教 案 课题：递推关系求通项公式 课型： 习题课 授课人：呼延敏 要点自主整合：累加法、累乘法两种基本的由递推公式求通项 教学目标: 【知识目标】 累加法、累乘法的应用 【能力目标】 培养学生的发散思维能力，进而提高转化与化归能力的培养. 【情感目标】培养学生的创新意识与创新思维，培养学生的合作探究意识 。 学生能够通过等差、等比数列的通项公式推导得到累加法、累乘法两种基 本的由递推公式求通项公式的方法，并进一步拓展到“构造法”，在此过程中使学生的思维空间得以拓展，养成善于观察，勇于创新的学习精神。 教学重点：已知数列递推关系求通项关系的几种基本类型。 教学难点：累加法、累乘法的应用 教学过程： 引 例： 11=a n n a a +=+21 求n a 提问：等差数列的通项公式的推导方法是什么? 学生答：…………… 类型<一> 形如a 1=a, a n+1=a n +f ()n 型 其中f ()n 为可求和数列采用累 加法求通项 例1：数列{}n a 中a 1=1 a n+1=2n+a n 求a n 解析： a n+1—a n =2n ∴当n 2≥时a n —a n-1=2()1-n a 2—a 1=2 a 3—a 2=4

a 4—a 3=6 ..…… a n —a n-1=2()1-n 对上面的n-1个式子相加得到：a n =n 2—n+1 变式训练1：数列中{}n a a 1=1 a n+1=a n +2n 求a n 类型<二> 形如a 1=a, a n+1=a n *f ()n 型 采用累乘法 在引例1中将加号+变为乘号*即得到一个等比数列11=a n n a a *=+21 让学生回顾：等比数列中通项公式的推导方法是什么？ 学生答：………… 将变式训练1中的加号+变为乘号*得到如下例题 例2：数列中{}n a 11=a n n n a a 21*=+ 求n a 解析： 1+n a = n n a 2* ∴当2≥n 时 11 2--=n n n a a 21 2=a a 22 32=a a 3342=a a ……….. 11 2--=n n n a a

数列递推公式的九种方法

求递推数列的通项公式的九种方法 利用递推数列求通项公式，在理论上和实践中均有较高的价值.自从二十世纪八十年代以来，这一直是全国高考和高中数学联赛的热点之一. 一、作差求和法 例1 在数列{}中，31 =a , ) 1(11++ =+n n a a n n ，求通项公式. 解：原递推式可化为：1 111 +- + =+n n a a n n 则, 2 11112 -+=a a 3 12123-+ =a a 4 13134-+ =a a ，……，n n a a n n 1111--+ =-逐项相加得：n a a n 111- +=. 故n a n 14- =. 二、作商求和法 例 2 设数列{}是首项为1的正项数列，且 0)1(12 2 1 =+-+++n n n n a a na a n （n=1,2,3…） ，则它的通项公式是=▁▁▁（2000年高考15题） 解：原递推式可化为： ) ]()1[(11n n n n a a na a n +-+++=0 ∵ n n a a ++1＞0， 1 1+=+n n a a n n 则 ,4 3,32,21342312===a a a a a a ……，n n a a n n 11 -= - 逐项相乘得： n a a n 1 1=，即=n 1. 三、换元法 例3 已知数列{}，其中9 13,3421 == a a ，且当n ≥3时， ) (3 1 211----=-n n n n a a a a ，求通项公式（1986年高考文科第八

题改编）. 解：设1 1 ---=n n n a a b ，原递推式可化为： } {,3 1 21n n n b b b --=是一个等比数列，9 1 3491312 1 =-= -=a a b ，公比为3 1.故n n n n b b )3 1 ()31(91)31(2211 ==?=---.故n n n a a )3 1 (1=--.由逐差法可得： n n a )3 1(2123-= . 例4已知数列{}，其中2,12 1 ==a a ，且当n ≥3时，122 1 =+---n n n a a a ，求通项公式。解 由122 1 =+---n n n a a a 得：1)()(2 1 1 =------n n n n a a a a ，令1 1 ---=n n n a a b ，则上式为12 1 =---n n b b ，因此是一个等差数列，1121=-=a a b ，公差为1.故n b n =.。 由于112312121-=-++-+-=+++--n n n n a a a a a a a b b b ΛΛ 又2 )1(12 1 -= +++-n n b b b n Λ 所以)1(2 1 1-= -n n a n ，即)2(2 12 +-= n n a n 四、积差相消法 例5设正数列，，…，，…满足2 -n n a a 2 1---n n a a = ) 2(≥n 且11 ==a a ，求的通项公式. 解 将递推式两边同除以2 1--n n a a 整理得：122 1 1=----n n n n a a a a 设= 1 -n n a a ，则0 11 a a b = =1，1 21=--n n b b ，故有 1 212=-b b ⑴122 3 =-b b ⑵ … … … …

常见递推数列通项公式的求法典型例题及习题

.. . 常见递推数列通项公式的求法典型例题及习题 【典型例题】 [例1] b ka a n n +=+1型。 （1）1=k 时，}{1n n n a b a a ?=-+是等差数列，)(1b a n b a n -+?= （2）1≠k 时，设)(1m a k m a n n +=++ ∴ m km ka a n n -+=+1 比较系数：b m km =- ∴ 1-= k b m ∴ }1{-+ k b a n 是等比数列，公比为k ，首项为11-+k b a ∴ 11)1(1-?-+=-+ n n k k b a k b a ∴ 1)1(11--?-+=-k b k k b a a n n [例2] )(1n f ka a n n +=+型。 （1）1=k 时，)(1n f a a n n =-+，若)(n f 可求和，则可用累加消项的方法。 例：已知}{n a 满足11=a ，)1(1 1+= -+n n a a n n 求}{n a 的通项公式。 解： ∵ 11 1)1(11+- =+= -+n n n n a a n n ∴ n n a a n n 1111--= -- 112121---=---n n a a n n 21 3132-- -= ---n n a a n n ……

.. . 312123-= -a a 21112-=-a a 对这（1-n ）个式子求和得： n a a n 111- =- ∴ n a n 1 2- = （2）1≠k 时，当b an n f +=)(则可设)()1(1B An a k B n A a n n ++=++++ ∴ A B k An k ka a n n --+-+=+)1()1(1 ∴ ???=--=-b A B k a A k )1()1( 解得： 1-= k a A ，2)1(1-+-=k a k b B ∴ }{B An a n ++是以B A a ++1为首项，k 为公比的等比数列 ∴ 1 1)(-?++=++n n k B A a B An a ∴ B An k B A a a n n --?++=-1 1)( 将A 、B 代入即可 （3）n q n f =)(（≠q 0，1） 等式两边同时除以1 +n q 得q q a q k q a n n n n 1 11+?=++ 令 n n n q a C = 则q C q k C n n 1 1+ =+ ∴ }{n C 可归为b ka a n n +=+1型 [例3] n n a n f a ?=+)(1型。 （1）若)(n f 是常数时，可归为等比数列。 （2）若)(n f 可求积，可用累积约项的方法化简求通项。 例：已知： 311= a ，1121 2-+-=n n a n n a （2≥n ）求数列}{n a 的通项。 解：123537532521232121212233 2211+= ?--?--?+-=???-----n n n n n n n a a a a a a a a a a n n n n n n

由递推公式求通项的9种方法经典汇总

由递推公式求通项的9种方法经典汇总

————————————————————————————————作者：————————————————————————————————日期：

精析由递推公式求通项的9种方法 1．a n ＋1＝a n ＋f (n )型 把原递推公式转化为a n ＋1－a n ＝f (n )，再利用累加法(逐差相加法)求解，即a n ＝a 1＋(a 2－a 1)＋(a 3－a 2)＋…＋(a n －a n －1)＝a 1＋f (1)＋f (2)＋f (3)＋…＋f (n －1)． [例1] 已知数列{a n }满足a 1＝12，a n ＋1＝a n ＋1n 2＋n ，求a n . [解] 由条件，知a n ＋1－a n ＝1n 2＋n ＝1n (n ＋1)＝1n －1n ＋1 ，则(a 2－a 1)＋(a 3－a 2)＋(a 4－a 3)＋…＋(a n －a n －1)＝????1－12＋????12－13＋????13－14＋…＋? ?? ??1n －1－1n ， 所以a n －a 1＝1－1n . 因为a 1＝12，所以a n ＝12＋1－1n ＝32－1n . 2．a n ＋1＝f (n )a n 型 把原递推公式转化为a n ＋1a n ＝f (n )，再利用累乘法(逐商相乘法)求解，即由a 2a 1＝f (1)，a 3a 2＝f (2)，…，a n a n －1 ＝f (n －1)，累乘可得a n a 1＝f (1)f (2)…f (n －1)． [例2] 已知数列{a n }满足a 1＝23，a n ＋1＝n n ＋1·a n ，求a n . [解] 由a n ＋1＝n n ＋1 ·a n ，得a n ＋1a n ＝n n ＋1， 故a n ＝a n a n －1·a n －1a n －2·…·a 2a 1·a 1＝n －1n ×n －2n －1 ×…×12×23＝23n .即a n ＝23n . 3．a n ＋1＝pa n ＋q (其中p ，q 均为常数，pq (p －1)≠0)型 对于此类问题，通常采用换元法进行转化，假设将递推公式改写为a n ＋1＋t ＝p (a n ＋t )，比较系数可知t ＝ q p －1 ，可令a n ＋1＋t

已知数列递推公式求通项公式的几种方法

已知数列递推公式求通项公式的几种方法 Revised on November 25, 2020

求数列通项公式的方法 一、公式法 例1 已知数列{}n a 满足1232n n n a a +=+?，12a =，求数列{}n a 的通项公式。 解：1232n n n a a +=+?两边除以12n +，得 113222n n n n a a ++=+，则11 3 222 n n n n a a ++-=，故数列{}2n n a 是以1222 a 1 1==为首项，以23 为公差的等差数列，由等差数列的通项公式，得31(1)22n n a n =+-，所以数列{}n a 的通项公式为31()222n n a n =-。 评注：本题解题的关键是把递推关系式1232n n n a a +=+?转化为 11 3 222 n n n n a a ++-=，说明数列{}2 n n a 是等差数列，再直接利用等差数列的通项公式求出3 1(1) 22n n a n =+-，进而求出数列{}n a 的通项公式。 二、累加法 例2 已知数列{}n a 满足11211n n a a n a +=++=，，求数列{}n a 的通项公式。 解：由121n n a a n +=++得121n n a a n +-=+则 所以数列{}n a 的通项公式为2n a n =。 评注：本题解题的关键是把递推关系式121n n a a n +=++转化为 121n n a a n +-=+，进而求出11232211()()()()n n n n a a a a a a a a a ----+-+ +-+-+， 即得数列{}n a 的通项公式。 例3 已知数列{}n a 满足112313n n n a a a +=+?+=，，求数列{}n a 的通项公式。 解：由1231n n n a a +=+?+得1231n n n a a +-=?+则 所以3 1.n n a n =+-

常见递推数列通项公式求法(教案)

问题 1:已知数列{a } ， a 1 = 1 ， a n +1 = n + 2 ，求{a n }的通项公式。 2 常见递推数列通项公式的求法 一、课题：常见递推数列通项公式的求法 二、教学目标 (1)会根据递推公式求出数列中的项，并能运用叠加法、叠乘法、待定系数 法求数列的通项公式。 (2) 根据等差数列通项公式的推导总结出叠加法的基本题型，引导学生分 组合作并讨论完成叠乘法及待定系数法的基本题型。 (3)通过互助合作、自主探究培养学生细心观察、认真分析、善于总结的良 好思维习惯，以及积极交流的主体意识。 三、教学重点：根据数列的递推关系式求通项公式。 四、教学难点：解题过程中方法的正确选择。 五、教学课时： 1 课时 六、教学手段：黑板，粉笔 七、教学方法： 激励——讨论——发现——归纳——总结 八、教学过程 （一）复习回顾： 1、通项公式的定义及其重要作用 2、区别递推公式与通项公式，从而引入课题 （二）新知探究： a n 变式： 已知数列 {a n } ， a 1 = 1 ， a n +1 = a n + 2n ，求{a n }的通项公式。 活动 1：通过分析发现形式类似等差数列，故想到用叠加法去求解。教师引导学 生细致讲解整个解题过程。 解：由条件知： a n +1 - a = 2n n 分别令 n = 1,2,3,? ? ? ? ??,(n - 1) ，代入上式得 (n - 1) 个 等式叠加之， 即 (a 2 - a 1 ) + (a 3 - a 2 ) + (a 4 - a 3 ) + ? ? ? ? ? ? +(a n - a n -1 ) = 2 + 2 ? 2 + 2 ? 3 + 2 ? (n - 2) + 2 ? (n - 1) 所以 a - a = (n - 1)[2 + 2 ? (n - 1)] n 1 a = 1,∴ a = n 2 - n + 1 1 n

备战2020数学高考三大类递推数列通项公式的求法

三大类递推数列通项公式的求法 湖北省竹溪县第一高级中学徐鸿 一、一阶线性递推数列求通项问题 一阶线性递推数列主要有如下几种形式： 1. 这类递推数列可通过累加法而求得其通项公式(数列{f(n)}可求前n项和). 当为常数时，通过累加法可求得等差数列的通项公式．而当为等差数列时， 则为二阶等差数列，其通项公式应当为形式，注意与等差数列求和公式一般形式的区别，后者是，其常数项一定为０． 2. 这类递推数列可通过累乘法而求得其通项公式(数列{g(n)}可求前n项积). 当为常数时，用累乘法可求得等比数列的通项公式． 3.； 这类数列通常可转化为，或消去常数转化为二阶递推式 . 例１已知数列中，,求的通项公式． 解析：解法一：转化为型递推数列． ∵∴又，故数列｛｝是首项为２，公比为２的等比数列．∴，即． 解法二：转化为型递推数列． ∵=2x n-1+1(n≥2) ①∴=2x n+1 ② ②－①，得(n≥2)，故｛｝是首项为x 2-x 1 =2， 公比为２的等比数列，即，再用累加法得．解法三：用迭代法． 当然,此题也可用归纳猜想法求之，但要用数学归纳法证明．

例２已知函数的反函数为 求数列的通项公式. 解析：由已知得，则． 令=,则.比较系数，得. 即有．∴数列｛｝是以为首项，为 公比的等比数列，∴，故． 评析：此题亦可采用归纳猜想得出通项公式，而后用数学归纳法证明之． （4） 若取倒数,得，令，从而转化为（1）型而求之. （5）； 这类数列可变换成，令，则转化为(1)型一阶线性递推公式. 例３设数列求数列的通项公式．解析：∵，两边同除以，得．令，则有．于是，得，∴数列是以首项为，公比为的等比数列，故，即，从而．例４设求数列的通项公式． 解析：设用代入，可解出．

线性代数 递推公式法(行列式例题)

TH1： 5 1 010 6 51000 6500 06010 00152=D 展开 按第二列5 10 06510065 0006 1-6 510065*********- 3655 106510 65?-=1145108065-=--= 提取公因子： ef cf bf de cd bd ae ac ab ---=e c b e c b e c b adf --- =1 1 1 111 1 11 ---adfbce =abcdef 4 化上三角形： d c b a 10 1 10011001---21ar r +d c b a ab 100110011 010---+ =1 2) 1)(1(+--d c a ab 10110 1--+ 2 3dc c +0 10 111-+-+cd c ad a a b =2 3) 1)(1(+--cd ad ab +-+111=1++++ad cd ab abcd

递推法: n n n n n d c d c b a b a D 0 1 1 112 = n n n n n n d d c d c b a b a a 000000 1111 11 11 ---- 展开 按第一行 00 0) 1(11 1 1111 1 1 2c d c d c b a b a b n n n n n n n ----+-+ 2222---n n n n n n D c b D d a 都按最后一行展开 由此得递推公式： 222)(--=n n n n n n D c b d a D 即 ∏=-=n i i i i i n D c b d a D 222)( 而 11111 11 12c b d a d c b a D -==

数列的几种递推公式

数列的几种递推公式 一、 )(1n f a a n n +=+ 解法：把原递推公式转化为)(1n f a a n n =-+，利用累加法(逐差相加法)求解。 例1:已知数列{}n a 满足211=a ，n n a a n n ++=+211，求n a 。 二、 n n a n f a )(1=+ 解法：把原递推公式转化为)(1 n f a a n n =+，利用累乘法(逐商相乘法)求解。 例2:已知数列{}n a 满足321=a ，n n a n n a 1 1+= +，求n a 。

例3:已知31=a ，n n a n n a 2 31 31+-=+ )1(≥n ，求n a 。 解：1231 32231232)2(31)2(32)1(31)1(3a n n n n a n +-?+?-??????+---?+---= 3437 52633134 8531n n n n n --= ????=---。 变式:已知数列{a n }，满足a 1=1，1321)1(32--+???+++=n n a n a a a a (n ≥2)，则 {a n }的通项1 ___n a ?=?? 12n n =≥ 解：由已知，得n n n na a n a a a a +-+???+++=-+13211)1(32， 用此式减去已知式，得 当2≥n 时，n n n na a a =-+1，即n n a n a )1(1+=+， 又112==a a ， n a a a a a a a a a n n =???====∴-1 3423121,,4,3,1, 1， 将以上n 个式子相乘，得2 ! n a n =)2(≥n 三、 q pa a n n +=+1（其中p ，q 均为常数，)0)1((≠-p pq ）。 解法（待定系数法）：把原递推公式转化为：)(1t a p t a n n -=-+，其中p q t -=1，再利用换元法转化为等比数列求解。

求递推数列通项公式和求和的常用方法

求递推数列通项公式和求和的常用方法 求递推数列通项公式是数列知识的一个重点，也是一个难点，高考也往往通过考查递推数列来考查学生对知识的探索能力，求递推数列的通项公式一般是将递推公式变形，推得原数列是一种特殊的数列或原数列的项的某种组合是一种特殊数列，把一些较难处理的数列问题化为中学中所研究的等差或等比数列，下面就求递推数列通向公式的常用方法举例一二，供参考： 一 公式法：利用熟知的的公式求通项公式的方法称为公式法，常用的公式有1n n n a S S -=-(2)n ≥，等差数列或等比数列的通项公式。 例一 已知无穷数列{}n a 的前n 项和为n S ，并且*1()n n a S n N +=∈，求{}n a 的通项公式？ 【解析】： 1n n S a =-，∴ 111n n n n n a S S a a +++=-=-，∴ 112n n a a +=，又112a =， ∴ 12n n a ??= ??? . 反思：利用相关数列{}n a 与{}n S 的关系：11a S =,1n n n a S S -=-(2)n ≥与提设条件，建立递推关系，是本题求解的关键. 跟踪训练1.已知数列{}n a 的前n 项和n S ，满足关系()1lg n S n +=(1,2)n =???.试证数列{}n a 是等比数列. 二 归纳法：由数列前几项用不完全归纳猜测出数列的通项公式，再利用数学归纳法证明其正确性，这种方法叫归纳法. 例二 已知数列{}n a 中，11a =，121(2)n n a a n -=+≥，求数列{}n a 的通项公式. 【解析】：11a =，121(2)n n a a n -=+≥，∴2121a a =+3=，3221a a =+7=???? 猜测21n n a =-*()n N ∈，再用数学归纳法证明.（略） 反思：用归纳法求递推数列，首先要熟悉一般数列的通项公式，再就是一定要用数学归纳法证明其正确性. 跟踪训练2.设{}n a 是正数组成的数列，其前n 项和为n S ，并且对于所有自然数n ，n a 与1的等差中项等于n S 与1的等比中项，求数列{}n a 的通项公式. 三 累加法：利用1211()()n n n a a a a a a -=+-+???-求通项公式的方法称为累加法。累加法是求型如1()n n a a f n +=+的递推数列通项公式的基本方法（()f n 可求前n 项和）. 例三 已知无穷数列{}n a 的的通项公式是12n n a ??= ??? ，若数列{}n b 满足11b =，(1)n ≥，求数列{}n b 的通项公式. 【解析】：11b =,112n n n b b +??-= ??? (1)n ≥,∴1211()()n n n b b b b b b -=+-+???-=1+12+??+

常见递推数列通项公式的求法典型例题及习题

常见递推数列通项公式的求法典型例题及习题 【典型例题】 [例1] b ka a n n +=+1型。 （1）1=k 时，}{1n n n a b a a ?=-+是等差数列，)(1b a n b a n -+?= （2）1≠k 时，设)(1m a k m a n n +=++ ∴ m km ka a n n -+=+1 比较系数：b m km =- ∴ 1-= k b m ∴ }1{-+ k b a n 是等比数列，公比为k ，首项为11-+k b a ∴ 11)1(1-?-+=-+ n n k k b a k b a ∴ 1)1(11--?-+=-k b k k b a a n n [例2] )(1n f ka a n n +=+型。 （1）1=k 时，)(1n f a a n n =-+，若)(n f 可求和，则可用累加消项的方法。 例：已知}{n a 满足11=a ，)1(1 1+= -+n n a a n n 求}{n a 的通项公式。 解： ∵ 11 1)1(11+- =+= -+n n n n a a n n ∴ n n a a n n 1111--= -- 112121---=---n n a a n n 21 3132-- -=---n n a a n n …… 312123-= -a a 21112-=-a a 对这（1-n ）个式子求和得： n a a n 111- =- ∴ n a n 1 2- =

（2）1≠k 时，当b an n f +=)(则可设)()1(1B An a k B n A a n n ++=++++ ∴ A B k An k ka a n n --+-+=+)1()1(1 ∴ ???=--=-b A B k a A k )1()1( 解得： 1-=k a A ，2)1(1-+-=k a k b B ∴ }{B An a n ++是以B A a ++1为首项，k 为公比的等比数列 ∴ 1 1)(-?++=++n n k B A a B An a ∴ B An k B A a a n n --?++=-11)( 将A 、B 代入即可 （3）n q n f =)(（≠q 0，1） 等式两边同时除以1 +n q 得q q a q k q a n n n n 1 11+?=++ 令 n n n q a C = 则q C q k C n n 1 1+ =+ ∴ }{n C 可归为b ka a n n +=+1型 [例3] n n a n f a ?=+)(1型。 （1）若)(n f 是常数时，可归为等比数列。 （2）若)(n f 可求积，可用累积约项的方法化简求通项。 例：已知： 311= a ，1 121 2-+-=n n a n n a （2≥n ）求数列}{n a 的通项。 解：123537532521232121212233 2211+= ?--?--?+-=???-----n n n n n n n a a a a a a a a a a n n n n n n ∴ 1211231+= +? =n n a a n [例4] 11 --+?? =n n n a m a m k a 型。

最全的递推数列求通项公式方法

高考递推数列题型分类归纳解析 各种数列问题在很多情形下，就是对数列通项公式的求解。特别是在一些综合性比较 强的数列问题中，数列通项公式的求解问题往往是解决数列难题的瓶颈。本文总结出几种求解数列通项公式的方法，希望能对大家有帮助。 类型1 )(1n f a a n n +=+ 解法：把原递推公式转化为)(1n f a a n n =-+，利用累加法(逐差相加法)求解。 例:已知数列{}n a 满足211= a ，n n a a n n ++=+211，求n a 。 解：由条件知：1 1 1)1(1121+-=+=+= -+n n n n n n a a n n 分别令)1(,,3,2,1-??????=n n ，代入上式得)1(-n 个等式累加之，即 )()()()(1342312--+??????+-+-+-n n a a a a a a a a )111()4131()3121()211(n n --+??????+-+-+-= 所以n a a n 1 11-=- 211=a ，n n a n 1231121-=-+=∴ 变式:（2004，全国I ，个理22．本小题满分14分） 已知数列1}{1=a a n 中，且a 2k =a 2k －1+(－1)K , a 2k+1=a 2k +3k , 其中k=1,2,3,……. （I ）求a 3, a 5； （II ）求{ a n }的通项公式. 解： k k k a a )1(122-+=-，k k k a a 3212+=+ ∴k k k k k k a a a 3)1(312212+-+=+=-+，即k k k k a a )1(31212-+=--+ ∴)1(313-+=-a a ， 2235)1(3-+=-a a …… …… k k k k a a )1(31212-+=--+ 将以上k 个式子相加，得 ]1)1[(2 1 )13(23])1()1()1[()333(22112--+-=-+???+-+-++???++=-+k k k k k a a 将11=a 代入，得