当前位置：网站首页>[combinatorics] recursive equation (characteristic equation and characteristic root | example of characteristic equation | root formula of monadic quadratic equation)

[combinatorics] recursive equation (characteristic equation and characteristic root | example of characteristic equation | root formula of monadic quadratic equation)

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

List of articles

One 、 Characteristic equation and characteristic root
Two 、 Characteristic equation and characteristic root Example ( important )

One 、 Characteristic equation and characteristic root

Standard form of linear homogeneous recurrence equation with constant coefficients :

{

(

)

−

(

−

)

−

(

−

)

−

⋯

−

(

−

)

(

)

(

)

(

)

⋯

(

−

)

−

\begin{cases} H(n) - a_1H(n-1) - a_2H(n-2) - \cdots - a_kH(n-k) = 0 \\\\ H(0) = b_0 , H(1) = b_1 , H(2) = b_2 , \cdots , H(k-1) = b_{k-1} \end{cases}

$⎩ ⎪ ⎨ ⎪ ⎧ H (n) - a_{1} H (n - 1) - a_{2} H (n - 2) - \dots - a_{k} H (n - k) = 0 H (0) = b_{0}, H (1) = b_{1}, H (2) = b_{2}, \dots, H (k - 1) = b_{k - 1}$

Constant coefficient It refers to the sequence of numbers Before item coefficient

⋯

a_1 , a_2 , \cdots , a_k

$a_{1}, a_{2}, \dots, a_{k}$ It's all constant ,

≠

a_k \not=0

$a_{k} \neq = 0$ ;

⋯

−

b_0 , b_1, b_2 , \cdots , b_{k-1}

$b_{0}, b_{1}, b_{2}, \dots, b_{k - 1}$ yes Recursive equation

−

k-1

$k - 1$ An initial value ;

Write the characteristic equation :

−

⋯

−

x^k - a_1x^{k-1} - \cdots - a^k = 0

$x^{k} - a_{1} x^{k - 1} - \dots - a^{k} = 0$

Characteristic equation 、 The number of terms of the recursive equation 、 The sub idempotent of the characteristic equation :

Characteristic equation 、 The number of terms of the recursive equation : Number of characteristic equation terms And Constant coefficient linear homogeneous The number of recursion equation terms is the same , Yes
k
+
1
k+1
$k + 1$ term ;
The sub idempotent of the characteristic equation : All in all
k
+
1
k+1
$k + 1$ term , Characteristic equation term
x
x
$x$ Power of power from
k
k
$k$ To
0
0
$0$ , All in all
k
+
1
k + 1
$k + 1$ term ;

Recurrence equation And Characteristic equation relation :

x
k
x^k
$x^{k}$ The coefficient before
1
1
$1$ Corresponding
H
(
n
)
H(n)
$H (n)$ Coefficient before item
1
1
$1$ ;
x
k
−
1
x^{k-1}
$x^{k - 1}$ The coefficient before
−
a
1
-a_1
$- a_{1}$ Corresponding
H
(
n
−
1
)
H(n-1)
$H (n - 1)$ Coefficient before item
−
a
1
-a_1
$- a_{1}$ ;

⋮

\vdots

$⋮$

$x^{0}x0 The coefficient before − a k -a_k−ak Corresponding H ( n − k ) H(n-k)H(n−k) Coefficient before item − a k -a_k−ak ;$

from 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$

Can export

$1$ element

$k$ Sub characteristic equation :

−

⋯

−

x^k - a_1x^{k-1} - \cdots - a^k = 0

$x^{k} - a_{1} x^{k - 1} - \dots - a^{k} = 0$

The

$1$ element

$k$ Sub characteristic equation be called Of the original recursive equation Characteristic equation ;

The

$1$ element

$k$ Sub characteristic equation Yes

$k$ A root , be called Recurrence equation The characteristic root of the ;

From recurrence equation to characteristic equation ( a key ) :

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 ;

Solve the above characteristic equation , You can get the characteristic root , Generally, it is a quadratic equation with one variable ;

Univariate quadratic equation form

ax^2 + bx + c = 0

$a x^{2} + b x + c = 0$

The solution is :

−

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

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

Two 、 Characteristic equation and characteristic root Example ( important )

1 . Fibonacci sequence example :

( 1 ) Fibonacci sequence :

⋯

1 , 1 , 2 , 3 , 5 , 8 , 13 , \cdots

$1, 1, 2, 3, 5, 8, 13, \dots$

( 2 ) Recurrence equation :

(

)

(

−

)

(

−

)

F(n) = F(n-1) + F(n-2)

$F (n) = F (n - 1) + F (n - 2)$

describe : The first

$n$ Item equal to

−

n-1

$n - 1$ term and The first

−

n-2

$n - 2$ Sum of items ;

Such as : The first

$4$ Item value

(

)

F(4) = 5

$F (4) = 5$ , Is equal to

The first

−

4-1=3

$4 - 1 = 3$ Item value

(

−

)

(

)

F(4-1)=F(3) = 3

$F (4 - 1) = F (3) = 3$

add The first

−

4-2=2

$4 - 2 = 2$ Item value

(

−

)

(

)

F(4-2) = F(2) =2

$F (4 - 2) = F (2) = 2$ ;

( 3 ) initial value :

(

)

(

)

F(0) = 1 , F(1) = 1

$F (0) = 1, F (1) = 1$

according to

(

)

(

)

F(0) = 1, F(1) = 1

$F (0) = 1, F (1) = 1$ You can calculate

(

)

F(2)

$F (2)$ , according to

(

)

(

)

F(1),F(2)

$F (1), F (2)$ You can calculate

(

)

F(3)

$F (3)$ , according to

(

)

(

)

F(2)F(3)

$F (2) F (3)$ Sure Calculation

(

)

F(4)

$F (4)$ ,

⋯

\cdots

$\dots$ , according to

(

−

)

(

−

)

F(n-2) , F(n-1)

$F (n - 2), F (n - 1)$ You can calculate

(

)

F(n)

$F (n)$ ;

2 . Write the characteristic equation of Fibonacci sequence :

Recurrence equation :

(

)

(

−

)

(

−

)

F(n) = F(n-1) + F(n-2)

$F (n) = F (n - 1) + F (n - 2)$

( 1 ) The standard form of recurrence equation :

(

)

−

(

−

)

−

(

−

)

F(n) - F(n-1) - F(n-2) = 0

$F (n) - F (n - 1) - F (n - 2) = 0$

( 2 ) Recursive equation writing :

① First determine the number of terms of the characteristic equation : The same number of terms as the recursive equation ,

$3$ term ;

② In determining the characteristic equation

$x$ Power of power : from

−

3-1=2

$3 - 1 = 2$ To

$0$ ;

③ Write a recurrence equation without coefficients :

x^2 + x^1 + x^0 = 0

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

④ Filling factor : Then the characteristic equation without coefficients

x^2 + x^1 + x^0 = 0

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

(

)

−

(

−

)

−

(

−

)

F(n) - F(n-1) - F(n-2) = 0

$F (n) - F (n - 1) - F (n - 2) = 0$ The coefficients of corresponding bits are filled into the characteristic equation :

$x^2x2 The coefficient before Corresponding F ( n ) F(n)F(n) Coefficient before item 1 11 ;$
$x^1x1 The coefficient before Corresponding F ( n − 1 ) F(n-1)F(n−1) Coefficient before item − 1 -1−1 ;$
$x^0x0 The coefficient before Corresponding F ( n − 2 ) F(n-2)F(n−2) Coefficient before item − 1 -1−1 ;$

Then the final The characteristic equation is

(

−

)

(

−

)

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

$1 x^{2} + (- 1) x^{1} + (- 1) x^{0} = 0$ , It is reduced to :

−

x^2 - x - 1 = 0

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

The characteristic root of the characteristic equation is : The solution of the above equation is the characteristic root , Generally, it is a quadratic equation with one variable ;

x = \cfrac{1 \pm \sqrt{5}}{2}

$x = \frac{1 \pm 5}{2}$

Reference resources : Univariate quadratic equation form
a
x
2
+
b
x
+
c
=
0
ax^2 + bx + c = 0
$a x^{2} + b x + c = 0$
The solution is :
x
=
−
b
±
b
2
−
4
a
c
2
a
x = \cfrac{-b \pm \sqrt{b^2 - 4ac}}{2a}
$x = \frac{- b \pm b ^{2} - 4 a c}{2 a}$