# Quod Erat Demonstrandum

## 2015/04/06

### 平鋪

Filed under: Fun — johnmayhk @ 11:23 下午
Tags:

$a_{n-1}$ 種方式。

$a_n=a_{n-1}+2c_{n-1}$ ……………….. (1)

$a_n$ 種；和

$c_{n-1}$ 種；所以

$c_n=a_n+c_{n-1}$ ……………….. (2)

$a_n-a_{n-1}=2c_{n-1}$

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

$3a_n-a_{n-1}=2c_n$

$3a_n-a_{n-1}=a_{n+1}-a_n$　（由 (1)）

$a_{n+1}=4a_n-a_{n-1}$

$a_n=4a_{n-1}-a_{n-2}$

（當中 $n\ge 2$$a_0=1$。驗算一下，$a_1=3$$a_2=4a_1-a_0=4(3)-1=11$

$p=\displaystyle \sum^{\infty}_{r=0}a_rx^r$

$p$

$=\displaystyle \sum^{\infty}_{r=0}a_rx^r$

$= a_0+a_1x+\displaystyle \sum^{\infty}_{r=2}a_rx^r$

$= 1+3x+\displaystyle \sum^{\infty}_{r=2}(4a_{r-1}-a_{r-2})x^r$

$= 1+3x+\displaystyle \sum^{\infty}_{r=2}4a_{r-1}x^r-\displaystyle \sum^{\infty}_{r=2}a_{r-2}x^r$

$= 1+3x+\displaystyle \sum^{\infty}_{r=1}4a_{r}x^{r+1}-\displaystyle \sum^{\infty}_{r=0}a_rx^{r+2}$

$= 1+3x+4x\displaystyle \sum^{\infty}_{r=1}a_{r}x^r-x^2\displaystyle \sum^{\infty}_{r=0}a_rx^r$

$= 1+3x+4x(\displaystyle \sum^{\infty}_{r=0}a_{r}x^r-a_0)-x^2\displaystyle \sum^{\infty}_{r=0}a_rx^r$

$= 1-x+4x\displaystyle \sum^{\infty}_{r=0}a_{r}x^r-x^2\displaystyle \sum^{\infty}_{r=0}a_rx^r$

$= 1-x+4xp-x^2p$

$p=\frac{1-x}{1-4x+x^2}$

$(1-4x+x^2)^{-1}$

$=(1-x(4-x))^{-1}$

$=1+x(4-x)+x^2(4-x)^2+x^3(4-x)^3+x^4(4-x)^4+x^5(4-x)^5+\dots$

$=b_0+b_1x+b_2x^2+b_3x^3+b_4x^4+b_5x^5+\dots$

$b_0=1$

$b_1=4$

$b_2=(-1)+4^2=-1+4^2$

$b_3=C^2_1(-4)+4^3=-4C^2_1+4^3$

$b_4=(-1)^2-C^3_1(4^2)+4^4=1-4^2C^3_1+4^4$

$b_5=C^3_2(4)+C^4_1(-1)4^3+4^5=4C^3_2-4^3C^4_1+4^5$

$b_6=(-1)^3+C^4_2(-1)^24^2+C^5_1(-1)4^4+4^6=-1+4^2C^4_2-4^4C^5_1+4^6$

$\dots$

$b_0=1,b_1=4,b_n=4^n-4^{n-2}C^{n-1}_1+4^{n-4}C^{n-2}_2-\dots+(-1)^k4^{n-2k}C^{n-k}_k$ for $n\ge 2$

$p$

$=\frac{1-x}{1-4x+x^2}$

$=(1-x)(b_0+b_1x+b_2x^2+b_3x^3+\dots)$

$=1+(b_1-b_0)x+(b_2-b_1)x^2+(b_3-b_2)x^3+\dots$

$a_n=b_n-b_{n-1}$

http://www.wolframalpha.com/

expand (1-x)/(1-4x+x^2)

$a_1=3,a_2=11,a_3=41,a_4=153,a_5=571,\dots$