什么是遞歸數列？
遞歸數列
是一種用歸納方法給定的數列。
例如，等比數列可以用歸納方法來定義，先定義第一項
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，… ) 給定的數列，也是二階遞歸數列，這是等差數列。
