$\text{OGF}$推导 $\text{\#0}$

$$p_0 = 0,p_1=1,\forall n\ge 2,p_n=2p_{n-1}+p_{n-2}$$
其$\text{OGF}$
$$\begin{aligned} P(x)&=\sum_{i\ge 0}p_ix^i \\\ &=\sum_{i\ge 2}p_ix^i + x \\\ &=2x\sum_{i\ge 1}p_ix^i+x^2\sum_{i\ge 0}p_ix^i + x \\\ &=2xP(x)+x^2P(x)+x \end{aligned}$$
$$P(x)=\frac{x}{1-2x-x^2}$$

$$1-2x-x^2=(1-\phi x)(1-\hat{\phi}x)$$

可得$\phi=1+\sqrt{2},\hat{\phi}=1-\sqrt{2}$

部分分式展开与不同根的有理展开定理

如果$R(x)=\frac{P(x)}{Q(x)}$，$Q(x)=q_0\prod_{i=1}^l(1-\rho_ix)$，且$\rho_1…\rho_l$均不相同，且$P(x)$是一个次数小于$l$的多项式，那么

$$[x^n]R(x)=\sum_{i=1}^la_i\rho_i^n,a_k=\frac{-\rho_kP(1/\rho_k)}{Q’(1/\rho)}$$

即：
$$R(x)=\sum_{i=1}^l\frac{a_i}{1-\rho_ix}$$

$Q(x)=P(x)=1-2x-x^2,Q’(x)=P’(x)=-2-2x$
下面的$P$指的是$z$。
$$[x^k]R(x)=\frac{-\rho P(1/\rho)}{Q’(1/\rho)}=\frac{-1}{-2-2/\rho}=\frac{\rho}{2\rho+2}$$

因此$\phi$的系数为$\frac{1}{2\sqrt{2}}$

$\hat{\phi}$的系数为$-\frac{1}{2\sqrt{2}}$

因此

$$p_n=\frac{(1+\sqrt{2})^n-(1-\sqrt{2})^n}{2\sqrt{2}}$$