当前位置：网站首页>[combinatorics] recursive equation (special solution example 1 Hannover tower complete solution process | special solution example 2 special solution processing when the characteristic root is 1)

[combinatorics] recursive equation (special solution example 1 Hannover tower complete solution process | special solution example 2 special solution processing when the characteristic root is 1)

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

List of articles

One 、 Special solution example 1 ( Hanoi )
Two 、 Special solution example 2 ( The characteristic root is 1 The situation of )

One 、 Special solution example 1 ( Hanoi )

Hanoi problem :

The recurrence equation is :
initial value :

Find the solution of the recursive equation ?

Solve its special solution first

1 . Special solution form :

On the left side of the above recursive equation is “ Linear homogeneous recurrence equation with constant coefficients ” form , Never mind ,

On the right side of the

$1$ Related to special solutions ,

$1$ by

$n$ Of

$0$ Sub polynomial ,

Therefore, the special solution

∗

(

)

H^*(n)

$H^{*} (n)$ It's also

$n$ Of

$0$ Sub polynomial ;

2 . Write the special solution form :

Number of special solutions : be Number of special solutions yes

0 + 1 = 1

$0 + 1 = 1$ term ;

Understand each component : Each term is explained by constant multiply

$n$ Power of power form ,

1
1
$1$ It's a constant Set to
P
1
P_1
$P_{1}$ ,
1
1
$1$ individual
n
n
$n$ Power of power , Power value
0
0
$0$ ,

Therefore, the form of the special solution is

∗

(

)

T^*(n) = P_1n^0

$T^{*} (n) = P_{1} n^{0}$ ,

It is reduced to :

∗

(

)

T^*(n) = P_1

$T^{*} (n) = P_{1}$

3 . Put the special solution into the recursive equation :

Will explain

∗

(

)

T^*(n) = P_1

$T^{*} (n) = P_{1}$ ,

Into the recursive equation

(

)

(

−

)

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

$T (n) = 2 T (n - 1) + 1$ in ,

obtain :

P_1 = 2P_1 + 1

$P_{1} = 2 P_{1} + 1$

The result of solving the equation :

−

P_1 = -1

$P_{1} = - 1$

The special solution is :

∗

(

)

−

T^*(n) = -1

$T^{*} (n) = - 1$

The whole process of solving recursive equations : Solve the above Hanoi Tower Linear homogeneous recurrence equation with constant coefficients General solution of part ,

(

)

−

(

−

)

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

$T (n) - 2 T (n - 1) = 0$ ;

1 . Characteristic equation :

( 1 ) 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$ ;

(

)

−

(

−

)

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

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

( 2 ) Number of terms of characteristic equation : determine Number of terms of characteristic equation , And The recurrence equation has the same number of terms ;

$2$ term ;

( 3 ) The characteristic equation is sub idempotent : The highest power is Number of terms of characteristic equation

−

-1

$- 1$ , Lowest power

$0$ ;

Lowest power

$0$ , Highest power

$1$ ;

( 4 ) Write There is no coefficient The characteristic equation of ;

x + 1 = 0

$x + 1 = 0$

( 5 ) The coefficients of the recursive equation will be deduced bit by bit Copy Into the characteristic equation ;

−

x - 2 = 0

$x - 2 = 0$

2 . Solution characteristic root : take Characteristic equation Characteristic root Work it out ,

−

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

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

Characteristic root

q_1=2

$q_{1} = 2$ ;

3 . Construct the general solution of recurrence equation :

( 1 ) No double root : structure

⋯

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}$ Linear combination of forms , This linear combination is the of recursive equations general solution ;

The homogeneous partial general solution of the recurrence equation is :

(

)

‾

\overline{T(n)} = c2^n

$\overline{T (n)} = c 2^{n}$

“ Linear Nonhomogeneous recurrence equation with constant coefficients ” The general solution is

(

)

(

)

‾

∗

(

)

T(n) = \overline{T(n)} + T^*(n)

$T (n) = \overline{T (n)} + T^{*} (n)$

The special solution of the nonhomogeneous part is :

∗

(

)

−

T^*(n) = -1

$T^{*} (n) = - 1$

Therefore, the general solution of Hanoi Tower recurrence equation is :

(

)

−

T(n) = c2^n - 1

$T (n) = c 2^{n} - 1$

( 2 ) Double root : Refer to the following “ The general solution form under the double root is listed ” Content ;

4 . Find the constant in the general solution :

( 1 ) Substitute the initial values to obtain the equations : Substitute the initial value of the recursive equation into the general solution , obtain

$k$ individual

$k$ Finite element equations , adopt Solve the equations , obtain Constants in general solutions ;

Initial value

(

)

T(1) = 1

$T (1) = 1$ Substitute the above general solution

(

)

−

T(n) = c2^n - 1

$T (n) = c 2^{n} - 1$ , obtain

−

2c - 1 = 1

$2 c - 1 = 1$

constant

c = 1

$c = 1$ ;

( 2 ) Substitute constants to obtain the general solution : Substitute constants into the general solution , You can get the final solution of the recursive equation ;

Will constant

c=1

$c = 1$ Substitute into the general solution , The final result is the solution of the recursive equation :

(

)

