[combinatorics] recursive equation (the non-homogeneous part is an exponential function and the bottom is the characteristic root | example of finding a special solution)

One 、 The nonhomogeneous part is Exponential function And The bottom is the case of characteristic root

---

Linear Nonhomogeneous recurrence equation with constant coefficients :

H

(

n

)

−

a

1

H

(

n

−

1

)

−

⋯

−

a

k

H

(

n

−

k

)

=

f

(

n

)

H(n) - a_1H(n-1) - \cdots - a_kH(n-k) = f(n)

H(n)−a1​H(n−1)−⋯−ak​H(n−k)=f(n) ,

n

≥

k

,

a

k

≠

0

,

f

(

n

)

≠

0

n\geq k , a_k\not= 0, f(n) \not= 0

n≥k,ak​​=0,f(n)​=0

The left side of the above equation And “ Linear homogeneous recurrence equation with constant coefficients ” It's the same , But not on the right

0

0

0 , It's based on

n

n

n Of function

f

(

n

)

f(n)

f(n) , This type of recursive equation is called “ Linear Nonhomogeneous recurrence equation with constant coefficients ” ;

The nonhomogeneous part is Exponential function And The bottom is the case of characteristic root :

If the above “ Linear Nonhomogeneous recurrence equation with constant coefficients ” Of Nonhomogeneous part

f

(

n

)

f(n)

f(n) It's an exponential function ,

β

n

\beta^n

βn ,

If

β

\beta

β yes

e

e

e Heavy characteristic root ,

The special solution form of the nonhomogeneous part is :

H

∗

(

n

)

=

P

n

e

β

n

H^*(n) = P n^e \beta^n

H∗(n)=Pneβn ,

P

P

P Is constant ;

The above special solution

H

∗

(

n

)

=

P

n

e

β

n

H^*(n) = P n^e \beta^n

H∗(n)=Pneβn , Into the recursive equation , Solve the constant

P

P

P Value , Then the complete special solution is obtained ;

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

H

(

n

)

=

H

(

n

)

‾

+

H

∗

(

n

)

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

H(n)=H(n)​+H∗(n)

Use the above solution Special solution , And recurrence equation General solution of homogeneous part , Form the complete general solution of the recursive equation ;

Two 、 The nonhomogeneous part is Exponential function And The bottom is the case of characteristic root Example

---

Recurrence equation :

H

(

n

)

−

5

H

(

n

−

1

)

+

6

H

(

n

−

2

)

=

2

n

H(n) - 5H(n-1) + 6H(n-2)=2^n

H(n)−5H(n−1)+6H(n−2)=2n, Seeking special solution ?

View its characteristic root :

The standard form of recurrence equation is :

H

(

n

)

−

5

H

(

n

−

1

)

+

6

H

(

n

−

2

)

=

2

n

H(n) - 5H(n-1) + 6H(n-2)=2^n

H(n)−5H(n−1)+6H(n−2)=2n ,

Homogeneous part is

H

(

n

)

−

5

H

(

n

−

1

)

+

6

H

(

n

−

2

)

=

0

H(n) - 5H(n-1) + 6H(n-2)=0

H(n)−5H(n−1)+6H(n−2)=0

Write the characteristic equation :

x

2

−

5

x

+

6

=

0

x^2 - 5x + 6 = 0

x2−5x+6=0 ,

Characteristic root

q

1

=

2

,

q

2

=

3

q_1= 2, q_2 = 3

q1​=2,q2​=3

Find the recurrence equation Special solutions corresponding to Nonhomogeneous parts ,

The standard form of recurrence equation is :

H

(

n

)

−

5

H

(

n

−

1

)

+

6

H

(

n

−

2

)

=

2

n

H(n) - 5H(n-1) + 6H(n-2)=2^n

H(n)−5H(n−1)+6H(n−2)=2n

The nonhomogeneous part is

2

n

2^n

2n , It's an exponential function , But the bottom line is

1

1

1 Heavy characteristic root ,

At this time, the bottom is

e

e

e The special solution is constructed by repeating the special solution form of the characteristic root

H

∗

(

n

)

=

P

n

e

β

n

H^*(n) = P n^e \beta^n

H∗(n)=Pneβn

The form of the special solution is

H

∗

(

n

)

=

P

n

1

2

n

=

P

n

2

n

H^*(n) = P n^1 2^n = Pn2^n

H∗(n)=Pn12n=Pn2n , among

P

P

P Is constant ;

The special solution is substituted into the above recursive equation :

P

n

2

n

−

5

P

(

n

−

1

)

2

n

−

1

+

6

P

(

n

−

2

)

2

n

−

2

=

2

n

Pn2^n - 5P(n-1)2^{n-1} + 6P(n-2)2^{n-2} = 2^n

Pn2n−5P(n−1)2n−1+6P(n−2)2n−2=2n

All items are constructed

2

n

2^n

2n

P

n

2

n

−

5

P

(

n

−

1

)

2

n

2

+

6

P

(

n

−

2

)

2

n

4

=

2

n

Pn2^n - \cfrac{5P(n-1)2^{n}}{2} + \cfrac{6P(n-2)2^n}{4} = 2^n

Pn2n−25P(n−1)2n​+46P(n−2)2n​=2n

Divide left and right by

2

n

2^n

2n

P

n

−

5

P

(

n

−

1

)

2

+

3

P

(

n

−

2

)

2

=

1

Pn - \cfrac{5P(n-1)}{2} + \cfrac{3P(n-2)}{2} = 1

Pn−25P(n−1)​+23P(n−2)​=1

P

n

−

5

P

n

2

+

5

P

2

+

3

P

n

2

−

3

P

=

1

Pn - \cfrac{5Pn}{2} + \cfrac{5P}{2} + \cfrac{3Pn}{2} -3P = 1

Pn−25Pn​+25P​+23Pn​−3P=1

5

P

2

−

3

P

=

1

\cfrac{5P}{2} -3P = 1

25P​−3P=1

−

P

2

=

1

-\cfrac{P}{2} = 1

−2P​=1

P

=

−

2

P=-2

P=−2

The form of special solution

H

∗

(

n

)

=

P

n

2

n

H^*(n) = Pn2^n

H∗(n)=Pn2n , among

P

P

P Constant value is

−

2

-2

−2 ;

The special solution is

H

∗

(

n

)

=

−

2

n

2

n

H^*(n) = -2n2^n

H∗(n)=−2n2n