Recurrence

「遞迴數列」。以遞迴函數得到的數列。

recursive function:       |  f(0) = 1
⎰ f(0) = 1                |  f(1) = 2 f(0)² - 4 = -2
⎱ f(n) = 2 f(n-1)² - 4    |  f(2) = 2 f(1)² - 4 = 4
                          |  f(3) = 2 f(2)² - 4 = 28
recursive sequence:       |  f(4) = 2 f(3)² - 4 = 1564
1 -2 4 28 1564 ......     |    :        :          :

數學當中，遞迴數列與遞迴函數一體兩面，同稱Recurrence。計算學當中，則是各飾一角。本文為了方便講解，暫將Recurrence視作遞迴數列。

Linear Recurrence（Linear Feedback Shift Register）

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

⎧ f(0) = c₀
⎨ f(1) = c₁
⎪   :     :
⎩ f(n) = a₁ f(n-1) + a₂ f(n-2) + ... + aₖ f(n-k)

知名範例是Fibonacci Sequence。往前兩項、係數皆是一。

recursive function:       |  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
recursive sequence:       |  f(5) = f(4) + f(3) = 5
0 1 1 2 3 5 ...           |    :      :      :    :

演算法（Dynamic Programming）

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

const int N = 10; int f[N+1]; void Fibonacci_sequence() { f[0] = 0; f[1] = 1; for (int i=2; i<=N; i++) f[i] = f[i-1] + f[i-2]; }

演算法（Companion Matrix）

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

linear recursive function:
f(n+3) = 7 f(n) + 8 f(n+1) + 9 f(n+2)

companion matrix:
⎡ f(n+1) ⎤   ⎡ 0 1 0 ⎤ ⎡ f(n)   ⎤
⎢ f(n+2) ⎥ = ⎢ 0 0 1 ⎥ ⎢ f(n+1) ⎥
⎣ f(n+3) ⎦   ⎣ 7 8 9 ⎦ ⎣ f(n+2) ⎦

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

recursive function:     |  linear recursive function:
⎰ f(0) = 1              |  ⎧ f(0) = 0
⎱ f(n) = 2 f(n-1)² - 4  |  ⎨ f(1) = 1
                        |  ⎪ f(2) = 2
function compositions:  |  ⎩ f(n+3) = 7 f(n) + 8 f(n+1) + 9 f(n+2)
let g(x) = 2x² - 4      |
f(0) = 1                |  companion matrix exponentiation:
f(1) = g(1)             |  ⎡ f(n)   ⎤   ⎡ 0 1 0 ⎤ⁿ ⎡ f(0) ⎤
f(2) = g(g(1))          |  ⎢ f(n+1) ⎥ = ⎢ 0 0 1 ⎥  ⎢ f(1) ⎥
f(3) = g(g(g(1)))       |  ⎣ f(n+2) ⎦   ⎣ 7 8 9 ⎦  ⎣ f(2) ⎦

線性遞迴函數的第N項＝同伴矩陣（轉置）的N次方。

同伴矩陣n次方，得到第n項。
⎡ f(n)   ⎤   ⎡ 0 1 0 ⎤ⁿ ⎡ f(0) ⎤   <----- f(n) is here
⎢ f(n+1) ⎥ = ⎢ 0 0 1 ⎥  ⎢ f(1) ⎥
⎣ f(n+2) ⎦   ⎣ 7 8 9 ⎦  ⎣ f(2) ⎦

同伴矩陣n-k+1次方，稍微快一點。此處k等於3。
⎡ f(n-2) ⎤   ⎡ 0 1 0 ⎤ⁿ⁻² ⎡ f(0) ⎤
⎢ f(n-1) ⎥ = ⎢ 0 0 1 ⎥    ⎢ f(1) ⎥
⎣ f(n)   ⎦   ⎣ 7 8 9 ⎦    ⎣ f(2) ⎦   <--- f(n) is here

矩陣次方有高速演算法，如同整數次方。

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

