什么是递归数列?
递归数列
是一种用归纳方法给定的数列。
例如,等比数列可以用归纳方法来定义,先定义第一项
a1
的值(
a1
≠
0
),对
于以后的项
,用递推公式an+1=qan
(q≠0,n=1,2,…)给出定义。
一般地,递归数列的前k项a1,a2,…,ak为已知数,从第k+1项起,由某一递推公式an+k=f(an,an+1,…,an+k-1)
(
n=1,2,…)所确定。k称为递归数列的阶数。例如
,已知
a1=1,a2=1,其余各项由公式an+1=an+an-1(n=2,3,…)给定的数列是二阶递归数列。这是斐波那契数列,各项依次为
1
,1
,2
,3,5
,8
,13
,21
,…,同样
,由递归式an+1-an
=an-an-1(
a1,a2
为已知,n=2,3,…
)
给定的数列,也是二阶递归数列,这是等差数列。
什么是线性递归数列
当递推式中只含数列中的项,而无常数项或其它项时,就叫做递归公式。递归程序设计的公式化方法是一种简单而有效的设计思想,它把程序设计和程序理解的难点都集中到递归公式上。由递归公式设计出的程序具有标准的分支结构,编写和理解都要简单的多
程序调用自身的编程技巧称为递归( recursion)。递归做为一种算法在程序设计语言中广泛应用。 一个过程或函数在其定义或说明中有直接或间接调用自身的一种方法,它通常把一个大型复杂的问题层层转化为一个与原问题相似的规模较小的问题来求解,递归策略只需少量的程序就可描述出解题过程所需要的多次重复计算,大大地减少了程序的代码量。递归的能力在于用有限的语句来定义对象的无限集合。一般来说,递归需要有边界条件、递归前进段和递归返回段。当边界条件不满足时,递归前进;当边界条件满足时,递归返回。
递归,就是在运行的过程中调用自己。
构成递归需具备的条件:
1,子问题须与原始问题为同样的事,且更为简单;
2,不能无限制地调用本身,须有个出口,化简为非递归状况处理。
在数学和计算机科学中,递归指由一种(或多种)简单的基本情况定义的一类对象或方法,并规定其他所有情况都能被还原为其基本情况。
递推公式
如果数列{an}的第n项与它前一项或几项的关系可以用一个式子来表示,那么这个公式叫做这个数列的递推公式。
由递推公式写出数列的方法:
1,根据递推公式写出数列的前几项,依次代入计算即可
2,若知道的是末项,通常将所给公式整理成用后面的项表示前面的项的形式。
一阶二次递归数列 的题型 方法!额 可以顺便讲下二阶线性递归数列么?
一阶二次递归数列:
二次递归数列不具有普遍的求通项的方法,只有个别情况可解
例如:
(一)换元法
递推式:
a(n+1)=2*an^2-1
1)当|a1|=1时,显然有an=1(n>=2,n∈N*)
2)当|a1|1时
令a1=(t+1/t)/2
显然,由数学归纳法可证明
an=(t^(2^(n-1))+1/(t^(2^(n-1)))/2
变式1
递推式:
a(n+1)=an^2-2
1)当|a1|=2时,显然有an=2(n>=2,n∈N*)
2)当|a1|2时
令a1=t+1/t
显然,由数学归纳法可证明
an=t^(2^(n-1))+1/(t^(2^(n-1))
变式2
递推式:
a(n+1)=((an+1)/2)^0.5
(a1>=0)
1)当a1=1时,显然有an=1(n>=2,n∈N*)
2)当a11时
令a1=(t+1/t)/2
显然,由数学归纳法可证明
an=(t^(2^(1-n))+1/(t^(2^(1-n)))/2
变式3
递推式:
an=(a(n-1)+2)^0.5
(a1>=0)
1)当a1=2时,显然有an=2(n>=2,n∈N*)
2)当a12时
令a1=t+1/t
显然,由数学归纳法可证明
an=t^(2^(1-n))+1/(t^(2^(1-n))
(二)配方法
递推式:
a(n+1)=A*an^2+B*an+C
且A、B、C满足B^2-4*A*C=2B,
a1=D
A,B,C,D为常数,A不为0
则有a(n+1)+B/(2A)=A*(an+B/(2A))^2
两边取对数,令xn=ln(an+B/(2A))
则有x(n+1)=2*xn+ln(A)
这样即转化成了一阶常系数线性递推数列.
变式:
递推式:
a(n+1)=A*an^2+B*an+C
A,B,C为常数,A不为0
可利用配方法,将其转化为
a(n+1)+B/(2A)=A*(an+B/(2A))^2+C+B/(2A)-(B^2)/(4*A)
不妨设
xn=an+B/(2A)
C+B/(2A)-(B^2)/(4*A)=-P
若A>0,P>0
即转化为
x(n+1)=A*xn^2-P
若
满足
AP=2
则可化为
A*x(n+1)=(A*xn)^2-2
接下来即可用换元法解决
二阶线性递归数列:
如果是二阶常系数线性递归数列的话,存在通解(如果系数不是常数那就很麻烦,也只有个别情况下可解,我只给出二阶常系数线性递归数列的解法)
a(n+2)=p*a(n+1)+q*an+f(n),即为二阶常系数线性递归数列
如果f(n)=0,称为二阶常系数齐次线性递归数列
对于二阶常系数齐次线性递归数列
递推式:
a(n+2)=p*a(n+1)+q*an
(n∈N*,p,q为常数)
1)待定系数法
a(n+2)=p*a(n+1)+q*an
可转化为等比数列:
a(n+2)-α*a(n+1)=β*(a(n+1)-α*an)
和
a(n+2)-β*a(n+1)=α*(a(n+1)-β*an)
其中α+β=A
α*β=-B
2)特征根法
a(n+2)=p*a(n+1)+q*an
其特征方程为x^2-p*x-q=0
i.若其有两个不相等的根(称作特征根)α、β
则an=A*α^n+B*β^n
其中常数A、B的值由初始值a1、a2的值确定.
ii.若其有两个相等的根α
则an=(A*n+B)*α^n
其中常数A、B的值由初始值a1、a2的值确定.
最终可得:
当{an}有两个不等的特征根为根α,β时
an=((a2-β*a1)/(α-β))*α^(n-1)-((a2-β*a1)/(α-β))*β^(n-1)
当特征根为重根α时
an=((a2-a1*α)*n+2*a1*α-a2)*α^(n-2)
当f(n)不为0时
a(n+2)=p*a(n+1)+q*an+f(n)
利用待定系数法,将f(n)分配入各单项式,使之满足:
g(n+2)+f(n)=p*g(n+1)+q*g(n)
这个g(n)称为特解
(当然前提是f(n)表达式不过于复杂,否则的话非常麻烦)
这样,令bn=an+g(n)
原递推式化为
b(n+2)=p*b(n+1)+q*bn
bn称为通解
最后an=bn-g(n)
即得到答案
递归数列特征方程的推导过程
a(n+2)=p*a(n+1)+q*an
其特征方程为x^2-p*x-q=0
i.若其有两个不相等的根(称作特征根)α、β
则an=A*α^n+B*β^n
其中常数A、B的值由初始值a1、a2的值确定.
ii.若其有两个相等的根α
则an=(A*n+B)*α^n
其中常数A、B的值由初始值a1、a2的值确定.
最终可得:
当{an}有两个不等的特征根为根α,β时
由
a(n+2)-α*a(n+1)=β^(n-1)*(a2-α*a1)
a(n+2)-β*a(n+1)=α^(n-1)*(a2-β*a1)
得
an=((a2-β*a1)/(α-β))*α^(n-1)-((a2-β*a1)/(α-β))*β^(n-1)
或由
A*α+B*β=a1
A*α^2+B*β^2=a2
可得
A=(a2-β*a1)/(α^2-α*β)
B=(a2-β*a1)/(β^2-α*β)
得
an=((a2-β*a1)/(α-β))*α^(n-1)+((a2-β*a1)/(β-α))*β^(n-1)
当特征根为重根α时
由
an-α*a(n-1)=α^(n-2)*(a2-α*a1)
α*a(n-1)-α^2*a(n-2)=α^(n-2)*(a2-α*a1)
…
α^(n-2)*a2-α^(n-1)*a1=α^(n-2)*(a2-α*a1)
an-α^(n-1)*a1=(n-1)*α^(n-2)*(a2-α*a1)
得
an=((a2-a1*α)*n+2*a1*α-a2)*α^(n-2)
或由
(A+B)*α=a1
(2*A+B)*α^2=a2
可得
A=(a2-a1*α)/(α^2)
A=(2*a1*α-a2)/(α^2)
得
((a2-a1*α)*n+2*a1*α-a2)*α^(n-2)
由于
α+β=A
α*β=-B
由韦达定理,可构造一元二次方程
x^2-p*x-q=0
此即为二阶常系数齐次线性递推数列
a(n+2)=p*a(n+1)+q*an
的特徵方程
特殊的,当二阶常系数齐次线性递推数列
a(n+2)=p*a(n+1)+q*an
的特徵根为重根α=1时
即p=2,q=-1
a(n+2)=2*a(n+1)-an
此时,二阶常系数齐次线性递推数列
a(n+2)=2*a(n+1)-an
为等差数列
递归数列中特征函数递减为什么数列没单调性
函数y=f(x)是递减函数,那么对定义域内任意两个值x1,x2,当x1<x2时,一定有f(x1)>f(x2)。
对于数列{an},满足a(n+1)=f(an),如果条件an<a(n+1)成立,那么一定有f(an)>f(a(n+1))。
即a(n+1)>a(n+2),从而又可推出a(n+2)<a(n+3),...这是一个摆动数列,所{an}不具有单调性。
勒维连续定理
如果两个随机变量具有相同的特征函数,那么它们具有相同的概率分布; 反之, 如果两个随机变量具有相同的概率分布, 它们的特征函数也相同(显然)。
独立随机变量和的特征函数等于每个随机变量特征函数的乘积。
什么是递归数列
递归数列
recursive quence
一种用归纳方法给定的数列。例如,等比数列可以用归纳方法来定义,先定义第一项 a1 的值( a1 ≠ 0 ),对 于以后的项 ,用递推公式an+1=qan (q≠0,n=1,2,…)给出定义。一般地,递归数列的前k项a1,a2,…,ak为已知数,从第k+1项起,由某一递推公式an+k=f(an,an+1,…,an+k-1) ( n=1,2,…)所确定。k称为递归数列的阶数。例如 ,已知 a1=1,a2=1,其余各项由公式an+1=an+an-1(n=2,3,…)给定的数列是二阶递归数列。这是斐波那契数列,各项依次为 1 ,1 ,2 ,3,5 ,8 ,13 ,21 ,…,同样 ,由递归式an+1-an =an-an-1( a1,a2 为已知,n=2,3,… ) 给定的数列,也是二阶递归数列,这是等差数列。