【组合数学】递推方程 ( 通解定义 | 无重根下递推方程通解结构定理 )

一、通解定义

递推方程解的形式 : 满足 H ( n ) − a 1 H ( n − 1 ) − a 2 H ( n − 2 ) − ⋯ − a k H ( n − k ) = 0 H(n) - a_1H(n-1) - a_2H(n-2) - \cdots - a_kH(n-k) = 0 H(n)−a1​H(n−1)−a2​H(n−2)−⋯−ak​H(n−k)=0 公式的所有递推方程 , 都具有 c 1 q 1 n + c 2 q 2 n + ⋯ + c k q k n c_1q_1^n + c_2q_2^n + \cdots + c_kq_k^n c1​q1n​+c2​q2n​+⋯+ck​qkn​ 形式的解 ;

下面开始讨论之前得到的 解的形式 c 1 q 1 n + c 2 q 2 n + ⋯ + c k q k n c_1q_1^n + c_2q_2^n + \cdots + c_kq_k^n c1​q1n​+c2​q2n​+⋯+ck​qkn​ 是否概括了所有解的共同模式 ; 数列中所有的项是否都遵从该模式 ;

如果有些不同的初值 , 不遵循上述模式 , 那该解就 不能作为 所有的 该族 递推方程 的解的通用格式 ;

递推方程通解定义 :

如果递推方程 , 每个解 h ( n ) h(n) h(n) 都存在一组常数 c 1 ′ , c 2 ′ , ⋯   , c k ′ c_1' , c_2' , \cdots , c_k' c1′​,c2′​,⋯,ck′​ ,

使得 h ( n ) = c 1 ′ q 1 n + c 2 ′ q 2 n + ⋯ + c k ′ q k n h(n) = c_1'q_1^n + c_2'q_2^n + \cdots + c_k'q_k^n h(n)=c1′​q1n​+c2′​q2n​+⋯+ck′​qkn​ 成立 ,

则称 c 1 q 1 n + c 2 q 2 n + ⋯ + c k q k n c_1q_1^n + c_2q_2^n + \cdots + c_kq_k^n c1​q1n​+c2​q2n​+⋯+ck​qkn​ 是 递推方程的 通解 ;

分析 :

递推方程解个数 : 递推方程有多少解呢 , 将特征方程解出特征根 , 特征根个数 , 就是递推方程解的个数 ;

常数确定 : h ( n ) h(n) h(n) 是数列的第 n n n 项 , h ( n ) h(n) h(n) 是否能表达成 c 1 ′ q 1 n + c 2 ′ q 2 n + ⋯ + c k ′ q k n c_1'q_1^n + c_2'q_2^n + \cdots + c_k'q_k^n c1′​q1n​+c2′​q2n​+⋯+ck′​qkn​ 格式 , 找到一组常数 c 1 ′ , c 2 ′ , ⋯   , c k ′ c_1' , c_2' , \cdots , c_k' c1′​,c2′​,⋯,ck′​ , 使得上述解的格式确定下来即可 , 这些常数是由初值确认的 ;

二、无重根下递推方程通解结构定理

无重根下递推方程通解结构定理 :

如果 q 1 , q 2 , ⋯   , q k q_1, q_2, \cdots , q_k q1​,q2​,⋯,qk​ 是 递推方程 不相等 的 特征根 ,

则 H ( n ) = c 1 q 1 n + c 2 q 2 n + ⋯ + c k q k n H(n) = c_1q_1^n + c_2q_2^n + \cdots + c_kq_k^n H(n)=c1​q1n​+c2​q2n​+⋯+ck​qkn​ 为通解 ;

随便在递推方程中 , 拿出一个方程出来 , 其解一定是 H ( n ) = c 1 q 1 n + c 2 q 2 n + ⋯ + c k q k n H(n) = c_1q_1^n + c_2q_2^n + \cdots + c_kq_k^n H(n)=c1​q1n​+c2​q2n​+⋯+ck​qkn​ 格式 , 只不过是不同的初值 , 对应不同的 c 1 , c 2 , ⋯   , c k c_1, c_2, \cdots , c_k c1​,c2​,⋯,ck​ 常数 ;

