# 遞迴關係式

$x_{n+1} = r x_n (1 - x_n) \,$

## 解線性遞迴關係式

$a_{n}=Aa_{n-1}+Ba_{n-2} \,$

$r^{n}=Ar^{n-1}+Br^{n-2} \,$

$r^2=Ar+B \,$
$r^2-Ar-B=0 \,$

$a_n = C\lambda_1^n+D\lambda_2^n \,$

$a_n = C\lambda^n+Dn\lambda^n \,$

CD都是常數。

## 範例：斐波那契数（Fibonacci Number）

$F_{0} = 0 \,$
$F_{1} = 1 \,$
$F_{n} = F_{n-1}+F_{n-2} \,$

$F_n = {\Phi^n \over \sqrt{5}} - {(1-\Phi)^n \over \sqrt{5}}$

$F_{0} = 0 \,$
$F_{1} = 1 \,$

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89 ...

## 常系数非齐次线性递推关系

### 时域经典法求解

$\sum_{k=0}^N a_k y(n-k)=\sum_{r=0}^M b_r x(n-r)$

$\sum_{k=0}^N a_k y(n-k)=0$

$\sum_{k=0}^N a_k \alpha^{N-k}=0$

$y_h(n)=\sum_{i=1}^N C_i \alpha_i^n$

$y_h(n)=\sum_{i=1}^K n^{K-i} \alpha_1^n$

$y_p(n)=A_0 n^k + A_1 n^{k-1} + \cdots + A_k$

$y_p(n)=Aa^n$

$y_p(n)=(A_1n + A_0)a^n$

$y_p(n)=(A_r n^r + A_{r-1} n^{r-1} + \cdots + A_1 n + A_0)a^n$

### 例子

$a_{n+1} = 2a_n + 3^n + 5n\,$

$b_{n+1} = 2b_n\,$

$b_n = c_1 2^n\,$

$a_n = c_2 3^n + c_3 n + c_4\,$

$c_2 3^{n+1} + c_3 (n+1) + c_4 = 2(c_2 3^n + c_3 n + c_4) + 3^n + 5n\,$

$3c_2 = 2c_2 + 1\,$
$c_2 = 1\,$

$c_3 = 2c_3 + 5\,$
$c_3 = -5\,$

$c_3 + c_4 = 2c_4\,$
$c_4 = c_3 = -5\,$

$a_n = c_1 2^n + 3^n - 5n - 5\,$

## 與差分方程的關係

$y'(t) = f(t,y(t)), \qquad y(t_0)=y_0, \qquad\qquad$

$y_{n+1} = y_n + hf(t_n,y_n)$