# 二階數學補充-數列與遞迴

## 一階遞迴
### 左右補項法
- $a_1=1,\ a_{n+1}=3a_n+4$, 求一般式

> 假設$a_{n+1}+k=3(a_n+k)$
> 解得$k=2$
> 故有
> $\ \ \ a_2+2=3(a_1+2)$
> $\ \ \ a_3+2=3(a_2+2)$
> $\ \ \ a_4+2=3(a_3+2)$
> $\ \ \ \ \ \ \ \ \ \ \ \ \ \ ...$
> $\times a_n+2=3(a_{n-1}+2)$
> $----------$
> $a_n+2=3^{n-1}(a_1+2)=3^n$
> $a_n=3^n-2$

### 斷頭去尾法(Perturb and Conquer)
credit: [mathinity](https://www.instagram.com/p/Ch7LuCQj9vB/?igshid=YmMyMTA2M2Y=)
- 化簡$\sum_{k=1}^nk2^k$

> 令$a_n=n2^n,\ \ S_n=\sum_{k=1}^nk2^k$
> 我們有$S_n+a_{n+1}=a_1+S_{2\ to\ n+1}$
> $S_n+(n+1)2^{n+1}=2+\sum_{k=2}^{n+1}k2^k$
> 我們的目標是從$\sum_{k=2}^{n+1}k2^k$裡面生出$S_n$
> 令$t=k-1$
> $S_n+(n+1)2^{n+1}=2+\sum_{t=1}^n(t+1)2^{t+1}$
> $=2+\sum_{t=1}^nt2^{t+1}+\sum_{t=1}^n2^{t+1}$
> $=2+2\sum_{t=1}^nt2^t+(2^{n+2}-4)$
> $=2+2S_n+2^{n+2}-4$
> 化簡得$S_n=(n-1)2^{n+1}+2$

其實這題也可以用平常用的等差等比解法

### 窮舉通靈法
- 考慮像下圖一樣的數值三角形,在兩條邊上依序填入 0,1,2,...,而三角形內部的數字則跟巴斯卡三角形一樣,是上列相鄰的兩數字的和。
第一列所有數字的總和是 0,第二列所有數字的總和是 2,第三列所有數字的總和是 6。請問第 2022 列的總和~~除以 1000 的餘數~~是?。

> 0, 2, 6, 14, 30, ...
> 可以看出後一項是前一項$\times2+2$
> $\rightarrow a_n=2^n-2$

## 二階遞迴
### Method of Divine Inspiration
好啦 其實就是通靈
圖文不太相關

### 特徵方程式
- $F_1=1, F_2=1, F_{n+2}=F_{n+1}+F_n$, 求一般式

> 先寫成$F_{n+2}-F_{n+1}-F_n=0$
> 便可以得出特徵方程式$\lambda^2-\lambda-1=0$
> 解為$\lambda=\cfrac{1+\sqrt5}2, \cfrac{1-\sqrt5}2$
> 故有$F_n=c_1(\cfrac{1+\sqrt5}2)^n+c_2(\cfrac{1-\sqrt5}2)^n$
> $F_0=0, F_1=1代入$
> 可得$c_1=\cfrac1{\sqrt5}, c_2=-\cfrac1{\sqrt5}$

### 特徵矩陣對角化
- $F_1=1, F_2=3, F_{n+2}=F_{n+1}+2F_n$, 求一般式

> $\begin{bmatrix}1&2\\1&0\end{bmatrix}\begin{bmatrix}F_{n+1}\\F_n\end{bmatrix}=\begin{bmatrix}F_{n+2}\\F_{n+1}\end{bmatrix}$
> 令$P=\begin{bmatrix}1&2\\1&0\end{bmatrix}$
> $\det(P-\lambda I)=0\rightarrow\lambda=2, -1$
> $(1-\lambda)x+2\times1=0\rightarrow x=2, -1$
> 令特徵矩陣
>
> $Q=\begin{bmatrix}2&-1\\1&1\end{bmatrix}$
> $Q^{-1}=\cfrac13\begin{bmatrix}1&1\\-1&2\end{bmatrix}$
>
> 令$P=QRQ^{-1}\rightarrow R=$
> $Q^{-1}PQ=\cfrac13\begin{bmatrix}1&1\\-1&2\end{bmatrix}\begin{bmatrix}1&2\\1&0\end{bmatrix}\begin{bmatrix}2&-1\\1&1\end{bmatrix}$
>
> $=\cfrac13\begin{bmatrix}2&2\\1&-2\end{bmatrix}\begin{bmatrix}2&-1\\1&1\end{bmatrix}=\begin{bmatrix}2&0\\0&-1\end{bmatrix}$
>
> $\begin{bmatrix}F_{n+1}\\F_{n}\end{bmatrix}=\begin{bmatrix}1&2\\1&0\end{bmatrix}^{n-1}\begin{bmatrix}F_2\\F_1\end{bmatrix}$
> $=P^{n-1}\begin{bmatrix}F_2\\F_1\end{bmatrix}$
> $=(QRQ^{-1})^{n-1}\begin{bmatrix}F_2\\F_1\end{bmatrix}$
> $=QR^{n-1}Q^{-1}\begin{bmatrix}F_2\\F_1\end{bmatrix}$
> $=\begin{bmatrix}2&-1\\1&1\end{bmatrix}\begin{bmatrix}2&0\\0&-1\end{bmatrix}^{n-1}\cfrac13\begin{bmatrix}1&1\\-1&2\end{bmatrix}\begin{bmatrix}F_2\\F_1\end{bmatrix}$
> $=\cfrac13\begin{bmatrix}2^n&(-1)^n\\2^{n-1}&(-1)^{n-1}\end{bmatrix}\begin{bmatrix}1&1\\-1&2\end{bmatrix}\begin{bmatrix}F_2\\F_1\end{bmatrix}$
> $=\cfrac13\begin{bmatrix}2^n+(-1)^{n+1}&2^n+2(-1)^n\\2^{n-1}+(-1)^n&2^{n-1}+2(-1)^{n-1}\end{bmatrix}\begin{bmatrix}3\\1\end{bmatrix}$

> $F_n=2^{n-1}+(-1)^n+\cfrac13\times(2^{n-1}+2(-1)^{n-1})$
> $=\cfrac23\times2^n+\cfrac13\times(-1)^n$

## 其他遞迴
### 找源頭法
- 有10階階梯, 一次可以爬1或2階, 請問有幾種方法爬上去?

> 假設我現在在第n階
> 我一定是從前1階或前2階爬上來的
> $\rightarrow f(n)=f(n-1)+f(n-2)$ (變費氏數列了)

### 動態規劃(DP)
問楊翔宇 窩不會DP
- 下圖為一個7x7格子盤，每個格子都填上一個數字。今天從左上角的0要走到右下角的4，規定每一次只能往右走一個或者往下走一格，試問在所有這樣走法的路徑中，數字和最小者為何?

| 0 | 1 | 3 | 2 | 3 | 4 | 5 |
| --- | --- | --- | --- | --- | --- |:--- |
| 2 | 2 | 1 | 4 | 6 | 2 | 0 |
| 1 | 9 | 9 | 9 | 9 | 9 | 1 |
| 4 | 7 | -3 | 2 | 1 | -2 | 1 |
| 9 | 8 | 7 | 0 | 1 | 2 | 7 |
| -3 | 2 | 2 | 3 | 1 | -3 | 1 |
| 4 | 5 | 4 | 0 | 4 | 5 | 4 |

> 你想算13x924次還是2x84次?

## 寫寫考古

### EC2106 (等差等比級數)
令$s=\sum=p+2p^2+3p^3+...$
$\ \ \ \ \ -)\ sp=\ \ \ \ \ \ \ \ \ p^2+2p^3+...$
$-----------------$
$\ s(1-p)=p+\ \ p^2+\ \ p^3+...=\cfrac p{1-p}$

