# 遞迴關係式

（重定向自递回关系式

${\displaystyle x_{n+1}=rx_{n}(1-x_{n})\,}$

## 遞迴關係式的例子

### 等差數列

${\displaystyle x_{0}=1,x_{n+1}=x_{n}+2}$ 為等差數列${\displaystyle 1,3,5,7,.....}$

### 等比數列

${\displaystyle x_{0}=1,x_{n+1}=2x_{n}}$ 為等比數列${\displaystyle 1,2,4,8,.....}$

### 階乘

${\displaystyle 0!=1}$
${\displaystyle n!=n\times (n-1)!}$

### 倒数和

${\displaystyle x_{k}=x^{k}+x^{-k}}$ ，則
${\displaystyle x_{1}=x_{1}}$
${\displaystyle x_{2}=(x_{1})^{2}-2}$
${\displaystyle x_{3}=x_{1}\cdot x_{2}-x_{1}}$
${\displaystyle x_{4}=(x_{2})^{2}-2}$
${\displaystyle x_{5}=x_{2}\cdot x_{3}-x_{1}}$
${\displaystyle x_{6}=(x_{3})^{2}-2}$
${\displaystyle x_{7}=x_{3}\cdot x_{4}-x_{1}}$
${\displaystyle \cdots \cdots }$
${\displaystyle x_{2k}=(x_{k})^{2}-2}$
${\displaystyle x_{2k+1}=x_{k}\cdot x_{k+1}-x_{1}}$

## 解線性遞迴關係式

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

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

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

${\displaystyle a_{n}=C\lambda _{1}^{n}+D\lambda _{2}^{n}\,}$

${\displaystyle a_{n}=C\lambda ^{n}+Dn\lambda ^{n}\,}$

CD都是常數。

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

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

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

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

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

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

### 时域经典法求解

${\displaystyle \sum _{k=0}^{N}a_{k}y(n-k)=\sum _{r=0}^{M}b_{r}x(n-r)}$

${\displaystyle \sum _{k=0}^{N}a_{k}y(n-k)=0}$

${\displaystyle \sum _{k=0}^{N}a_{k}\alpha ^{N-k}=0}$

${\displaystyle y_{h}(n)=\sum _{i=1}^{N}C_{i}\alpha _{i}^{n}}$

${\displaystyle y_{h}(n)=\sum _{i=1}^{K}n^{K-i}\alpha _{1}^{n}}$

${\displaystyle y_{p}(n)=A_{0}n^{k}+A_{1}n^{k-1}+\cdots +A_{k}}$

${\displaystyle y_{p}(n)=Aa^{n}}$

${\displaystyle y_{p}(n)=(A_{1}n+A_{0})a^{n}}$

${\displaystyle y_{p}(n)=(A_{r}n^{r}+A_{r-1}n^{r-1}+\cdots +A_{1}n+A_{0})a^{n}}$

### 例子

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

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

${\displaystyle b_{n}=c_{1}2^{n}\,}$

${\displaystyle a_{n}=c_{2}3^{n}+c_{3}n+c_{4}\,}$

${\displaystyle c_{2}3^{n+1}+c_{3}(n+1)+c_{4}=2(c_{2}3^{n}+c_{3}n+c_{4})+3^{n}+5n\,}$

${\displaystyle 3c_{2}=2c_{2}+1\,}$
${\displaystyle c_{2}=1\,}$

${\displaystyle c_{3}=2c_{3}+5\,}$
${\displaystyle c_{3}=-5\,}$

${\displaystyle c_{3}+c_{4}=2c_{4}\,}$
${\displaystyle c_{4}=c_{3}=-5\,}$

${\displaystyle a_{n}=c_{1}2^{n}+3^{n}-5n-5\,}$

## 與微分方程的關係

${\displaystyle y'(t)=f(t,y(t)),\qquad y(t_{0})=y_{0},\qquad \qquad }$

${\displaystyle y_{n+1}=y_{n}+hf(t_{n},y_{n})}$