[combinatorics] recursive equation (constant coefficient linear homogeneous recursive equation | constant coefficient, linear, homogeneous concept description | constant coefficient linear homogeneous

One 、 Linear homogeneous recurrence equation with constant coefficients

---

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

)

=

b

k

\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) = b_k \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)=bk​​

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 ;

Homogeneous It refers to moving the sequence item to the left , The right term is equal to

0

0

0 ;

The above is called

k

k

k rank Linear homogeneous recurrence equation with constant coefficients ;

b

0

,

b

1

,

b

2

,

⋯
 

,

b

k

b_0 , b_1, b_2 , \cdots , b_k

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

k

k

k An initial value ;

Two 、 Constant coefficient 、 linear 、 Homogeneous Concept description

---

Constant coefficient 、 linear 、 Homogeneous Concept description :

1 . Constant coefficient concept : Constant coefficient refers to

T

(

n

)

,

T

(

n

−

1

)

T(n) , T(n-1)

T(n),T(n−1) these Coefficient before term , It's all constant , Such as

2

T

(

n

−

1

)

2 T(n-1)

2T(n−1) ,

T

(

n

−

1

)

T(n-1)

T(n−1) The coefficient before the term is constant

2

2

2 ;

The recurrence equation introduced in chestnut before , Such as

• Hanoi Tower recursive equation $T(n)=2T(n-1)+1$
• Insert sort recurrence equation $W(n)=W(n-1)+n-1$

All are Constant coefficient linear recurrence equation , Not homogeneous ;

2 . Linear concept : The first

n

n

n Items are the previous items

n

−

1

n-1

n−1 Of A linear combination , There is no exponential relationship , So it becomes linear ;

3 . Homogeneous concept : stay

T

(

n

)

T(n)

T(n) There are no other elements besides the item , Only items , Above

T

(

n

)

=

2

T

(

n

−

1

)

+

1

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

T(n)=2T(n−1)+1 There is a constant beyond the term

1

1

1 , The recursive equation is not homogeneous ; If change to

T

(

n

)

=

2

T

(

n

−

1

)

T(n) =2 T(n-1)

T(n)=2T(n−1) , The recursive equation is homogeneous ;

3、 ... and 、 The formula solution of linear homogeneous recurrence equation with constant coefficients

---

1 . Characteristic root 、 general solution 、 Special solution

Characteristic root : According to the original Recurrence equation , Find out Characteristic root ;

general solution : utilize Characteristic root , Write general solution ;

Special solution : according to general solution , Substitute into the initial value of the recursive equation , Get... For these initial values Special solution , That is, the solution of the sequence ,

2 . The relationship between general solution and special solution :

Recurrence equation and initial value : The dependence of recurrence equation , Recursive equations express more than one sequence , The recurrence equation is Express an infinite sequence of numbers with the same dependencies , Different initial values of recurrence equations , Corresponding to different series , Recurrence equation and The initial value can only determine a sequence ;

Recurrence equation 、 Understand the relationship : general solution It's actually a recursive equation Corresponding Infinite series The common solution of , and A sequence cannot be uniquely determined ;

Special solution 、 Sequence relation : Some undetermined coefficients of the general solution , It should be determined by the initial value , The general solution is substituted into the initial value , Got Special solution , To uniquely determine a given sequence ;

Four 、 Outline of the formula solution of linear homogeneous recurrence equation with constant coefficients

---

Outline of the solution of recurrence equation formula :

• Characteristic equation and characteristic root
• The relation between the solution of recurrence equation and characteristic root
• Linear properties of solutions
• General solution structure without multiple roots
• There is a general solution structure under double roots