$s=\cfrac p{(1-p)^2}=\cfrac34$

### EC2110 (醉漢漫遊)
參看EE1807

### EC2116 (一階遞迴 帶一次項)
$x_{n+1}=2x_n+n$
$\rightarrow x_{n+1}+n+2=2(x_n+n+1)$
:::info
此處配n+2的原因是
如果配成$x_{n+1}+n=2(x_n+n)$
會因為變動的$n$導致相乘消不掉
:::

$\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ x_2+3=2(x_1+2)$
$\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ x_3+4=2(x_2+3)$
$\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ ...$
$\times)\ x_{2021}+2022=2(x_{2020}+2021)$
$-----------------$
$\ \ \ \ \ \ x_{2021}+2022=2^{2020}\times 3$

$x_{2021}=3\times2^{2020}-2022$

### EC2001 找規律

### EC2007 (一階遞迴 帶一次係數指數項)

### EE1807 (醉漢漫遊)
$P(1)=x$是假設的

### CS1805 (費氏數列性質)
$\lim_{n\rightarrow\infty}A_n=A_{n+1}$
$F_{n+1}=A_{n+1}F_{n+2}=A_nF_{n+2}$
$F_n=A_nF_{n+1}=A_n\ ^2F_{n+2}$
$F_{n+2}=F_{n+1}+F_n$
$\rightarrow F_{n+2}=A_nF_{n+2}+A_n\ ^2F_{n+2}$
$\rightarrow 1=A_n+A_n\ ^2$
$\rightarrow A_n\ ^2+A_n-1=0$
$\rightarrow A_n=\cfrac{-1\pm\sqrt5}2$(負不合)