int Fibonacci_sequence(int n) { if (n < 0) return -n & 1; // 初始向量。O(K)。 // f(0) = 0 , f(1) = 1 Matrix v0(2, 1); v0[0][0] = 0; v0[0][1] = 1; // 初始向量已經有第N項 if (n < 2) return v0[0][n]; // 同伴矩陣。O(K²)。 // f(n+2) = 1 ⋅ f(n) + 1 ⋅ f(n+1) Matrix A(2, 2); A[0][0] = 0; A[0][1] = 1; A[1][0] = 1; A[1][1] = 1; // 同伴矩陣n次方。O(K³logN)。 // Matrix v(2, 1); // v = (A ^ n) * v0; // retrun v[0][0]; // 同伴矩陣n-k+1次方，稍微快一點。O(K³log(N-K))。 Matrix v(2, 1); v = (A ^ (n-1)) * v0; return v[0][1]; }

UVa 10229 10518 10655 10743 10754 10870 12653

演算法（Characteristic Polynomial）

特殊的生成函數。f(n)變成xⁿ。

linear recursive function:
f(n+3) = 9 f(n+2) + 8 f(n+1) + 7 f(n)

generating function:
xⁿ⁺³ = 9xⁿ⁺² + 8xⁿ⁺¹ + 7xⁿ

特殊的特徵多項式。移項、刪除變數n。

characteristic polynomial:
x³ - 9x² - 8x¹ - 7x⁰

展開最高項＝長除法求得餘數。

expand leading term:
  f(5)
= 9 f(4) + 8 f(3) + 7 f(2)
= 89 f(3) + 79 f(2) + 63 f(1)
= 880 f(2) + 775 f(1) + 623 f(0)

divide characteristic polynomial:
  (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」。

Fibonacci Sequence

0 1 1 2 3 5 8 ...

⎧ f(0) = 0
⎨ f(1) = 1
⎩ f(n) = f(n-1) + f(n-2)

UVa 495 11582 luogu P3986

Generating Function / Characteristic Equation

(0 1 1 2 3 5 8 ...)  ←—→  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)       when n ≥ 2
f(n) - f(n-1) - f(n-2) = 0   when n ≥ 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²)

Binet Formula

       αⁿ - βⁿ    1  ⎛⎛  1+√5̅  ⎞ⁿ  ⎛  1-√5̅  ⎞ⁿ⎞
f(n) = ——————— = ——— ⎜⎜ —————— ⎟ - ⎜ —————— ⎟ ⎟
         √5̅      √5̅  ⎝⎝    2   ⎠   ⎝    2   ⎠ ⎠

  0x⁰ + 1x¹ + 1x² + 2x³ + 3x⁴ + 5x⁵ + 8x⁶ + ...

    x
= ——————
  1-x-x²

        x               quadratic factoring
= ————————————          ⎰ α = (1 + √5̅) / 2
  (1-αx)(1-βx)          ⎱ β = (1 - √5̅) / 2

  1/(α-β)   1/(β-α)
= ——————— + ———————     partial fraction expansion
   1-αx      1-βx  

   1    1     1    1 
= ——— ———— - ——— ————
  √5̅  1-αx   √5̅  1-βx

   1                                   1
= ——— ((αx)⁰ + (αx)¹ + (αx)² + ...) - ——— ((βx)⁰ + (βx)¹ + (βx)² + ...)
  √5̅                                  √5̅

  α⁰-β⁰      α¹-β¹      α²-β²
= ————— x⁰ + ————— x¹ + ————— x² + ...
   √5̅         √5̅         √5̅  
  ^^^^^      ^^^^^      ^^^^^
  f(0)       f(1)       f(2)

luogu P4451

Fibonacci Number Test

Golden Ratio

         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/φ = 0     when n → ∞
φ² - φ - 1 = 0
φ = (1 ± √5̅) / 2
φ = (1 + √5̅) / 2     since φ > 0

Additive Law

爬樓梯問題：每步一階或兩階，爬上第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)

GCD Distributive Law

gcd(f(n), f(n-1)) = 1
fib(gcd(a,b)) = gcd(fib(a),fib(b))
f(n)|f(m) when n|m

Fibonacci Base（Zeckendorf's Theorem）

UVa 763 948

微分不動點/輾轉相除法

微分不動點是0數列。微分之後左移一項是倍增數列。微分之後左移兩項是Fibonacci數列。位移的傅立葉轉換是角加速度。

Pisano Period

https://en.wikipedia.org/wiki/Pisano_period

luogu P4000

Benford's Law

Fibonacci Convolution

斐波那契卷積可以用來解決哥德巴赫猜想與黎曼猜想。我已找到一個精妙的證明，而硬碟沒有足夠的空位寫下。

Fibonacci Sequence

Vajda's Identity：f(n+i)f(n+j) - f(n)f(n+i+j) = (-1)ⁿf(i)f(j)

