離散數學/遞迴

在本節中，我們將探討一些數學過程，這些過程的核心是遞迴的基本性質。

什麼是遞迴？

簡單來說，遞迴就是用自身來描述一個動作的過程。這可能聽起來有點奇怪，但一旦你理解了，它就是一種表達某些概念的極其強大的方法。

讓我們看一些例子，讓事情更清晰。

指數

當我們計算一個指數，比如x³時，我們將x自乘三次。如果我們有x⁵，我們將x自乘五次。

然而，如果我們想要指數的遞迴定義，我們需要用自身來定義取指數的操作。因此我們注意到，例如x⁴與x³ × x相同。但什麼是x³？x³與x² × x相同。我們可以繼續以這種方式進行，直到x⁰=1。那麼我們一般能說些什麼呢？遞迴地，

xⁿ = x × (x^n-1)

以及

x⁰=1

我們需要第二個事實，因為如果我們繼續使用負指數，定義將不再有意義，我們將無限地繼續下去！

遞迴定義

將問題簡化為相同問題，但輸入更小。例如

            a power n
            2 power 4
   the recursion(smaller inputs) of this function is = 2.2.2.2.1
   for this we declare some recursive definitions 
  a=2
  n=4
  f(0)=1
  f(1)=2
  f(2)=2
  f(3)=2
  f(4)=2
  for this recursion we form a formula f(n)= a.f(n-1)
  by putting these smaller values we get the same answer.

遞推關係

在數學中，我們可以建立遞迴函式，這些函式依賴於其先前的值來建立新的值。我們通常稱這些為遞推關係。

例如，我們可以有函式 :f(x)=2f(x-1)，其中f(1)=1。如果我們計算一些f的值，我們會得到

1, 2, 4, 8, 16, ...

然而，這個數字序列對你來說應該很熟悉！這些值與函式2^x相同，其中x = 0、1，依此類推。

我們所做的是找到一個非遞迴函式，該函式與遞迴函式具有相同的數值。我們稱之為求解，也稱為x'to sup，其值為0，依此類推。

線性遞推關係

我們將特別關注一種被稱為線性的遞推關係。

這是一個線性遞推關係的例子

f(x)=3f(x-1)+12f(x-2)，其中f(0)=1，f(1)=1

我們通常使用a_n表示a(n)，而不是寫f(x)，但這些表示法是完全可以互換的。

注意，線性遞推關係應該始終有終止情況，否則我們將無法計算f(2)，例如，因為如果我們沒有定義f(1)，它將是什麼呢？當我們談論線性遞推關係時，這些終止情況被稱為初始條件。

一般來說，線性遞推關係的形式為

a_n=A₁a_n-1 + A₂a_n-2 + ... + A_ja_n-j

其中f(t₁)=u₁，f(t₂)=u₂，...，f(t_j)=u_j作為初始條件。

數字j很重要，它被稱為線性遞推關係的階。請注意，我們始終至少需要j個初始條件才能使遞推關係有意義。

回顧上一節，我們看到可以找到一個非遞迴函式（一個解），它將取與遞推關係本身相同的數值。讓我們看看如何求解一些線性遞推關係 - 我們可以用一種非常系統的方法來做到這一點，但我們首先需要建立幾個定理。

求解線性遞推關係

解的和

這個定理說

如果f(n)和g(n)都是線性遞推關係a_n=Aa_n-1+Ba_n-2的解，那麼它們的和也是一個解。

這是真的，因為如果我們將遞推關係重新排列為a_n-Aa_n-1-Ba_n-2=0，並且我們知道f(n)和g(n)是解，因此，在代入遞推關係後，我們有

f(n)-Af(n-1)-Bf(n-2)=0

g(n)-Ag(n-1)-Bg(n-2)=0

如果我們將和f(n)+g(n)代入遞推關係，我們將得到

(f(n)+g(n))-A(f(n-1)+g(n-1))-B((f(n-2)+g(n-2))=0

展開後，我們有

f(n)-Af(n-1)-Bf(n-2)+g(n)-Ag(n-1)-Bg(n-2)

但使用我們首先建立的兩個事實，這與

0+0=0

因此，f(n)+g(n)確實是遞推關係的解。

通解

下一個定理指出

假設我們有一個二階線性遞推關係，a_n-Aa_n-1-Ba_n-2=0，並給出初始條件。

那麼γrⁿ是遞推關係的解，其中r是二次方程

x²-Ax-B=0

的解，我們稱之為特徵方程。
我們猜測（為什麼並不重要，現在就接受它）γrⁿ可能是一個解。我們可以證明，如果（且僅當）它解出特徵方程，它就是一個解 ;

我們將γrⁿ（r不等於零）代入遞推關係中，得到

γrⁿ-Aγr^n-1-Bγr^n-2=0

然後用最右邊的項γr^n-2進行因式分解

γr^n-2(r²-Ar-B)=0

我們知道r不等於零，因此r^n-2永遠不可能為零。因此，r²-Ar-B必須為零，因此，γrⁿ（其中r是r²-Ar-B=0的解）確實是線性遞推關係的解。請注意，我們可以輕鬆地將這個事實推廣到更高階的線性遞推關係。

這是從哪裡來的？為什麼它有效（除了死板的證明）？這裡有一個更直觀的（但數學上不那麼嚴謹）的解釋。
求解特徵方程找到一個滿足線性遞推關係的函式，並且方便地不需要對所有n項進行求和來找到第n項。
我們需要 : 一個函式F(n)，使得F(n) = A * F(n-1) + B * F(n-2)
我們求解 : x² = A* x + B，並將其解稱為r。可能有多個r值，如下面的例子所示！
我們得到 : 一個函式F(n) = rⁿ，它滿足F(n) = A * F(n-1) + B * F(n-2)
讓我們檢查一下：rⁿ = A*r^n-1 + B*r^n-2 是否成立？將兩邊都除以r^n-2，我們會得到r² = A*r + B，這必須成立，因為r是x² = A* x + B的解

為什麼 γ*rⁿ 也滿足遞迴關係？ 如果 F(n)=rⁿ 是一個解，也就是說，rⁿ-A*r^n-1-B*r^n-2=0，那麼 F(n)=γrⁿ 當然也是一個解，因為 γrⁿ-A*γr^n-1-B*γr^n-2=γ(rⁿ-A*r^n-1-B*r^n-2)=0。

因為我們有一個二階遞迴關係，所以通解是兩個解的和，這兩個解對應特徵方程的兩個根。假設這兩個根是 r 和 s。通解是 C(rⁿ)+D(sⁿ)，其中 C 和 D 是常數。我們可以透過關係的兩個初始值（必須有兩個才能找到 C 和 D）來求出它們。將這些值代入通解，將得到兩個方程，我們可以（希望）解出它們。

例子

讓我們透過一個例子來了解如何使用上述定理來解決線性遞迴關係。考察這裡給出的函式 a(n)

a(n)=a(n-1)+2a(n-2)

這個遞迴關係的特徵方程是

r²-r-2 = 0，如上所示，因為 A=1 且 B=2

即 (r-2)(r+1)=0，它的根為 2，-1。

所以通解是 C(2ⁿ)+D(-1)ⁿ。

為了找到這個特定情況下的 C 和 D，我們需要兩個初始值，假設 a(1) = 0 且 a(2) = 2。這些值會得到一個由兩個方程組成的系統
0 = C(2¹)+D(-1)¹
2 = C(2²)+D(-1)²
解這兩個方程得到：C = 1/3，D = 2/3，所以解是 1/3*(2ⁿ)+2/3*(-1)ⁿ。