$\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}} $$