### CS1806 (裂項)
原式$=2(\cfrac12+\cfrac16+\cfrac1{12}+\cfrac1{20}+\cfrac1{30}+...)$
$=2[(1-\cfrac12)+(\cfrac12-\cfrac13)+(\cfrac13-\cfrac14+...)]$
$=2(1-\cfrac1\infty)=2$

### EE1708 (遞迴-矩陣對角化)
(a)
假設今天要排$n$元($n\ge2$)
可以在$n-1$元後面補一張$1$元
或是在$n-2$元後面補一張$2$元(2元有兩種)
$\rightarrow a_n=a_{n-1}+2a_{n-2}$
$a_1=1$(一張1元)
$a_2=3$(1+1 or 2)

(b)
設$P=\begin{bmatrix}a&b\\c&d\end{bmatrix}$
可得$a_n=a\times a_{n-1}+b\times a_{n-2}$
$a_{n-1}=c\times a_{n-1}+d\times a_{n-2}$
得$a=1, b=2, c=1, d=0$
$P=\begin{bmatrix}1&2\\1&0\end{bmatrix}$

(c\)
:::info
矩陣$Q$的來源:
假設一個矩陣$X=\begin{bmatrix}a_1\\a_2\end{bmatrix}$滿足$PX=\lambda X$
$\rightarrow PX=\lambda IX$
$\rightarrow (P-\lambda I)X=\begin{bmatrix}0\\0\end{bmatrix}$
$\begin{bmatrix}1-\lambda&2\\1&0-\lambda\end{bmatrix}\begin{bmatrix}a_1\\a_2\end{bmatrix}=\begin{bmatrix}0\\0\end{bmatrix}$
且$\begin{bmatrix}a_1\\a_2\end{bmatrix}\not=\begin{bmatrix}0\\0\end{bmatrix}$
我們稱$X$為$P$的特徵向量
:::
$\det(Q)=-3$
$Q^{-1}=\cfrac1{-3}\begin{bmatrix}-1&-1\\-1&2\end{bmatrix}$

(d)
$P=QRQ^{-1}$
$PQ=QRQ^{-1}Q=QR$
$Q^{-1}PQ=Q^{-1}QR=R$
$R=\cfrac13\begin{bmatrix}1&1\\1&-2\end{bmatrix}\begin{bmatrix}1&2\\1&0\end{bmatrix}\begin{bmatrix}2&1\\1&-1\end{bmatrix}$
$=\begin{bmatrix}2&0\\0&-1\end{bmatrix}$