−

T(n) = 2^n - 1

$T (n) = 2^{n} - 1$

Two 、 Special solution example 2 ( The characteristic root is 1 The situation of )

The recurrence equation is :

(

)

−

(

−

)

H(n) - H(n-1) = 7n

$H (n) - H (n - 1) = 7 n$ , Find the general solution of the recursive equation ?

First find its homogeneous part

(

)

−

(

−

)

H(n) - H(n-1) = 0

$H (n) - H (n - 1) = 0$ A general understanding of ;

Write the characteristic equation :

−

x - 1 = 0

$x - 1 = 0$ , The characteristic root is

q= 1

$q = 1$ ;

Homogeneous partial general solution form :

(

)

‾

\overline{H(n)} =c_11^n = c_1

$\overline{H (n)} = c_{1} 1^{n} = c_{1}$

Find its special solution ( Failed attempts ) :

These are constant coefficients linear Nonhomogeneous equation , Then ask for it first Nonhomogeneous Part of it corresponds to Special solution ,

The right side is

$n$ Of

$1$ Sub equation , Then the corresponding special solution is

∗

(

)

H^*(n) = P_1n + P_2

$H^{*} (n) = P_{1} n + P_{2}$ , The above special solution , Into the recursive equation ,

−

(

−

)

\ \ \ \ P_1n + P_2 - (P_1(n - 1) + P_2) =7n

$P_{1} n + P_{2} - (P_{1} (n - 1) + P_{2}) = 7 n$ , After simplification, it becomes :

−

\ \ \ \ P_1n + P_2 - P_1n + P_1 - P_2 = 7n

$P_{1} n + P_{2} - P_{1} n + P_{1} - P_{2} = 7 n$

\ \ \ \ P_1 = 7n

$P_{1} = 7 n$

At this time, the constant in the special solution cannot be solved

P_1, P_2

$P_{1}, P_{2}$ , Therefore, the special solution cannot be set as

$n$ Of

$1$ Sub equation ,

The reason for this problem is , Homogeneous part , The characteristic equation is

−

x-1 = 0

$x - 1 = 0$ , The corresponding characteristic root is

$1$ ,

The characteristic root is

$1$ when , The highest term of the polynomial will cancel , The constant term will also be offset ;

Seeking special solution , take

$n$ To the power of

$1$ :

The power of increase is Characteristic root

$1$ The repeatability of , If the repetition is

$2$ , You need to improve

$2$ The next power ;

In order to solve the above problems , Here we need to

$n$ To the power of

$1$ , Let the first power term in the form of special solution , Set to square , The constant term is not set , Even if it is set, it will offset , Cannot find the value of the constant term ;

Set the special solution to

$n$ Of

$2$ Sub equation ,

The special solution is in the form of

∗

(

)

H^*(n) = P_1n^2 + P_2n

$H^{*} (n) = P_{1} n^{2} + P_{2} n$ ;

Put the special solution into the recursive equation :

−

(

−

)

(

−

)

P_1n^2 + P_2n - ( P_1(n-1)^2 + P_2(n-1) )=7n

$P_{1} n^{2} + P_{2} n - (P_{1} (n - 1)^{2} + P_{2} (n - 1)) = 7 n$

−

(

−

)

(

−

)

P_1n^2 + P_2n - ( P_1(n^2 -2n + 1) + P_2(n-1) )=7n

$P_{1} n^{2} + P_{2} n - (P_{1} (n^{2} - 2 n + 1) + P_{2} (n - 1)) = 7 n$

−

P_1n^2 + P_2n - P_1n^2 + 2P_1n - P_1 - P_2n + P_2=7n

$P_{1} n^{2} + P_{2} n - P_{1} n^{2} + 2 P_{1} n - P_{1} - P_{2} n + P_{2} = 7 n$

−

2P_1n - P_1 + P_2=7n

$2 P_{1} n - P_{1} + P_{2} = 7 n$

analysis

$n$ Write the system of equations by the power of :

The left and right sides are equal , here according to

$n$ The coefficient before the power of , Write the equations ;

analysis

$n$ Coefficient to the power of :

n
2
n^2
$n^{2}$ Coefficient analysis : There's no on the right
n
2
n^2
$n^{2}$ , So on the left
n
2
n^2
$n^{2}$ The coefficient before the term is
0
0
$0$ ; Nor on the left
n
2
n^2
$n^{2}$ term , Unable to extract equation ;
n
1
n^1
$n^{1}$ Coefficient analysis : The right side is
7
n
7n
$7 n$ , therefore
n
n
$n$ The coefficient before is
7
7
$7$ ; Expand the left side ,
n
n
$n$ The coefficient before is
2
P
1
2P_1
$2 P_{1}$ ;
2
P
1
n
=
7
n
2P_1n = 7n
$2 P_{1} n = 7 n$
n
0
n^0
$n^{0}$ Coefficient analysis : The right side is
0
0
$0$ ; Expand the left side ,
n
0
n^0
$n^{0}$ The coefficient before is
P
2
−
P
1
P_2-P_1
$P_{2} - P_{1}$ ;
P
2
−
P
1
=
0
P_2-P_1 = 0
$P_{2} - P_{1} = 0$