一阶线性递推（生成函数）

就是长这个样子的：
a n+1 ${n+1}_{}$=pa n $n_{}$+q
a0=0 $a_0=0$
比如：a n+1 ${n+1}_{}$=2a n $n_{}$+1
这种就是我们高中的时候学的差比数列嘛φ(>ω<*)

但我们现在用生成函数来弄一弄：
令f(x)=a 0 $0_{}$+a 1 $1_{}$x+a 2 $2_{}$x+…..+a n $n_{}$x
即：
f(x)= ∑∞n=0 $\sum _{n=0}^{\infty }$a n $n_{}$x n $n^{}$

= ∑∞n=1 $\sum _{n=1}^{\infty }$(pa n−1 ${n-1}_{}$+q)x n $n^{}$

= ∑∞n=1 $\sum _{n=1}^{\infty }$(pa n−1 ${n-1}_{}$)x n $n^{}$+ ∑∞n=1 $\sum _{n=1}^{\infty }$qx n $n^{}$

=px ∑∞n=1 $\sum _{n=1}^{\infty }$(a n−1 ${n-1}_{}$)x n−1 ${n-1}^{}$+q( ∑∞n=0 $\sum _{n=0}^{\infty }$x n $n^{}$-x 0 $0^{}$)

=px f(x)+q( 11−x $\frac{1}{1-x}$-1)

=px f(x)+q( x1−x $\frac{x}{1-x}$)

所以：f(x)= qx(1−x)(1−px) $\frac{qx}{(1-x)(1-px)}$

然后再拆开
f(x)= q1−p(1−x) $\frac{\frac{q}{1-p}}{(1-x)}$+ qp−1(1−px) $\frac{\frac{q}{p-1}}{(1-px)}$

= ∑∞n=0 $\sum _{n=0}^{\infty }$ q1−p $\frac{q}{1-p}$x n $n^{}$+ ∑∞n=0 $\sum _{n=0}^{\infty }$ qp−1 $\frac{q}{p-1}$(px) n $n^{}$

= ∑∞n=0 $\sum _{n=0}^{\infty }$( q1−p $\frac{q}{1-p}$+ qp−1 $\frac{q}{p-1}$q n $n^{}$ )x n $n^{}$

里面那一坨就是a n $n^{}$
即：
a n $n^{}$= q1−p $\frac{q}{1-p}$+ qp−1 $\frac{q}{p-1}$q n $n^{}$

所以：a n+1 ${n+1}_{}$=2a n $n_{}$+1的通项公式就是当p=2,q=1的时候了

a n $n^{}$=2 n $n^{}$-1

(￣▽￣)~*