(e)
$\begin{bmatrix}a_{n+1}\\a_n\end{bmatrix}=P^{n-1}\begin{bmatrix}3\\1\end{bmatrix}$
$=(QRQ^{-1})^{n-1}\begin{bmatrix}3\\1\end{bmatrix}$
$=QR^{n-1}Q^{-1}\begin{bmatrix}3\\1\end{bmatrix}$
$=\begin{bmatrix}2&1\\1&-1\end{bmatrix}\begin{bmatrix}2^{n-1}&0\\0&(-1)^{n-1}\end{bmatrix}\cfrac13\begin{bmatrix}1&1\\1&-2\end{bmatrix}\begin{bmatrix}3\\1\end{bmatrix}$
$=\begin{bmatrix}2^n&(-1)^{n-1}\\2^{n-1}&(-1)^n\end{bmatrix}\begin{bmatrix}\cfrac43\\\cfrac13\end{bmatrix}$
$a_n=\cfrac23\times2^n+\cfrac13\times(-1)^n$

### CS1703 (拆級數)
$(\sqrt{S_n}+\sqrt{S_{n-1}})=a_n$ ---==式1==
$a_n(\sqrt{S_n}-\sqrt{S_{n-1}})=(\sqrt{S_n}+\sqrt{S_{n-1}})(\sqrt{S_n}-\sqrt{S_{n-1}})$
$=S_n-S_{n-1}$
$=a_n$
$\rightarrow(\sqrt{S_n}-\sqrt{S_{n-1}})=1$ ---==式2==

12兩式相加
$2\sqrt{S_n}=a_n+1\rightarrow S_n=\cfrac{a_n^2+2a_n+1}4\rightarrow S_{n-1}=\cfrac{a_{n-1}^2+2a_{n-1}+1}4$

12兩式相減
$2\sqrt{S_{n-1}}=a_n-1\rightarrow S_{n-1}=\cfrac{a_n^2-2a_n+1}4=\cfrac{a_{n-1}^2+2a_{n-1}+1}4$

$a_n^2-a_{n-1}^2=2(a_n+a_{n-1})\rightarrow a_n-a_{n-1}=2$
$\rightarrow a_n=2n-1$

### CS1705 (函數遞迴)*

### CS1711 (根號遞迴)
注意到
$\sqrt{(n+2)+(n-2)(n+1)}=\sqrt{n+2+n^2-n-2}=n$
$\sqrt{(n+3)+(n-1)(n+2)}=\sqrt{n+3+n^2+n-2}=n+1$
$\sqrt{(n+4)+(n)(n+3)}=\sqrt{n+4+n^2+3n}=n+2$
...
$n=4$帶進去即為所求

### CS1718 (巴斯卡三角形)
找個規律
第一行和$=(1+n+1)(n+1)/2$
第二行和$=(3+2n+1)(n)/2$
第三行和$=(8+4n)(n-1)/2$
...
通靈猜第n行和$=2^{n-1}(n+2)$

### EE1606 (?)*

### EE1607 (有理數)*

### CS1606 (藏陷阱的級數)
$a_1+2a_2+...+(n-1)a_{n-1}+na_n=n^3+3n+1$
$a_1+2a_2+...+(n-1)a_{n-1}\ \ \ \ \ \ \ \ \ \ \ \ =(n-1)^3+3(n-1)+1$
相減得$na_n=3n^2-3n+1+3\rightarrow a_n=3n-3+\cfrac4n$
:::danger
注意我們在求解過程用到了$a_0$
但$a_0$存在嗎?
:::
帶入$n=1$發現$a_1=4\not=5$
因此$n=1, a_1=5$要特別拿出來講

### CS1613 (倒數遞迴)*

### CS1614 (通靈積分?)
原式$=\cfrac12\sum(-1)^k(\cfrac1{2k-1}-\cfrac1{2k+1})$
$=\cfrac12(-\cfrac11+\cfrac13+\cfrac13-\cfrac15-\cfrac15+\cfrac17+...)$
$=\cfrac12-(\cfrac11-\cfrac13+\cfrac15-\cfrac17+...)$
$=\cfrac12-\cfrac\pi4$
:::info
$\cfrac11-\cfrac13+\cfrac15-\cfrac17+...$
$=\int_0^11dx-\int_0^1x^2dx+\int_0^1x^4dx-\int_0^1x^6dx+...$
$=\int_0^1(1-x^2+x^4-x^6+...)dx$
$=\int_0^1\cfrac1{1+x^2}dx$
$=\arctan x|^1_0$
$=\cfrac\pi4$
:::

