Recurrence - 演算法筆記

計算學當中，則是各飾一角。

本文為了方便講解，暫將Recurrence 視作遞迴數列。

Linear Recurrence. Linear Recurrence （ Linear Feedback Shift ... Recurrence Recurrence 「遞迴數列」。

以遞迴函數得到的數列。

recursivefunction:|f(0)=1 {f(0)=1|f(1)=2f(0)²-4=-2 {f(n)=2f(n-1)²-4|f(2)=2f(1)²-4=4 |f(3)=2f(2)²-4=28 recursivesequence:|f(4)=2f(3)²-4=1564 1-24281564......|::: 數學當中，遞迴數列與遞迴函數一體兩面，同稱Recurrence。

計算學當中，則是各飾一角。

本文為了方便講解，暫將Recurrence視作遞迴數列。

LinearRecurrence LinearRecurrence（LinearFeedbackShiftRegister） 「線性遞迴數列」。

以線性遞迴函數得到的數列。

{f(0)=c₀ {f(1)=c₁ {:: {f(n)=a₁f(n-1)+a₂f(n-2)+...+aₖf(n-k) 知名範例是FibonacciSequence。

往前兩項、係數皆是一。

recursivefunction:|f(0)=0 {f(0)=0|f(1)=1 {f(1)=1|f(2)=f(1)+f(0)=1 {f(n)=f(n-1)+f(n-2)|f(3)=f(2)+f(1)=2 |f(4)=f(3)+f(2)=3 recursivesequence:|f(5)=f(4)+f(3)=5 011235...|:::: 演算法（DynamicProgramming） 從頭開始一項一項算。

線性遞迴函數K項，求數列第N項，時間複雜度O(K+(N-K)K)，通常簡單寫成O(NK)。

constintN=10; intf[N+1]; voidFibonacci_sequence() { f[0]=0; f[1]=1; for(inti=2;i<=N;i++) f[i]=f[i-1]+f[i-2]; } 演算法（CompanionMatrix） 線性函數＝矩陣。

線性遞迴函數＝同伴矩陣（轉置）。

linearrecursivefunction: f(n+3)=7f(n)+8f(n+1)+9f(n+2) companionmatrix: [f(n+1)][010][f(n)] [f(n+2)]=[001][f(n+1)] [f(n+3)][789][f(n+2)] 遞迴函數＝函數複合許多次。

線性遞迴函數＝線性函數複合許多次＝同伴矩陣（轉置）次方。

recursivefunction:|linearrecursivefunction: {f(0)=1|{f(0)=0 {f(n)=2f(n-1)²-4|{f(1)=1 |{f(2)=2 functioncompositions:|{f(n+3)=7f(n)+8f(n+1)+9f(n+2) letg(x)=2x²-4| f(0)=1|companionmatrixexponentiation: f(1)=g(1)|[f(n)][010]ⁿ[f(0)] f(2)=g(g(1))|[f(n+1)]=[001][f(1)] f(3)=g(g(g(1)))|[f(n+2)][789][f(2)] 線性遞迴函數的第N項＝同伴矩陣（轉置）的N次方。

同伴矩陣n次方，得到第n項。

[f(n)][010]ⁿ[f(0)] 矩陣次方有高速演算法，如同整數次方。

線性遞迴函數K項，求數列第N項，需要O(log(N-K))次矩陣乘法，時間複雜度O(K²+K³log(N-K))，通常簡單寫成O(K³logN)。

此處假設矩陣相乘是O(K³)。

intFibonacci_sequence(intn) { if(n<0)return-n&1; //初始向量。

O(K)。

//f(0)=0,f(1)=1 Matrixv0(2,1); v0[0][0]=0; v0[0][1]=1; //初始向量已經有第N項 if(n<2)returnv0[0][n]; //同伴矩陣。

O(K²)。

//f(n+2)=1⋅f(n)+1⋅f(n+1) MatrixA(2,2); A[0][0]=0;A[0][1]=1; A[1][0]=1;A[1][1]=1; //同伴矩陣n次方。

O(K³logN)。

// Matrixv(2,1); // v=(A^n)*v0; // retrunv[0][0]; //同伴矩陣n-k+1次方，稍微快一點。

O(K³log(N-K))。

Matrixv(2,1); v=(A^(n-1))*v0; returnv[0][1]; } UVa10229105181065510743107541087012653 演算法（CharacteristicPolynomial） 特殊的生成函數。

f(n)變成xⁿ。

linearrecursivefunction: f(n+3)=9f(n+2)+8f(n+1)+7f(n) generatingfunction: xⁿ⁺³=9xⁿ⁺²+8xⁿ⁺¹+7xⁿ 特殊的特徵多項式。

移項、刪除變數n。

characteristicpolynomial: x³-9x²-8x¹-7x⁰ 展開最高項＝長除法求得餘數。

expandleadingterm: f(5) =9f(4)+8f(3)+7f(2) =89f(3)+79f(2)+63f(1) =880f(2)+775f(1)+623f(0) dividecharacteristicpolynomial: (x⁵) ⇒(x⁵)÷(x³-9x²-8x-7)=x²...9x⁴+8x³+7x² ⇒(9x⁴+8x³+7x²)÷(x³-9x²-8x-7)=9x...89x³+79x²+63x¹ ⇒(89x³+79x²+63x¹)÷(x³-9x²-8x-7)=89...880x²+775x¹+623x⁰ 展開第n項＝xⁿ模特徵多項式。

最後再代入實際數值。

線性遞迴函數K項，求數列第N項，使用多項式除法，時間複雜度O(K(N-K)+K)，通常簡單寫成O(NK)。

多項式除法還可以更快。

請見本站文件「Polynomial」。

FibonacciSequence FibonacciSequence 0112358... {f(0)=0 {f(1)=1 {f(n)=f(n-1)+f(n-2) UVa49511582luoguP3986 GeneratingFunction/CharacteristicEquation (0112358...)←—→x/(1-x-x²) G(x)=0x⁰+1x¹+1x²+2x³+3x⁴+5x⁵+8x⁶+... G(x)=f(0)x⁰+f(1)x¹+f(2)x²+f(3)x³+... G(x)=f(0)x⁰+f(1)x¹+[f(0)+f(1)]x²+[f(1)+f(2)]x³+... G(x)=f(0)x⁰+f(1)x¹+f(0)x²+f(1)x²+f(1)x³+f(2)x³+... G(x)=f(0)x⁰+f(1)x¹+[f(0)x²+f(1)x³+...]+[f(1)x²+f(2)x³+...] G(x)=f(0)x⁰+f(1)x¹+[G(x)x²]+[G(x)x¹-f(0)x¹] G(x)=0+x¹+[G(x)x²]+[G(x)x¹-0] G(x)=x+G(x)x+G(x)x² G(x)-G(x)x-G(x)x²=x G(x)(1-x-x²)=x G(x)=x/(1-x-x²) f(n)=f(n-1)+f(n-2)whenn≥2 f(n)-f(n-1)-f(n-2)=0whenn≥2 (G(x)-f(0)x⁰-f(1)x¹)x⁰-(G(x)-f(0)x⁰)x¹-G(x)x²=0 G(x)-G(x)x-G(x)x²=x G(x)=x/(1-x-x²) BinetFormula αⁿ-βⁿ1//1+√̅5\ⁿ/1-√̅5\ⁿ\ f(n)=―――――――=―――⎸⎸――――――⎹-⎸――――――⎹⎹ √̅5√̅5\\2/\2// 0x⁰+1x¹+1x²+2x³+3x⁴+5x⁵+8x⁶+... x =―――――― 1-x-x² xquadraticfactoring =――――――――――――{α=(1+√̅5)/2 (1-αx)(1-βx){β=(1-√̅5)/2 1/(α-β)1/(β-α) =―――――――+―――――――partialfractionexpansion 1-αx1-βx 1111 =―――――――-――――――― √̅51-αx√̅51-βx 11 =―――((αx)⁰+(αx)¹+(αx)²+...)-―――((βx)⁰+(βx)¹+(βx)²+...) √̅5√̅5 α⁰-β⁰α¹-β¹α²-β² =―――――x⁰+―――――x¹+―――――x²+... √̅5√̅5√̅5 ^^^^^^^^^^^^^^^ 0F(1)F(2) luoguP4451 FibonacciNumberTest GoldenRatio f(n)1+√̅5 φ=lim――――――=――――――=1.618... n→∞f(n-1)2 f(n)=f(n-1)+f(n-2) f(n)-f(n-1)-f(n-2)=0 f(n)/f(n-1)-1-f(n-2)/f(n-1)=0 φ-1-1/φ=0whenn→∞ φ²-φ-1=0 φ=(1±√̅5)/2 φ=(1+√̅5)/2sinceφ>0 AdditiveLaw 爬樓梯問題：每步一階或兩階，爬上第n階有幾種步法。

c(n)=c(n-1)+c(n-2) 爬上第n+m階，分成兩種情況：沒踩第n階、有踩第n階。

c(n+m)=c(n-1)c(m-1)+c(n)c(m) 爬樓梯問題的答案，右移一項，即是費氏數列。

f(n+m+1)=f(n)f(m)+f(n+1)f(m+1) 變數代換，n+1換成n。

f(n+m)=f(n-1)f(m)+f(n)f(m+1) GCDDistributiveLaw gcd(f(n),f(n-1))=1 fib(gcd(a,b))=gcd(fib(a),fib(b)) f(n)|f(m)whenn|m FibonacciBase（Zeckendorf'sTheorem） UVa763948 微分不動點/輾轉相除法 微分不動點是0數列。

微分之後左移一項是倍增數列。

微分之後左移兩項是Fibonacci數列。

位移的傅立葉轉換是角加速度。

PisanoPeriod https://en.wikipedia.org/wiki/Pisano_period luoguP4000 Benford'sLaw FibonacciConvolution 斐波那契卷積可以用來解決哥德巴赫猜想與黎曼猜想。

我已找到一個精妙的證明，而硬碟沒有足夠的空位寫下。

LucasSequence FibonacciSequence Vajda'sIdentity：f(n+i)f(n+j)-f(n)f(n+i+j)=(-1)ⁿf(i)f(j) Catalan'sIdentity：f(n)²-f(n-i)f(n+i)=(-1)ⁿ⁻ⁱf(i) Cassini'sIdentity：f(n-1)f(n+1)-f(n)²=(-1)ⁿ PellSequence LucasSequence UlamSequence UlamSequence Skolem–Mahler–LechTheorem