当前位置：网站首页>[combinatorics] recursive equation (the problem of solving recursive equation with multiple roots | the problem is raised)

[combinatorics] recursive equation (the problem of solving recursive equation with multiple roots | the problem is raised)

2022-07-03 17:13:00 【Programmer community】

List of articles

One 、 The problem of solving recurrence equations with multiple roots
Two 、 Examples of recurrence equations with multiple roots

One 、 The problem of solving recurrence equations with multiple roots

There are some Recurrence equation Of Characteristic equation Of Characteristic root Yes Heavy root The situation of , The characteristic equation is solved Some of the characteristic roots are equal , So that makes Constants in the general solution cannot obtain unique values ;

Reference resources : 【 Combinatorial mathematics 】 Recurrence equation ( General definition | Structure theorem of general solution of recursive equation without multiple roots ) Two 、 Structure theorem of general solution of recursive equation without multiple roots

stay “ Structure theorem of general solution of recursive equation without multiple roots ” In the chapter , General understanding requirements In the system of equations The coefficient determinant is not equal to

$0$ ,

∏

≤

(

−

)

≠

\prod\limits_{1 \leq i < j \leq k} ( q_i - q_k ) \not= 0

$1 \leq i < j \leq k \prod (q_{i} - q_{k}) \neq = 0$ , If there are two characteristic roots

q_i , q_k

$q_{i}, q_{k}$ equal , The top " The coefficient determinant is not equal to

$0$ " It cannot be achieved ;

If the characteristic equation has multiple roots , You can't use it “ Formula solution of recurrence equation without multiple roots ” Solve the recursive equation ;

For recursive equations with multiple roots , Needs to be Linearly independent elements All found , Linear combination , To get a general solution ;

A linear combination : Multiply a solution by

c_1

$c_{1}$ , The other solution is multiplied by

c_2

$c_{2}$ , The combination after adding ;

Two 、 Examples of recurrence equations with multiple roots

Recurrence equation :

(

)

−

(

−

)

(

−

)

H(n) - 4H(n-1) + 4H(n-2) = 0

$H (n) - 4 H (n - 1) + 4 H (n - 2) = 0$

initial value :

(

)

(

)

H(0) = 0 , H(1) = 1

$H (0) = 0, H (1) = 1$

Complete process of solving recursive equations without multiple roots :
1 . Write the characteristic equation :
( 1 ) The standard form of recurrence equation : Write the recurrence equation Standard form , All items are to the left of the equal sign , On the right is
$0$ ;
( 2 ) Number of terms of characteristic equation : determine Number of terms of characteristic equation , And The recurrence equation has the same number of terms ;
( 3 ) The characteristic equation is sub idempotent : The highest power is Number of terms of characteristic equation $00 0;$
$- 1$ , Lowest power
( 4 ) Write There is no coefficient The characteristic equation of ;
( 5 ) The coefficients of the recursive equation will be deduced bit by bit Copy Into the characteristic equation ;
2 . Solution characteristic root : take The eigenvalue of the characteristic equation is solved , $\cfrac{-b \pm \sqrt{b^2 - 4ac}}{2a}$
$x = \frac{- b \pm b ^{2} - 4 a c}{2 a}$
3 . Construct the general solution of recurrence equation : structure $c_1q_1^n + c_2q_2^n + \cdots + c_kq_k^n$
$c_{1} q_{1}^{n} + c_{2} q_{2}^{n} + \dots + c_{k} q_{k}^{n}$ Linear combination of forms , The linear combination is the solution of the recursive equation ;
4 . Find the constant in the general solution : Substitute the initial value of the recursive equation into the general solution , obtain

Solve according to the above solution process :

1 . Characteristic equation :

( 1 ) The standard form of recurrence equation : Recursive equations are already in standard form ;

( 2 ) Number of terms of characteristic equation : And The number of terms of recurrence equation identical ,

$3$ term ;

( 3 ) The characteristic equation is sub idempotent : The highest power is The number of terms of the characteristic equation minus one ,

−

3-1=2

$3 - 1 = 2$ , Lowest power

$0$ ;

( 4 ) Write There is no coefficient The characteristic equation of :

x^2 + x + 1 = 0

$x^{2} + x + 1 = 0$

( 5 ) The coefficients of the recursive equation will be deduced bit by bit Copy Into the characteristic equation ;

(

−

)

(

)

1x^2 + (-4)x + (4)1 = 0

$1 x^{2} + (- 4) x + (4) 1 = 0$

−

x^2 - 4x + 4 = 0

$x^{2} - 4 x + 4 = 0$

2 . Solution characteristic root : take The eigenvalue of the characteristic equation is solved ,

−

x = \cfrac{-b \pm \sqrt{b^2 - 4ac}}{2a}

$x = \frac{- b \pm b ^{2} - 4 a c}{2 a}$

−

x=\cfrac{4 \pm \sqrt{16 - 16}}{2} = 2

$x = \frac{4 \pm 1 6 - 1 6}{2} = 2$

Both characteristic roots are

$2$ ,

q_1=2, q_2 = 2

$q_{1} = 2, q_{2} = 2$ ;

3 . Construct the general solution of recurrence equation : structure

⋯

c_1q_1^n + c_2q_2^n + \cdots + c_kq_k^n

$c_{1} q_{1}^{n} + c_{2} q_{2}^{n} + \dots + c_{k} q_{k}^{n}$ Linear combination of forms , The linear combination is the solution of the recursive equation ;