Catalan's Identity：f(n)² - f(n-i)f(n+i) = (-1)ⁿ⁻ⁱf(i)

Cassini's Identity：f(n-1)f(n+1) - f(n)² = (-1)ⁿ

Pell Sequence

Lucas Sequence

Ulam Sequence

Skolem–Mahler–Lech Theorem

Linear Difference Equations

等號左邊是相鄰兩項的差，等號右邊是索引值更小的項（否則無窮遞迴）。

{ x(n+1) - x(n) = a0 x(n) + a1 x(n-1) + ... + b0 y(n) + b1 y(n-1) + ...
{ y(n+1) - y(n) = c0 x(n) + c1 x(n-1) + ... + d0 y(n) + d1 y(n-1) + ...

稍微移項，其實就是遞迴函數。

{ x(n+1) = a0 x(n) + a1 x(n-1) + ... + b0 y(n) + b1 y(n-1) + ...
{ y(n+1) = c0 x(n) + c1 x(n-1) + ... + d0 y(n) + d1 y(n-1) + ...

方程組化作方程式，事情就解決了。

{ xn+1 = a11 xn + a12 yn
{ yn+1 = a21 xn + a22 yn

xn+2 = a11 xn+1 + a12 yn+1
     = a11 xn+1 + a12 (a21 xn + a22 yn)
     = a11 xn+1 + a12 a21 xn + a12 a22 yn
     = a11 xn+1 + a12 a21 xn + a22 (xn+1 - a11 xn)
     = (a11 + a12) xn+1 + (a12 a21 - a22 a11) xn

穩態x̅ = xn = xn+1 = xn+2 = ...

x̅ = (a11 + a12) x + (a12 a21 - a22 a11) x
x̅ = 0

Linear Differential Equation

luogu P6613

Polynomial Sequence

Discrete Derivative

高階微分可以改變底數。

difference operator:
Δa(n) = a(n+1) - a(n)

Δᵏa(n) = sum (-1)ⁱ C(k,i) a(n+k-i) = sum (-1)ᵏ⁻ⁱ C(k,i) a(n+i) 
        i=0⋯k                       i=0⋯k

Δ(x³) = (x+1)³ - x³ = 3x² + 3x + 1     let a(x) = x³

Δᵏ(xⁿ) = sum (-1)ⁱ C(k,i) (x+k-i)ⁿ
        i=0⋯k

derangement number:
D(n) = sum (-1)ⁿ⁻ⁱ C(n,i) i!
      i=0⋯n

D(n) = Δⁿ(x!) at x = 0
     = Δⁿ(0!)

shift operator: E

Continuous Derivative

d/dx(xⁿ) = n xⁿ⁻¹

L'Hôpital's rule: a/b = a′/b′
https://en.wikipedia.org/wiki/L'Hôpital's_rule

Hasse–Teichmüller Derivative

Dᵏ(xⁿ) = C(n,k) xⁿ⁻ᵏ
https://en.wikipedia.org/wiki/Hasse_derivative

Umbral Derivative

Dᵏ(Bₙ(x)) = sum Bₙ₋ₖ(x) C(n,k) xᵏ
           k=0⋯n

Appell sequence        d/dx pₙ(x) = n pₙ₋₁(x)
Bernoulli polynomial   ΔBₙ(x) = n xⁿ⁻¹
Euler polynomial       ΔEₙ(x) = 2(xⁿ - Eₙ(x))

https://en.wikipedia.org/wiki/Appell_sequence
https://en.wikipedia.org/wiki/Bernoulli_polynomials#Another_explicit_formula
https://planetmath.org/eulerpolynomial
https://en.wikipedia.org/wiki/Umbral_calculus
https://blog.csdn.net/EI_Captain/article/details/118317406

https://en.wikipedia.org/wiki/Bernoulli_number
https://en.wikipedia.org/wiki/Bernoulli_polynomials
http://luschny.de/math/zeta/The-Bernoulli-Manifesto.html

Polar Derivative

Dₖ P(x) = n P(x) + (k-x) P′(x)

Apolar polynomials
⎰ p(x) = a₀x⁰ + ... + aₙxⁿ
⎱ q(x) = b₀x⁰ + ... + bₙxⁿ
where        a₀bₙ           a₁bₙ₋₁                aₙb₀
      (-1)⁰ —————— + (-1)¹ —————— + ... + (-1)ⁿ —————— = 0
            C(n,0)         C(n,1)               C(n,n)

https://mathoverflow.net/questions/378463/