### CS1619 (組合級數)*

### EE1505 (幾何遞迴)
$a_1=2$
我們放一條新的線到平面上
穿過$n$條線會讓區域增加$n+1$塊(可以畫圖感受一下)
$\rightarrow$第$n+1$條線會讓區域增加$n+1$塊
$\rightarrow a_n=1+\cfrac{n(n+1)}2$

### CS1403 (?)*

### EE1301 (?)

#### 解1:消常數
令$b_n=a_n-1$
有$b_n=b_{n-1}+2b_{n-2}$
再用二階遞迴解

#### 解2:降階遞迴
$a_n+(a_{n-1}-2)=2a_{n-1}+2a_{n-2}-4=2(a_{n-1}+a_{n-2}-2)$

$\ \ \ \ a_n+(a_{n-1}-2)=2(a_{n-1}+a_{n-2}-2)$
$a_{n-1}+(a_{n-2}-2)=2(a_{n-2}+a_{n-3}-2)$
$\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ ...$
$\times)\ \ \ \ a_3+(a_2-2)=2(a_2+a_1-2)$
$----------------------$
$\ \ \ \ \ \ \ a_n+a_{n-1}-2=2^{n-2}(5+3-2)=3\times2^{n-1}$

$(a_n-1)+(a_{n-1}-1)=2^n+2^{n-1}$
$a_n=2^n+1$

#### 解3:矩陣對角化
$a_0=\cfrac{5-3+2}2=2$
$P\begin{bmatrix}a_{n+1}\\a_n\\1\end{bmatrix}$
$=\begin{bmatrix}1&2&-2\\1&0&0\\0&0&1\end{bmatrix}\begin{bmatrix}a_{n+1}\\a_n\\1\end{bmatrix}=\begin{bmatrix}a_{n+2}\\a_{n+1}\\1\end{bmatrix}$
$P=QRQ^{-1}$
$=\begin{bmatrix}1&1&2\\-1&1&1\\0&1&0\end{bmatrix}\begin{bmatrix}-1&0&0\\0&1&0\\0&0&2\end{bmatrix}\cfrac13\begin{bmatrix}1&-2&1\\0&0&3\\1&1&-2\end{bmatrix}$

$P^{n}\begin{bmatrix}a_1\\a_0\\1\end{bmatrix}=\begin{bmatrix}a_{n+1}\\a_n\\1\end{bmatrix}$
$\rightarrow QR^nQ^{-1}\begin{bmatrix}a_1\\a_0\\1\end{bmatrix}$
$=\begin{bmatrix}1&1&2\\-1&1&1\\0&1&0\end{bmatrix}\begin{bmatrix}(-1)^n&0&0\\0&1&0\\0&0&2^n\end{bmatrix}\cfrac13\begin{bmatrix}1&-2&1\\0&0&3\\1&1&-2\end{bmatrix}\begin{bmatrix}3\\2\\1\end{bmatrix}$
$=\begin{bmatrix}(-1)^n&1&2\times2^n\\-(-1)^n&1&2^n\\0&1&0\end{bmatrix}\cfrac13\begin{bmatrix}1&-2&1\\0&0&3\\1&1&-2\end{bmatrix}\begin{bmatrix}3\\2\\1\end{bmatrix}$
$=\cfrac13\begin{bmatrix}(-1)^n+2\times2^n&-2(-1)^n+2\times2^n&(-1)^n+3-4\times2^n\\2^n-(-1)^n&2(-1)^n+2^n&-(-1)^n+3-2\times2^n\\0&1&3\end{bmatrix}\begin{bmatrix}3\\2\\1\end{bmatrix}$

$a_n=\cfrac13(3\times2^n-3(-1)^n+4(-1)^n+2\times2^n-(-1)^n+3-2\times2^n)=2^n+1$

### CS1303 (?)*

###### tags: `電資二階` `Cosmos`