# Recurrence Relations

$$
c_na_n+c_{n-1}a_{n-1}+...+c_{n-k}a_{n-k}=f(n),\ n\ge k
$$

$k$ 是正整數，$c_n$ 跟 $c_{n-k}$ 是非 0 常數，中間的 $c_i$ 是任意常數，$a_n$ 是某個 discrete numeric function。
>$c_n=0$ 或 $c_{n-k}=0$ 就會退化了

那麼 $f(n)$ 就叫做 **linear recurrence relation with constant coefficients of order k**。

如果 $f(n)=0$ 那麼他是 **homogeneous**，反之就是 **nonhomogeneous**

# First-Order Linear Homogeneous Recurrence Relations with Constant Coefficients

型如：

$$
a_n=c\cdot a_{n-1},\ n\ge 1
$$

那麼可以得知：

$$
a_n=c^n\cdot a_0
$$

# Second-Order Linear Homogeneous Recurrence Relations with Constant Coefficients

型如：

$$
c_na_n+c_{n-1}a_{n-1}+c_{n-2}a_{n-2}=0,\ n\ge 2
$$

我們可以**通靈知道**這種形式有個通解：

$$
a_n=c\cdot r^n,\ \ c\ne0,\ r\ne0
$$

把他代回去會得到：

$$
\displaylines{
c_n(c\cdot r^n)+c_{n-1}(c\cdot r^{n-1})+c_{n-2}(c\cdot r^{n-2})=0\\
c_nr^2+c_{n-1}r+c_{n-2}=0
}
$$

$c_nr^2+c_{n-1}r+c_{n-2}=0$ 這東西叫做 **characteristic equation**，並且他的兩個根 $r_1$, $r_2$叫做 **characteristic roots**。

$$
r=\frac{-c_{n-1}\pm\sqrt{c_{n-1}^2-4c_{n}c_{n-2}}}{2c_n}
$$

## Case 1 兩個相異==實根==

此時通解為：

$$
a_n=c_1r_1^n+c_2r_2^n
$$

$c_1$ 跟 $c_2$ 可以藉由邊界情形($a_0$ 跟 $a_1$ 的值)解出來。

### 示範例子

$$
a_n+a_{n-1}-6\cdot a_{n-2}=0,\ n\ge 2,\ a_0=1,\ a_1=2
$$

特徵方程式為 $r^2+r-6=0$，瞪眼法可以看出 -3 跟 2 兩個根，所以通解是

$$a_n=c_12^n+c_2(-3)^n$$

透過邊界條件得知：

- $1=c_1+c_2$
- $2=2c_1-3c_2$
- $c_2=0,\ c_1=1$

也就是：

$$a_n=2^n$$

你可以代回去，會驚人的發現確實滿足那個遞迴式子。

### 著名例子 費氏數列

$$
a_n=a_{n-1}+a_{n-2},\ n\ge 2,\ a_0=0,\ a_1=1
$$

換個位子 $a_n-a_{n-1}-a_{n-2}=0$，直接套用公式解：

$$
r=\frac{1\pm\sqrt{5}}{2}
$$

解通解：

$$
a_n=c_1\left(\frac{1+\sqrt{5}}{2}\right)^n+c_2\left(\frac{1-\sqrt{5}}{2}\right)^n
$$

- $c_1+c_2=0$
- $\frac{c_1+c_2+(c_1-c_2)\sqrt{5}}{2}=1$
- $\frac{c_1+c_2+(c_1-c_2)\sqrt{5}}{2}=\frac{(c_1-c_2)\sqrt{5}}{2}=1$
- $c_1-c_2=\frac{2\sqrt{5}}{5}$
- $c_1=\frac{1}{\sqrt{5}},\ c_2=\frac{-1}{\sqrt{5}}$

於是就得到大名鼎鼎的費氏數列的通項表達式：

$$
a_n=\frac{1}{\sqrt{5}}\left(\left(\frac{1+\sqrt{5}}{2}\right)^n-\left(\frac{1-\sqrt{5}}{2}\right)^n\right)
$$

:::warning
很多例子都可以表達出跟費氏數列一樣的關係式，但是差在 $a_0$ 跟 $a_1$ 的不同，所以這些例子的 $a_n$ 有時候會是費氏的 $a_{n+i}$
:::

## Case 2 兩個共軛==虛根==

$$
\displaylines{
r_1=x+iy=\sqrt{x^2+y^2}(\cos\theta+i\sin\theta)\\
r_2=x-iy=\sqrt{x^2+y^2}(\cos\theta-i\sin\theta)\\
}
$$

先回憶棣美弗定理：

