离散数学数列

本节不再过多描述数列知识，仅作为备忘性质。 对于一个非齐次线性数列，形如

@B13@N7N5__DP_ZR8@FVKT.png

此处F（n）是最高为t次的多项式和一个指数函数的乘积。我们要求解这个通式，如线性代数中一样，先解齐次方程，由解的结构，再加上特解即为所求的解。

解齐次方程

在解齐次方程的时候，先列出特征方程，如果没有重根，就把原式子中最高次的那一项留着（通常写成an），放在左边；右边是各个根的指数函数，如r1^n，r2^n等，前面设出常系数α1，α2……，即可解得通解。如果是重根，则省略写成一个指数函数，前面的系数改成m次的多项式，m为重数。

特解

如果非齐次项的形式如上图中F（n）所示，应判断其中底数（有可能是1）是否是特征方程的根。如果不是，特解形式则为P（t）*s^n（注意到特解里的底数和原来非齐次项的底数是一致的），其中t是原F（n）的最高次；若是，则应加上n^m乘到P（t）*s^n前面，作为特解。然后带入初值解出结果。解的形式中记得通解前面是有系数的。 在列举关于连续0或者不连续0的数列递推关系时候，应当注意：若列举连续0，比如3个0的bit string，应该从开头考虑，即将全集分割成1，01，001和000开头的这几类，因为这不重不漏；如果列举不连续的0的数列递推关系，如不连续的两个0，从数列后方考虑，如若第n位是1，则前n-1位应满足条件，即an-1，如是0则第n-1位应为1，则前n-2位应满足条件，列出an=an-1 + an-2.

本文适用于bupt的离散数学，或了解学习数列相关知识。