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

One 、 Characteristic equation and characteristic root

---

Standard form of linear homogeneous recurrence equation with constant coefficients :

{

H

(

n

)

−

a

1

H

(

n

−

1

)

−

a

2

H

(

n

−

2

)

−

⋯

−

a

k

H

(

n

−

k

)

=

0

H

(

0

)

=

b

0

,

H

(

1

)

=

b

1

,

H

(

2

)

=

b

2

,

⋯
 

,

H

(

k

−

1

)

=

b

k

−

1

\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)−a1​H(n−1)−a2​H(n−2)−⋯−ak​H(n−k)=0H(0)=b0​,H(1)=b1​,H(2)=b2​,⋯,H(k−1)=bk−1​​

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

a

1

,

a

2

,

⋯
 

,

a

k

a_1 , a_2 , \cdots , a_k

a1​,a2​,⋯,ak​ It's all constant ,

a

k

≠

0

a_k \not=0

ak​​=0 ;

b

0

,

b

1

,

b

2

,

⋯
 

,

b

k

−

1

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

b0​,b1​,b2​,⋯,bk−1​ yes Recursive equation

k

−

1

k-1

k−1 An initial value ;

Write the characteristic equation :

x

k

−

a

1

x

k

−

1

−

⋯

−

a

k

=

0

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

xk−a1​xk−1−⋯−ak=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

  xk 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}

  xk−1 The coefficient before

  −

  a

  1

  -a_1

  −a1​ Corresponding

  H

  (

  n

  −

  1

  )

  H(n-1)

  H(n−1) Coefficient before item

  −

  a

  1

  -a_1

  −a1​ ;

⋮

\vdots

⋮

• $x^0$

from Recurrence equation :

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

Can export

1

1

1 element

k

k

k Sub characteristic equation :

x

k

−

a

1

x

k

−

1

−

⋯

−

a

k

=

0

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

xk−a1​xk−1−⋯−ak=0

The

1

1

1 element

k

k

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

The

1

1

1 element

k

k

k Sub characteristic equation Yes

k

k

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

  0

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

a

x

2

+

b

x

+

c

=

0

ax^2 + bx + c = 0

ax2+bx+c=0

The solution is :

x

=

−

b

±

b

2

−

4

a

c

2

a

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

x=2a−b±b2−4ac
​​

Two 、 Characteristic equation and characteristic root Example ( important )

---

1 . Fibonacci sequence example :

( 1 ) Fibonacci sequence :

1

,

1

,

2

,

3

,

5

,

8

,

13

,

⋯

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

1,1,2,3,5,8,13,⋯

( 2 ) Recurrence equation :

F

(

n

)

=

F

(

n

−

1

)

+

F

(

n

−

2

)

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

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

describe : The first

n

n

n Item equal to

n

−

1

n-1

n−1 term and The first

n

−

2

n-2

n−2 Sum of items ;

Such as : The first

4

4

4 Item value

F

(

4

)

=

5

F(4) = 5

F(4)=5 , Is equal to

The first

4

−

1

=

3

4-1=3

4−1=3 Item value

F

(

4

−

1

)

=

F

(

3

)

=

3

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

F(4−1)=F(3)=3

add The first

4

−

2

=

2

4-2=2

4−2=2 Item value

F

(

4

−

2

)

=

F

(

2

)

=

2

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

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

according to

F

(

0

)

=

1

,

F

(

1

)

=

1

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

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

F

(

2

)

F(2)

F(2) , according to

F

(

1

)

,

F

(

2

)

F(1),F(2)

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

F

(

3

)

F(3)

F(3) , according to

F

(

2

)

F

(

3

)

F(2)F(3)

F(2)F(3) Sure Calculation

F

(

4

)

F(4)

F(4) ,

⋯

\cdots

⋯ , according to

F

(

n

−

2

)

,

F

(

n

−

1

)

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

F(n−2),F(n−1) You can calculate

F

(

n

)

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)

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

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

3

3 term ;

② In determining the characteristic equation

x

x

x Power of power : from

3

−

1

=

2

3-1=2

3−1=2 To

0

0

0 ;

③ Write a recurrence equation without coefficients :

x

2

+

x

1

+

x

0

=

0

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

x2+x1+x0=0

④ Filling factor : Then the characteristic equation without coefficients

x

2

+

x

1

+

x

0

=

0

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

x2+x1+x0=0 And

F

(

n

)

−

F

(

n

−

1

)

−

F

(

n

−

2

)

=

0

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^2$
• $x^1$
• $x^0$

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

1x2+(−1)x1+(−1)x0=0 , It is reduced to :

x

2

−

x

−

1

=

0

x^2 - x - 1 = 0

x2−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

=

1

±

5

2

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

x=21±5
​​

Reference resources : Univariate quadratic equation form

a

x

2

+

b

x

+

c

=

0

ax^2 + bx + c = 0

ax2+bx+c=0
The solution is :

x

=

−

b

±

b

2

−

4

a

c

2

a

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

x=2a−b±b2−4ac
​​