Question

组合数学递推关系看不懂...

下了好几份课件, 看了很久依然看不懂怎么由特征根方程求得a(n)通项公式,
现在只会从a(n)+C(1)a(n-1)+C(2)a(n-2)+...+C(k)a(n-k)=0得到特征多项式C(x)=x^k+C1x^(k-1)+...+C(k-1)x+C(k)
之后母函数G(x)=P(x)/(1+C(1)x+...+C(k)x^k)的P(x)是什么东西, 分母那堆东西怎么求就看不懂了... 跳到了G(x)=A1/(1-a1x)+...则不知道A1~Ak要怎么求
再之后怎么由G(x)得到a(n)也更搞不懂... 课件没找到一个明确的公式能套进去解...

请问有谁能直接地提供一下从特征多项式求得an通项式的明确步骤? 不求证明, 只需要算法步骤和公式 谢谢`

Answer 1

设特征多项式C(x)=x^k+C1x^(k-1)+...+C(k-1)x+C(k)的根为{r1,r2,....,rk}
这里P(x)=a1x+(a1c1+a2)x²+....+(a1c(k-1)+a2c(k-2)+....a(k-1)c1+ak)x^k
其中a1,a2,...,ak是数列an的初始条件值
然后母函数G(x)=P(x)/(1+C(1)x+...+C(k)x^k)=P(x)/[(1-r1x)(1-r2x)...(1-rkx)]
则可将有理函数G(x)分解为A1/(1-r1x)+....+Ak/(1-rkx)
其中A1，A2....Ak的求法可以设G(x)=A1/(1-r1x)+....+Ak/(1-rkx)，
则A1/(1-r1x)+....+Ak/(1-rkx)=P(x)/[(1-r1x)(1-r2x)...(1-rkx)]，等式两边同乘(1-r1x)
得A1+A2(1-r1x)/(1-r2x)+....+Ak(1-r1x)/(1-rkx)=P(x)/[(1-r2x)...(1-rkx)]，然后再令x=1/r1
得A1=P(1/r1)/[(1-r2/r1)...(1-rk/r1)]，类似等式两边同乘(1-rix)，然后再令x=1/ri，便可得Ai
然后利用1/(1-rx)=1+rx+(rx)²+...，将G(x)中每一项写成这种形式
整理后便可以求得G(X)=f(0)+f(1)x+f(2)x²+....f(n)x^n+.....
其中x^n的系数f(n)=A1(r1)^n+A2(r2)^n+...+Ak(rk)^n便为an的通项公式
即an=A1(r1)^n+A2(r2)^n+...+Ak(rk)^n