[combinatorics] recursive equation (definition of general solution | structure theorem of general solution of recursive equation without multiple roots)

One 、 General definition

---

The form of the solution of the recursive equation : Satisfy

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 All recursive equations of the formula , All have

c

1

q

1

n

+

c

2

q

2

n

+

⋯

+

c

k

q

k

n

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

c1​q1n​+c2​q2n​+⋯+ck​qkn​ Formal solution ;

Now let's discuss what we got before The form of the solution

c

1

q

1

n

+

c

2

q

2

n

+

⋯

+

c

k

q

k

n

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

c1​q1n​+c2​q2n​+⋯+ck​qkn​ Whether the common pattern of all solutions is summarized ; Whether all items in the sequence follow this pattern ;

If there are some different initial values , Do not follow the above pattern , Then the solution is Can not act as be-all This family Recurrence equation The general format of the solution of ;

Definition of general solution of recursive equation :

If the recurrence equation , Each solution

h

(

n

)

h(n)

h(n) There is a set of constants

c

1

′

,

c

2

′

,

⋯
 

,

c

k

′

c_1' , c_2' , \cdots , c_k'

c1′​,c2′​,⋯,ck′​ ,

bring

h

(

n

)

=

c

1

′

q

1

n

+

c

2

′

q

2

n

+

⋯

+

c

k

′

q

k

n

h(n) = c_1'q_1^n + c_2'q_2^n + \cdots + c_k'q_k^n

h(n)=c1′​q1n​+c2′​q2n​+⋯+ck′​qkn​ establish ,

said

c

1

q

1

n

+

c

2

q

2

n

+

⋯

+

c

k

q

k

n

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

c1​q1n​+c2​q2n​+⋯+ck​qkn​ yes Recursive equation general solution ;

analysis :

The number of solutions of recurrence equation : How many solutions do recursive equations have , Solve the characteristic equation to the characteristic root , Number of characteristic roots , Is the number of solutions of the recursive equation ;

Constant determination :

h

(

n

)

h(n)

h(n) It's the th of the sequence

n

n

n term ,

h

(

n

)

h(n)

h(n) Whether it can be expressed as

c

1

′

q

1

n

+

c

2

′

q

2

n

+

⋯

+

c

k

′

q

k

n

c_1'q_1^n + c_2'q_2^n + \cdots + c_k'q_k^n

c1′​q1n​+c2′​q2n​+⋯+ck′​qkn​ Format , Find a set of constants

c

1

′

,

c

2

′

,

⋯
 

,

c

k

′

c_1' , c_2' , \cdots , c_k'

c1′​,c2′​,⋯,ck′​ , Let the format of the above solution be determined , These constants are confirmed by initial values ;

Two 、 Structure theorem of general solution of recursive equation without multiple roots

---

Structure theorem of general solution of recursive equation without multiple roots :

If

q

1

,

q

2

,

⋯
 

,

q

k

q_1, q_2, \cdots , q_k

q1​,q2​,⋯,qk​ yes Recurrence equation It's not equal Of Characteristic root ,

be

H

(

n

)

=

c

1

q

1

n

+

c

2

q

2

n

+

⋯

+

c

k

q

k

n

H(n) = c_1q_1^n + c_2q_2^n + \cdots + c_kq_k^n

H(n)=c1​q1n​+c2​q2n​+⋯+ck​qkn​ For general solution ;

Casually in recursive equations , Take out an equation , The solution must be

H

(

n

)

=

c

1

q

1

n

+

c

2

q

2

n

+

⋯

+

c

k

q

k

n

H(n) = c_1q_1^n + c_2q_2^n + \cdots + c_kq_k^n

H(n)=c1​q1n​+c2​q2n​+⋯+ck​qkn​ Format , nothing but Different initial values , Corresponding to different

c

1

,

c

2

,

⋯
 

,

c

k

c_1, c_2, \cdots , c_k

c1​,c2​,⋯,ck​ constant ;

Prove the above theorem :

H

(

n

)

=

c

1

q

1

n

+

c

2

q

2

n

+

⋯

+

c

k

q

k

n

H(n) = c_1q_1^n + c_2q_2^n + \cdots + c_kq_k^n

H(n)=c1​q1n​+c2​q2n​+⋯+ck​qkn​ Is the solution of a recursive equation , From the theorem that has been proved before :

• $\iff$

  q Is the characteristic root of the characteristic equation

• $h_1(n)$

  c1​h1​(n)+c2​h2​(n) , This linear combination is also the solution of the recursive equation ;

It is proved that any solution can be expressed in the format of general solution ;

Assume

h

(

n

)

h(n)

h(n) Is any solution ,

The recurrence equation has

k

k

k The initial values are as follows :

• $h(0)=b_0$
• $h(1)=b_1$
• $h(2)=b_2$

         

⋮

\ \ \ \ \ \ \ \ \ \vdots

         ⋮

• $h(k-1)=b_{k-1}$

take

k

k

k An initial value , Substitute the above general solution format

H

(

n

)

=

c

1

q

1

n

+

c

2

q

2

n

+

⋯

+

c

k

q

k

n

H(n) = c_1q_1^n + c_2q_2^n + \cdots + c_kq_k^n

H(n)=c1​q1n​+c2​q2n​+⋯+ck​qkn​ in , The following equations are obtained :

{

c

1

′

+

c

2

′

+

⋯

+

c

k

′

=

b

0

c

1

′

q

1

+

c

2

′

q

2

+

⋯

+

c

k

′

q

k

=

b

1

     

⋮

c

1

′

q

1

k

−

1

+

c

2

′

q

2

k

−

1

+

⋯

+

c

k

′

q

k

k

−

1

=

b

k

−

1

\begin{cases} c_1' + c_2' + \cdots + c_k' = b_0 \\\\ c_1'q_1 + c_2'q_2 + \cdots + c_k'q_k = b_1 \\\\ \ \ \ \ \ \vdots \\\\ c_1' q_1^{k-1}+ c_2' q_2^{k-1}+ \cdots + c_k' q_k^{k-1}= b^{k-1} \end{cases}

⎩⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎨⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎧​c1′​+c2′​+⋯+ck′​=b0​c1′​q1​+c2′​q2​+⋯+ck′​qk​=b1​     ⋮c1′​q1k−1​+c2′​q2k−1​+⋯+ck′​qkk−1​=bk−1​

Whether the above equations can uniquely determine a group

c

1

,

c

2

,

⋯
 

,

c

k

c_1, c_2, \cdots , c_k

c1​,c2​,⋯,ck​ constant , If it can be explained that the solution is the general solution of the recursive equation , If not , Then the solution is not the general solution of the recursive equation ;

Put the above

c

1

,

c

2

,

⋯
 

,

c

k

c_1, c_2, \cdots , c_k

c1​,c2​,⋯,ck​ regard as

k

k

k An unknown number , also There are

k

k

k An equation , The condition for the existence and uniqueness of the solution of this system of equations is :

Coefficient determinant It's not equal to

0

0

0 ,

The symbol is :

∏

1

≤

i

<

j

≤

k

(

q

i

−

q

k

)

≠

0

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

1≤i<j≤k∏​(qi​−qk​)​=0

A word description : The coefficient determinant is all coefficient

q

1

,

q

2

,

⋯
 

,

q

k

−

1

q_1, q_2, \cdots , q_{k-1}

q1​,q2​,⋯,qk−1​ Of The product of two subtractions is not

0

0

0 , namely

q

1

,

q

2

,

⋯
 

,

q

k

−

1

q_1, q_2, \cdots , q_{k-1}

q1​,q2​,⋯,qk−1​ in There is no equality between two ;