5004：将一些简单的递推式转成通项式

镇楼图

Pixiv:飛者

相关blog：https://www.cnblogs.com/AlienfronNova/p/14825746.html

〇、为什么选择通项式？

通项式在相关blog中我们分析了一个递推式和通项式的优劣，为了开发效率我们常常使用递推式，但递推式的效率不尽人意，尽管使用通项式有诸多缺点，在程序里还会遇到精度问题和溢出问题，但为了速度！！！为了速度！！！为了速度！！！

为了速度我们希望能用通项式。

但我们能很容易的将通项式转成递推式，但反过来将递推式转成通项式我们可能就不会了。

你知道\(H(n)=2H(n-1)+3H(n-2)+4\)的通项式么？

我们接下来要学的就是如何将递推式转成通项式

一、等差、等比序列

这是最最最特殊的情况，我们可以其它方法计算求得，但我们可以直接套公式求得。

等差序列

递推式是\(f(n)-f(n-1)=d,f(0)=a_0\)这种形式的我们称这是等差数列

其通项式是\(f(n)=a_0+(n-1)d\)

等比序列

递推式是\(\frac{f(n)}{f(n-1)}=q,f(0)=a_0\)这种形式的我们称这是等比序列

其通项式是\(f(n)=a_0q^{n-1}\)

累加法、累乘法

略，这里不阐述这种方法，可自行baidu

三、线性齐次递推式

我们把\(a_n=C_1a_{n-1}+C_2a_{n-2}...+C_ka_{n-k},C_i为常数\)这种形式的递推式称为线性齐次递推式

斐波那契数列的递推式\(f(n)=f(n-1)+f(n-2),f(0)=1,f(1)=1\)是典型的线性齐次递推式

①令\(f(n)=r^n\)

②代入得\(r^n=r^{n-1}+r^{n-2}\)

③同除\(r^{n-2}\)得到\(r^2=r+1\)，这个方程我们称为特征方程

④计算求得\(r\)，\(r\)称为特征根（实际情况更复杂一些，不过我们暂时按这种情况来算）这里我们计算得出\(r_1=\frac{1+\sqrt5}{2}\),\(r_2=\frac{1-\sqrt5}{2}\)

⑤得出\(a_n=d_1(\frac{1+\sqrt5}{2})^{n}+d_2(\frac{1+\sqrt5}{2})^n\)

⑥我们根据初始条件\(f(0)=1，f(1)=1\)来计算出\(d_1\)，\(d_2\)

这里我们计算得出\(d_1=\frac{5+\sqrt5}{10}\)，\(d_1=\frac{5-\sqrt5}{10}\)

⑦因此我们得出斐波那契数列的通项式是

? \(a_n=\frac{5+\sqrt5}{10}(\frac{1+\sqrt5}{2})^{n}+\frac{5-\sqrt5}{10}(\frac{1+\sqrt5}{2})^n\)

【这和你百度里搜到的可能不太一样，因为这里我以0为初始项，如果你以1为初始项说不定算出来的和百度的一样】

通用解法

对于计算\(a_n=C_1a_{n-1}+C_2a_{n-2}...+C_ka_{n-k},C_i为常数\)

①令\(a_n=r^n\)

②求特征方程\(r^k-C_1r^{k-1}-C_2r^{k-2}-...-C_k=0\)

③求得特征根\(r\)

? 我们注意到特征方程根的个数由k决定，我们也称这个递推关系是\(k\)阶的，k 的多少就代表你要解一元\(k\)次方程

④根据特征根写出方程

? 注意即特征根\(r\)求出来也很可能是一个复数根，这我们也要考虑在内。而且 特征根也很有可能会出现重复，我们将重复的根记作\(x_0、x_1...x_m\)。

? 我们得出\(a_n=∑h_i(n)\)

? 其中\(h_i(n)=∑C_{e_i}^in^{e_i-1}{x_i}^n\)

? \(C_{e_i}^i\)为待求系数，需要通过初始条件求得

? \(e_i\)为与\(x_i\)重根的个数

? 【一般情况下我们只会遇到2阶的线性齐次递推式，所以也不算特别困难】

四、F(n)≡C的线性非齐次递推式

我们把\(a_n=C_1a_{n-1}+C_2a_{n-2}...+C_ka_{n-k}+F(n),C_i为常数\)这种形式的递推式称为线性非齐次递推式

不过求解这一类型要比上述难了不少，因此我们只考虑\(F(n)≡C\)的情况

我们以汉诺塔为例

汉诺塔的递推式是\(H(n)=2H(n-1)+1，H(0)=1\)是典型的线性非齐次递推式

①跟求线性齐次递推式一样，我们无视\(F(n)\)的存在求特征根，我们求得特征根\(q=2\)

②我们发现特征根为\(1\)的个数为\(0\)个，特征根为\(2\)的个数为\(1\)个

因此我们根据一个公式（后续会给）求得\(H(n)=C_1^0+C_1^12^n\)

③根据初始条件求得\(C_0^0=-1\)、\(C_1^1=2\)

因此我们得出汉诺塔的通项式是\(H(n)=2^{n+1}-1\)

通用解法

①求特征根\(q_i\)

? 同样我们求得重根数\(e_i\)，以及用\(x_i\)表示这个重根

? 另外线性非齐次与线性齐次的区别就是你还需要求得\(e_0\)，这个\(e_0\)代表了根 为1的个数

②\(a_n=∑C_{e_0}^in^{e_0}+∑h_i(n)\)

? 其中\(h_i(n)=∑C_{e_i}^in^{e_i-1}(x_i)^n\)

③通过初始条件求得系数，然后代入

总结

? 这里只介绍了最简单的情况，如果有机会，我会写一篇更详细的blog

参考书籍

《离散数学及其应用 第六版》

5004：将一些简单的递推式转成通项式

原文：https://www.cnblogs.com/AlienfronNova/p/14826094.html