$$
\displaylines{
z=r(\cos\theta\pm i\sin\theta)\\
z^n=r^n(\cos n\theta\pm i\sin n\theta)\\
}
$$

所以這時對於通解就可以換成：

$$
\displaylines{
a_n=c_1r_1^n+c_2r_2^n=c_1r^n(\cos n\theta+i\sin n\theta)+c_2r^n(\cos n\theta- i\sin n\theta)\\
a_n=r^n(k_1\cos n\theta+k_2\sin n\theta)\\
k_1=c_1+c_2,\ \ k_2=(c_1-c_2)i
}
$$

這時候解 $k_1$ 跟 $k_2$ 就足已：)。

## Case ==重根==

通解為：

$$
a_n=c_1r^n+n\cdot c_2r^n
$$

# Linear Homogeneous Recurrence Relations of Higher Order with Constant Coefficients

:::info
就是 $a_n$ 跟 $a_{n-3}$ 以後的項有關係。
:::

令 $a_n=cr^n$。

那麼對於 $r_1$ 到 $r_k$ 個相異根，通解可以表示成：

$$
a_n=c_1r_1^n+c_2r_2^n+...c_1r_k^n
$$

但如果某個根是重根，假設 $m$ 是他的 multiplicity 重數，那麼他的部分為：

$$
c_0n^0r^n+c_1n^1r^n+...+c_{m-1}n^{m-1}r^n
$$

# Linear Nonhomogeneous Recurrence Relations

fn 不等於 0 的情形

通解是齊次解(fn=0的解，但是代回去要補常數)+特解(代入原關係滿足等式的解，通常只能從 fn 的形式去猜)

1. 先猜特解，找出特解
2. 齊解跟特解帶回通解，解出齊解的常數

或者可以用展開的方法求出來。

然後一階跟二階如果 fn 是某個形式會有對應的解形式

但是這些都不是重點，因為我們有個終極表

如果 fn 型如 gn，或者是多個不同 gn 乘常數相加起來

- 如果 gn **不在齊解裡面**(意思是通解常數任意調可以調出 gn)
- 那麼特解就是對應的 h(gn)，或者是 h(gn) 相加起來
- 但如果 gn 在齊解裡面
- 那麼就要把 h(gn) 乘上 n 的某次方，讓他不能被齊解湊出來

例如 fn 是一個 n 平方加 n 指數，然後齊解是 n 平方 + n 指數 + n 乘 n 指數

- fn 是由兩個 gn 組合，這兩個 gn 對應的 hgn 是 (a+bn+cn^2) 跟 指數
- 但是因為 n 平方在齊解裡面，所以要想辦法不讓 (a+bn+cn^2) 這坨東西可以被齊解湊出來，方法就是乘上一個 n 就好，阿要記得再補一個常數
- 指數也是同道理，並且她還要乘兩次 n

齊次解是一個任意係數的解，透過給訂的初值決定出一個特解
特解是跟初值無關的另一個特解

在用待定係數解初值無關的特解前，要先確認他跟給定初值的特解是線性無關的

像 g_n = C * 2^n 跟 p_n = A * 3^n + B * 2^n

- 通常會說 p_n 後面的 B * 2^n 跟 g_n 的 C * 2^n 重合了
- 因為你可以隨便湊係數讓兩者只差常數倍

所以簡單來說就是 + 分開的每一項都要不一樣

# 生成函數法

除了上面的待定係數法來解高階，我們還有另一個工具就是用生成函數法。

原式令為 n 到 n-r 項的關係，我們把 n 到 n-r 項當作生成函數的事件。

原式兩邊同乘 x^n ，整理一下，然後讓兩邊取 n 到 n-r 項的 n 從 k 跑到無限大的級數和
k 就是挑滿足遞迴式的最小值，通常是 r；例如 n 跟 n-1 項的遞迴式，就是從 1 跑到無限大

然後就可以把級數和換成用生成函數扣掉某些東西來表示，這時候就可以解出生成函數了

然後就可以解出要求的 an 的通解了

# Nonlinear Recurrence Relations

這個章節介紹了著名的卡塔蘭數，以及用生成係數法推導出來的過程

# Recurrence Relations with Two Indices

這個章節介紹如果序列是跟兩個 index 有關，可以怎麼解

一樣是先觀察出關係，然後使用生成係數法

# Simultaneous Linear Recurrence Relations

這個章節世界少兩個序列之間有關係，一樣是建立兩個序列的生成函數去解函數的係數得出 an 跟 bn 的值

# General First-Order Linear Recurrence Relations

一般一階線性關係的通解，會是齊解乘上另一個序列，先找出齊解後，再透過通解的形式代回去原式，展開，得到另一個序列的解，然後就可以組合出通解了