当前位置：网站首页>[combinatorics] recursive equation (the relationship theorem between the solution of the recursive equation and the characteristic root | the linear property theorem of the solution of the recursive e

[combinatorics] recursive equation (the relationship theorem between the solution of the recursive equation and the characteristic root | the linear property theorem of the solution of the recursive e

2022-07-03 16:53:00 【Programmer community】

List of articles

One 、 The relation theorem between the solution of recurrence equation and characteristic root
Two 、 The linear property theorem of the solution of recurrence equation
3、 ... and 、 The form of the solution of the recursive equation

One 、 The relation theorem between the solution of recurrence equation and characteristic root

Characteristic root And Solution of recurrence equation There is a relationship between , If you know the inner connection , Can According to characteristic root , Write the pattern of the solution of the recursive equation , namely general solution ;

Recurrence equation solution and characteristic root correlation theorem :

$q$ Right and wrong

$0$ The plural , Then there is the following equivalence relationship :

$q$ Is the characteristic root of the characteristic equation

⇔

\Leftrightarrow

$\Leftrightarrow$

q^n

$q^{n}$ Is the solution of a recursive equation *

Prove the above theorem :

By definition , take Solution of recurrence equation

q^n

$q^{n}$ , Into the original recursive equation ,

The solution of the recurrence equation is

q^n

$q^{n}$ , On behalf of The first

$n$ The value of the item is

q^n

$q^{n}$ , namely

(

)

H(n) = q^n

$H (n) = q^{n}$ ;

Recurrence equation :

(

)

−

(

−

)

−

(

−

)

−

⋯

−

(

−

)

H(n) - a_1H(n-1) - a_2H(n-2) - \cdots - a_kH(n-k) = 0

$H (n) - a_{1} H (n - 1) - a_{2} H (n - 2) - \dots - a_{k} H (n - k) = 0$ ,

The first $q^n$
$q^{n}$
The first $q^{n-1}$
$q^{n - 1}$
The first $q^{n-2}$
$q^{n - 2}$

⋮

\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \vdots

$⋮$

The first $q^{n-k}$
$q^{n - k}$

After substitution, the result is :

\ \ \ \ \ q^n

$q^{n}$ Is the solution of a recursive equation

⇔

−

⋯

−

\Leftrightarrow q^n - a_1q^{n-1} - a_2q^{n-2} - \cdots - a_kq^{n-k} = 0

$\Leftrightarrow q^{n} - a_{1} q^{n - 1} - a_{2} q^{n - 2} - \dots - a_{k} q^{n - k} = 0$

take

−

q^{n-k}

$q^{n - k}$ Extracted as a common factor ;

⇔

−

(

−

⋯

−

)

\Leftrightarrow q^{n-k} ( q^k - a_1q^{k-1} - a_2q^{k-2} - \cdots - a_k ) = 0

$\Leftrightarrow q^{n - k} (q^{k} - a_{1} q^{k - 1} - a_{2} q^{k - 2} - \dots - a_{k}) = 0$

The product of the above two is

$0$ ,

−

q^{n-k}

$q^{n - k}$ Definitely not

$0$ , Then the rest of the result is

$0$ ;

⇔

−

⋯

−

\Leftrightarrow q^k - a_1q^{k-1} - a_2q^{k-2} - \cdots - a_k = 0

$\Leftrightarrow q^{k} - a_{1} q^{k - 1} - a_{2} q^{k - 2} - \dots - a_{k} = 0$

The above equation , Exactly the characteristic equation , The solution of the characteristic equation , Is the characteristic root

$q$ ;

⇔

\Leftrightarrow

$\Leftrightarrow$

$q$ Is the characteristic root

Two 、 The linear property theorem of the solution of recurrence equation

The linear property theorem of the solution of recurrence equation :

(

)

h_1(n)

$h_{1} (n)$ and

(

)

h_2(n)

$h_{2} (n)$ Are the solutions of the same recursive equation ,

c_1 , c_2

$c_{1}, c_{2}$ It's an arbitrary constant ,

Use these two solutions as A linear combination ,

(

)

(

)

c_1h_1(n) + c_2h_2(n)

$c_{1} h_{1} (n) + c_{2} h_{2} (n)$ , This linear combination is also the solution of the recursive equation ;

Method of proof :

take

(

)

(

)

c_1h_1(n) + c_2h_2(n)

$c_{1} h_{1} (n) + c_{2} h_{2} (n)$ The combination is substituted into the left formula of the recursive equation , It is reduced to

$0$ ;

Recurrence equation :

(

)

−

(

−

)

−

(

−

)

−

⋯

−

(

−

)

H(n) - a_1H(n-1) - a_2H(n-2) - \cdots - a_kH(n-k) = 0

$H (n) - a_{1} H (n - 1) - a_{2} H (n - 2) - \dots - a_{k} H (n - k) = 0$ ,

take

(

)

(

)

c_1h_1(n) + c_2h_2(n)

$c_{1} h_{1} (n) + c_{2} h_{2} (n)$ The linear combination is substituted into the above equation ,

$c 1 h 1 (n) + c 2 h 2 (n) c_1h_1(n) + c_2h_2(n) c_{1} h_{1} (n) + c_{2} h_{2} (n) Instead of$
$H (n)$ Use
$c_1h_1(n-1) + c_2h_2(n-1)c1h1(n−1)+c2h2(n−1) Instead of$
$c_1h_1(n-2) + c_2h_2(n-2)c1h1(n−2)+c2h2(n−2) Instead of$
$c_1h_1(n-k) + c_2h_2(n-k)c1h1(n−k)+c2h2(n−k) Instead of$

obtain :

(

)

(

)

(c_1h_1(n) + c_2h_2(n))

$(c_{1} h_{1} (n) + c_{2} h_{2} (n))$

−

$-$

(

a_1(

$a_{1} ($

(

−

)

(

−

)

c_1h_1(n-1) + c_2h_2(n-1)

$c_{1} h_{1} (n - 1) + c_{2} h_{2} (n - 1)$

)

−

) - a_2

$) - a_{2}$

(

−

)

(

−

)

(c_1h_1(n-2) + c_2h_2(n-2))

$(c_{1} h_{1} (n - 2) + c_{2} h_{2} (n - 2))$

−

⋯

−

(

- \cdots - a_k(

$- \dots - a_{k} ($

(

−

)

(

−

)

c_1h_1(n-k) + c_2h_2(n-k)

$c_{1} h_{1} (n - k) + c_{2} h_{2} (n - k)$

)

) = 0

$) = 0$

Will all contain

c_1h_1

$c_{1} h_{1}$ Merge items together , Will all contain

c_2h_2

$c_{2} h_{2}$ The item , Merge together , obtain :

(

)

−

(

−

)

−

(

−

)

−

⋯

−

(

−

)

c_1( h_1(n) - a_1h_1(n-1) - a_2h_1(n-2) - \cdots - a_kh_1(n-k))

$c_{1} (h_{1} (n) - a_{1} h_{1} (n - 1) - a_{2} h_{1} (n - 2) - \dots - a_{k} h_{1} (n - k))$

$+$

(

)

−

(

−

)

−

(

−

)

−

⋯

−

(

−

)

c_2( h_2(n) - a_1h_2(n-1) - a_2h_2(n-2) - \cdots - a_kh_k(n-k))

$c_{2} (h_{2} (n) - a_{1} h_{2} (n - 1) - a_{2} h_{2} (n - 2) - \dots - a_{k} h_{k} (n - k))$

= 0

$= 0$

In the above formula The blue part and The red part The difference is

$0$

$h_1(n)h1(n) Is the solution of a recursive equation , therefore c 1 ( h 1 ( n ) − a 1 h 1 ( n − 1 ) − a 2 h 1 ( n − 2 ) − ⋯ − a k h 1 ( n − k ) ) c_1( h_1(n) - a_1h_1(n-1) - a_2h_1(n-2) - \cdots - a_kh_1(n-k))c1(h1(n)−a1h1(n−1)−a2h1(n−2)−⋯−akh1(n−k)) The value of is 0 00 ;$
$h_2(n)h2(n) Is the solution of a recursive equation , therefore c 2 ( h 2 ( n ) − a 1 h 2 ( n − 1 ) − a 2 h 2 ( n − 2 ) − ⋯ − a k h k ( n − k ) ) c_2( h_2(n) - a_1h_2(n-1) - a_2h_2(n-2) - \cdots - a_kh_k(n-k))c2(h2(n)−a1h2(n−1)−a2h2(n−2)−⋯−akhk(n−k)) The value of is 0 00 ;$

3、 ... and 、 The form of the solution of the recursive equation

Put the previous “ The relation theorem between the solution of recurrence equation and characteristic root ” And “ The linear property theorem of the solution of recurrence equation ” Bind together , Can According to characteristic root , Write the solution of the recursive equation ;

Assume

⋯

q_1 , q_2 , \cdots , q_k

$q_{1}, q_{2}, \dots, q_{k}$ Is the characteristic root of a recursive equation , One yuan

$k$ The quadratic equation has

$k$ A root ;

according to “ The relation theorem between the solution of recurrence equation and characteristic root ” ,

⋯

q_1^n, q_2^n , \cdots , q_k^n

$q_{1}^{n}, q_{2}^{n}, \dots, q_{k}^{n}$ Are the solutions of recursive equations ,

Will this

$k$ A solution , Make a linear combination ,

⋯

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}$ ,

according to “ The linear property theorem of the solution of recurrence equation ” , The above linear combination

⋯

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}$ It is also the solution of the recursive equation ;

At this time, a form of the solution of the recursive equation is found ;

Sum up the process :

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$ ;
Number of terms of characteristic equation : determine Number of terms of characteristic equation , And The recurrence equation has the same number of terms ;
The characteristic equation is sub idempotent : The highest power is Number of terms of characteristic equation $00 0;$
$- 1$ , Lowest power
Write There is no coefficient The characteristic equation of ;
The coefficients of the recursive equation will be deduced bit by bit Copy Into the characteristic equation ;
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}$
Construct the solution of the recursive 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 ;