离散数学|递归关系类型–集合2

先决条件—— 解决复发 , 不同类型的递推关系及其解法 , 递归关系的实践集 一种序列，通过指示一个连接其一般术语a的关系来定义 _n 用一个 _n-1 A. _n-2 等被称为 递推关系 对于序列。

递归关系的类型

• 一阶递推关系：- 形式的递归关系： A. _N =ca _n-1 +f（n） 对于n>=1 其中c是常数，f（n）是已知函数，称为一阶常系数线性递推关系。如果f（n）=0，则该关系为齐次关系，否则为非齐次关系。

  例如：- 十、 _N =2x _n-1 –1，a _N =不适用 _n-1 +1等。

  问题:- 求递推关系T（2） ^K )=3T（2） ^k-1 )+1，T（1）=1。 让T（2） ^K )=a _k .因此 _K =3a _k-1 + 1 乘以x ^K 然后求和， ∑a _K 十、 ^K =3∑a _k-1 十、 ^K +∑x ^K ——> (1) ∑a _k-1 十、 ^K =[a] ₀ x+a _1. 十、 ^2. + ……] =x[a ₀ +a ₁ x+…]=x[G（x）] （1） 变成 G（x）–3xG（x）–x/（1-x）=0 G（x）（1-3x）–x/（1-x）=0 G（x）=x/[（1-x）（1-3x）]=A/（1-x）+B/（1-3x） –>A=-1/2和B=3/2 G（x）=（3/2）∑（3x） ^K –（1/2）∑（x） ^K x系数 ^K 是一个 _K = (3/2)3 ^K – (1/2)1 ^K 所以，一个 _K = [3 ^k+1 – 1]/2.

• 二阶线性齐次递推关系：- 形式的递推关系 C _N A. _N +c _n-1 A. _n-1 +c _n-2 A. _n-2 = 0 ——> (1) 对于n>=2，其中c _N ，c _n-1 c _n-2 是c的实数常数 _N != 0称为常系数二阶线性齐次递推关系。 解决方法是表格a _n =ck ^N c，k=0 把这个放进（1） C _N ck ^N +c _n-1 ck ^n-1 +c _n-2 ck ^n-2 = 0 C _N k ^2. +c _n-1 k+c _n-2 = 0 —–> (2) 因此 _n =ck ^N 是（1）的解，如果k满足二次方程（2）。这个方程被称为关系式（1）的特征方程。 现在出现了三个案例， 案例1： 如果两个根k _1. ，k _2. 方程的形式是实的和不同的，然后我们取 A. _N =A（k） _1. ) ^N +B（k） _2. ) ^N 作为（1）的通解，其中A和B是任意实常数。

  案例2： 如果两个根k _1. K _2. 方程的常数为实且相等，k为公共值，我们取 A. _n =（A+Bn）k ^N 作为（1）的通解，其中A和B是任意实常数。

  案例3： 如果两个根k _1. 和k ₂ 方程的形式是复杂的，k _1. 和k _2. 是彼此的复共轭，即k _1. =p+iq和k _2. =p–智商，我们需要 A. _N =r ^N （Acosnθ+bsinθ） 作为（1）的通解，其中A和B是任意复常数，r=|k _1. |=|k _2. |=&Sqrt； P ^2. +q ^2. θ=tan ^-1 （q/p）。

问题:- 求递推关系a _N +a _n-1 –6a _n-2 =0表示n>=2，假设a ₀ =-1和a _1. = 8. 这里是a的系数 _N A. _n-1 还有 _n-2 是c吗 _N =1，c _n-1 =1和c _n-2 分别为-6。因此，特征方程是 K ^2. +或（k）等于0-1 （1）的根是k _1. =-3和k _2. =2，它们是真实的和不同的。因此，一般的解决方案是 A. _N =A（-3） ^N +B（2） ^N 其中A和B是任意常数。从上面我们可以看到 ₀ =A+B和A ₁ =-3A+2B A+B=-1 -3A+2B=8 解决这些问题，我们得到A=-2和B=1 因此 _N = -2(-3) ^N + (2) ^N