Recurrence

Recurrence

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

recursive function:
{ f(0) = 1
{ f(n) = 2 f(n-1)² - 4

recursive sequence:
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 ...                :      :      :    :

從頭開始一項一項算。時間複雜度O(K + (N-K)K),通常簡單寫成O(NK)。

Fibonacci Sequence

Fibonacci Sequence

1 1 2 3 5 8 13 ...

UVa 495 11582

Fibonacci Base(Zeckendorf's Theorem)

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

UVa 763 948

GCD Distributivity

fib(gcd(a,b)) = gcd(fib(a),fib(b))

Fibonacci Convolution

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

Generating Function / Characteristic Equation

(1 1 2 3 5 ...)  ←→  1/(1-x-x²)

http://www.cut-the-knot.org/blue/GeneratingFunctionsFromRecurrences.shtml

Binet Formula

       αⁿ - βⁿ    1  / / 1+√̅5 \ⁿ  / 1-√̅5 \ⁿ \
f(n) = ――――――― = ――― ⎸ ⎸――――――⎹ - ⎸――――――⎹  ⎹
         √̅5      √̅5  \ \   2  /   \   2  /  /
  0x⁰ + 1x¹ + 1x² + 2x³ + 3x⁴ + 5x⁵ + 8x⁶ + ...

    1
= ――――――                generating function
  1-x-x²

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

Golden Ratio

(1 ± √5) / 2

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

Fibonacci Number Test

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

Cassini Identity

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

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

Pisano Period

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

luogu P3986

Lucas Sequence

Lucas Sequence

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

Ulam Sequence

Ulam Sequence

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