Recurrence

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 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)。

演算法(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³)。

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

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  
  ^^^^^      ^^^^^      ^^^^^
    0        F(1)        F(2)

luogu P4451

Fibonacci Number Test

http://www.geeksforgeeks.org/check-number-fibonacci-number/

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

https://www.cut-the-knot.org/arithmetic/algebra/FibonacciGCD.shtml

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)

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

UVa 763 948

Fibonacci Convolution

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

微分不動點/輾轉相除法

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

Pisano Period

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

luogu P4000

Benford's Law

http://www.maths.surrey.ac.uk/hosted-sites/R.Knott/Fibonacci/fibmaths.html

Lucas Sequence

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

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

Lucas Sequence

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

Ulam Sequence

Ulam Sequence

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

Skolem–Mahler–Lech Theorem

https://en.wikipedia.org/wiki/Skolem–Mahler–Lech_theorem