证明上述定理 :

H ( n ) = c 1 q 1 n + c 2 q 2 n + ⋯ + c k q k n H(n) = c_1q_1^n + c_2q_2^n + \cdots + c_kq_k^n H(n)=c1​q1n​+c2​q2n​+⋯+ck​qkn​ 是递推方程的解 , 由之前已经证明过的定理得出 :

• q q q 是特征方程的特征根 ⇔ \Leftrightarrow ⇔ q n q^n qn 是递推方程的解
• h 1 ( n ) h_1(n) h1​(n) 和 h 2 ( n ) h_2(n) h2​(n) 都是同一个递推方程的解 , c 1 , c 2 c_1 , c_2 c1​,c2​ 是任意常数 , 两个解的线性组合 c 1 h 1 ( n ) + c 2 h 2 ( n ) c_1h_1(n) + c_2h_2(n) c1​h1​(n)+c2​h2​(n) , 这个线性组合也是递推方程的解 ;

下面证明任意一个解都可以表达成通解的格式 ;

假定 h ( n ) h(n) h(n) 是任意一个解 ,

该递推方程有 k k k 个初值如下 :

• h ( 0 ) = b 0 h(0) = b_0 h(0)=b0​
• h ( 1 ) = b 1 h(1) = b_1 h(1)=b1​
• h ( 2 ) = b 2 h(2) = b_2 h(2)=b2​

          ⋮ \ \ \ \ \ \ \ \ \ \vdots          ⋮

• h ( k − 1 ) = b k − 1 h(k-1) = b_{k-1} h(k−1)=bk−1​

将 k k k 个初值 , 代入上述通解格式 H ( n ) = c 1 q 1 n + c 2 q 2 n + ⋯ + c k q k n H(n) = c_1q_1^n + c_2q_2^n + \cdots + c_kq_k^n H(n)=c1​q1n​+c2​q2n​+⋯+ck​qkn​ 中 , 得到如下方程组 :

{ c 1 ′ + c 2 ′ + ⋯ + c k ′ = b 0 c 1 ′ q 1 + c 2 ′ q 2 + ⋯ + c k ′ q k = b 1       ⋮ c 1 ′ q 1 k − 1 + c 2 ′ q 2 k − 1 + ⋯ + c k ′ q k k − 1 = b k − 1 \begin{cases} c_1' + c_2' + \cdots + c_k' = b_0 \\\\ c_1'q_1 + c_2'q_2 + \cdots + c_k'q_k = b_1 \\\\ \ \ \ \ \ \vdots \\\\ c_1' q_1^{k-1}+ c_2' q_2^{k-1}+ \cdots + c_k' q_k^{k-1}= b^{k-1} \end{cases} ⎩⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎨⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎧​c1′​+c2′​+⋯+ck′​=b0​c1′​q1​+c2′​q2​+⋯+ck′​qk​=b1​     ⋮c1′​q1k−1​+c2′​q2k−1​+⋯+ck′​qkk−1​=bk−1​

上述的方程组是否能唯一地确定一组 c 1 , c 2 , ⋯   , c k c_1, c_2, \cdots , c_k c1​,c2​,⋯,ck​ 常数 , 如果可以说明该解是递推方程的通解 , 如果不能 , 则该解不是递推方程的通解 ;

将上述 c 1 , c 2 , ⋯   , c k c_1, c_2, \cdots , c_k c1​,c2​,⋯,ck​ 看做 k k k 个未知数 , 并且 该方程组中有 k k k 个方程 , 该方程组存在唯一解的条件是 :

系数行列式 不等于 0 0 0 ,

符号表示为 : ∏ 1 ≤ i < j ≤ k ( q i − q k ) ≠ 0 \prod\limits_{1 \leq i < j \leq k} ( q_i - q_k ) \not= 0 1≤i