给定数列an ，若项an+k 与项an,an+1,…，an+k-1 之间满足关系式为
F（an+k,an+k-1,…,an）=0 或an+k=f(an+k-1,…,an)
则称此关系式为 k阶递推式，由此递推式和初始值 a1,a2,…,an所确定的数列an称为k 阶递推数列。
由此定义知，递推数列实质上定义在自然数集上的一个特殊函数 an=g(n)。例如，由an+1=an+d 和 a1确定的数列为等差数列，其通项公式为 an=a1+(n-1)d。由bn+1=q·bn 和b1 确定的数列为等比数列，其通项公式为 bn=b1·qn-1。对于一般的递推数列，不能像等差（等比）数列一样，很快写出通项公式。
下面介绍几种求递推数列通项公式的方法。
一、求差消去法
求差消去法主要用来求有关和式的递推式的通项公式。
例1 已知对任意 n∈N*，an ＞0且 ■ai3=(■ai)2，求数列 an的通项公式。
解 由题知 ■ai3=(■ai)2 ①
■ai3=(■ai)2 ②
②-①得 a3n+1=an+1(2■ai+an+1)
∵ an ＞0 ∴a2n+1=2■ai+an+1 ③
n≥2时有 a2n =2■ai+an ④
③-④得 (an+1-an)(an+1+an)=an+an+1
∵ an ＞0 ∴an+1-an=1(n∈N*)
又 a1=1 ∴an =a1+(n-1)=n
二、待定系数法
例2 已知 an+1=Aan+B（A,B∈R 且A≠0 ），求数列 an的通项公式。
解 引入参数 λ，使an+1- λ=A(an-λ)
则 an+1= Aan +λ-Aλ ∴λ-Aλ=B
当 A=1时， an是公差为B的等差数列，故an =a1+(n-1)B
当 A≠1时， λ=■，数列an-λ 是公比为A的等比数列。
故 an-λ=(a1-λ)An-1，即an= (a1-λ)An-1+λ。
例3 已知a1=1 ，an=■an-1+n2 -15(n≥2)，求数列an的通项公式
解 引入参数a,b,c ,使
an+(an2+bn+c)=■an-1+[a(n-1)2+b(n-1)+C]
整理得
an=■an-1+(-■a)n2+(-■a-■b)n+■a-■b-■c
与原递推公式对比系数得
-■a=1■a+■b=0■a-■b-■c=-15得 a=-3b=12c=15
故有an- 3n2+12n+15=■[an-1-3(n-1)2+12(n-1)+15]
∴an- 3n2+12n+15=(a1-3x12+12x1+15)·(■)n-1=25x(■)n-1
∴an=25(■)n-1+3n2-12n-15
推广：若an=Aan-1 +f(n) （A∈ R且a≠1 ）， f(n)为m次多项式，则有用待定系数法确定m 次多项式g(n) ，使an+g(n) =A[an-1 +g(n-1)]，于是有an+g(n) =[a1+g(1)]An-1，由此解出an 。
三、换元法
换元法基本思路：恰当选择变换函数φ(x) ，令 an=φ(bn)代入an 的递推公式中，化简得到bn 的一个新的递推式 bn=g(bn-1)，从而解出bn 的通项公式，则an 的通项公式为an= φ(bn)。
例4 已知a1=1 ， an+1=■(1+4an+■)(n∈N*)，求数列 an的通项公式.
解 为使递推公式有理化，可令bn=(■) 即an =■(b2n-1)代入原递推式得
■(b2n+1-1)=■[1+■(b2n-1)+bn]
即： 2b2n+1=■b2n+3bn+■
故 (2bn+1) 2=(bn+3)2
∵ bn＞0 ∴2bn+1=bn+3
即 bn+1=■bn+■
故 bn+1 -3=■(bn-3)
故bn-3 是首项为 b1-3=■-3=2，公比为■ 的等比数列。
∴bn-3=2(■)n-1=(■)n-2
∴bn=(■)n-2+3
于是 an=■(b2n-1)=■[(■)n-2+3]2-■。
四、数学归纳法
数学归纳法求通项公式，一般是先猜想再证明。
上文中例1，n=1,2,3,4,5 时，代入可得 a1=1， a2=2， a3=3，a4=4 ，a5=5
猜想：an=n （n∈N* ）下面用数学归纳法证明。
①当n=1 时显然成立。
②假设n=k （k≥2 且 k∈N*）时， ak=k，则 ■a3i=(■ai)2。
则当n=k+1 时
■a3i=13+23+33+…+k3+a3k+1=■+a3k+1
(■ai)2=[■+ak+1]2=■+k(k+1)ak+1+a2k+1
从而 a3k+1=k(k+1)ak+1+a2k+1
整理得 ak+1[a2k+1-ak+1-k(k+1)]=0
得ak+1=0 （舍）或ak+1=-k （舍）或ak+1=k 。
即n=k+1 时，命题成立。
由①，②可知 an=n
