当前位置：网站首页>[combinatorics] recursive equation (definition of general solution | structure theorem of general solution of recursive equation without multiple roots)

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

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

List of articles

One 、 General definition
Two 、 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_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$ All recursive equations of the formula , All have

⋯

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}$ Formal solution ;

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

⋯

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}$ 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)$ There is a set of constants

′

⋯

′

c_1' , c_2' , \cdots , c_k'

$c_{1}^{'}, c_{2}^{'}, \dots, c_{k}^{'}$ ,

bring

(

)

′

⋯

′

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

$h (n) = c_{1}^{'} q_{1}^{n} + c_{2}^{'} q_{2}^{n} + \dots + c_{k}^{'} q_{k}^{n}$ establish ,

said

⋯

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}$ 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)$ It's the th of the sequence

$n$ term ,

(

)

h(n)

$h (n)$ Whether it can be expressed as

′

⋯

′

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

$c_{1}^{'} q_{1}^{n} + c_{2}^{'} q_{2}^{n} + \dots + c_{k}^{'} q_{k}^{n}$ Format , Find a set of constants

′

⋯

′

c_1' , c_2' , \cdots , c_k'

$c_{1}^{'}, c_{2}^{'}, \dots, c_{k}^{'}$ , 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 :

⋯

q_1, q_2, \cdots , q_k

$q_{1}, q_{2}, \dots, q_{k}$ yes Recurrence equation It's not equal Of Characteristic root ,

(

)

⋯

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

$H (n) = c_{1} q_{1}^{n} + c_{2} q_{2}^{n} + \dots + c_{k} q_{k}^{n}$ For general solution ;

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

(

)

⋯

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

$H (n) = c_{1} q_{1}^{n} + c_{2} q_{2}^{n} + \dots + c_{k} q_{k}^{n}$ Format , nothing but Different initial values , Corresponding to different

⋯

c_1, c_2, \cdots , c_k

$c_{1}, c_{2}, \dots, c_{k}$ constant ;

Prove the above theorem :

(

)

⋯

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

$H (n) = c_{1} q_{1}^{n} + c_{2} q_{2}^{n} + \dots + c_{k} q_{k}^{n}$ Is the solution of a recursive equation , From the theorem that has been proved before :

$q q ⇔ \Leftrightarrow q n q^n Is the solution of a recursive equation$
$q$ Is the characteristic root of the characteristic equation
$h_1(n)h1(n) and h 2 ( n ) h_2(n)h2(n) Are the solutions of the same recursive equation , c 1 , c 2 c_1 , c_2c1,c2 It's an arbitrary constant , Linear combination of two solutions 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)$ , 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)$ Is any solution ,

The recurrence equation has

$k$ The initial values are as follows :

$b_0h(0)=b0$
$b_1h(1)=b1$
$b_2h(2)=b2$

⋮

\ \ \ \ \ \ \ \ \ \vdots

$⋮$

$b_{k-1}h(k−1)=bk−1$

take

$k$ An initial value , Substitute the above general solution format

(

)

⋯

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

$H (n) = c_{1} q_{1}^{n} + c_{2} q_{2}^{n} + \dots + c_{k} q_{k}^{n}$ in , The following equations are obtained :

{

′

⋯

′

⋯

′

⋮

′

−

′

−

⋯

′

−

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

$⎩ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎨ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎧ c_{1}^{'} + c_{2}^{'} + \dots + c_{k}^{'} = b_{0} c_{1}^{'} q_{1} + c_{2}^{'} q_{2} + \dots + c_{k}^{'} q_{k} = b_{1} ⋮ c_{1}^{'} q_{1}^{k - 1} + c_{2}^{'} q_{2}^{k - 1} + \dots + c_{k}^{'} q_{k}^{k - 1} = b^{k - 1}$

Whether the above equations can uniquely determine a group

⋯

c_1, c_2, \cdots , c_k

$c_{1}, c_{2}, \dots, c_{k}$ 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 ;