[combinatorics] recursive equation (solution of linear non-homogeneous recursive equation with constant coefficients | standard form and general solution of recursive equation | proof of general solut

One 、 Standard form and general solution of recurrence equation

---

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 ” ;

Then the general solution of the above recursive equation is as follows :

H

(

n

)

‾

\overline{H(n)}

H(n)​ Is corresponding to the above recursive equation “ Linear homogeneous recurrence equation with constant coefficients ”

H

(

n

)

−

a

1

H

(

n

−

1

)

−

⋯

−

a

k

H

(

n

−

k

)

=

0

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

H(n)−a1​H(n−1)−⋯−ak​H(n−k)=0 A general understanding of ,

H

∗

(

n

)

H^*(n)

H∗(n) Is a special solution ,

“ 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)

“ Linear Nonhomogeneous recurrence equation with constant coefficients ” yes “ Linear homogeneous recurrence equation with constant coefficients ” Of Homogeneous general solution , Add a Special solution ;

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)
Linear homogeneous recurrence equation with constant coefficients :

   
 

H

(

n

)

−

a

1

H

(

n

−

1

)

−

⋯

−

a

k

H

(

n

−

k

)

=

0

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

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

H

∗

(

n

)

H^*(n)

H∗(n) Special solution , Is a specific function that can make the equation equal on both sides ,

take

H

(

n

)

=

H

(

n

)

‾

+

H

∗

(

n

)

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

H(n)=H(n)​+H∗(n) general solution Substitute into

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) On the left ,

Will bring Top line Of

H

(

n

)

‾

\overline{H(n)}

H(n)​ Item merge , It must be

0

0

0 ,

Will bring

∗

*

∗ asterisk Of

H

∗

(

n

)

H^*(n)

H∗(n) Item merge , It must be

f

(

n

)

f(n)

f(n) ,

0

+

f

(

n

)

0 + f(n)

0+f(n) The end result is

f

(

n

)

f(n)

f(n) , With right

f

(

n

)

f(n)

f(n) equal ;

Any solution of a recursive equation , It's all one Homogeneous general solution , add A special solution The format of ;

Two 、 Proof of general solution of recurrence equation

---

prove : General solution of recurrence equation , A certain It's a Homogeneous general solution , add A special solution The format of ;

Recurrence equation :

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

hypothesis

h

(

n

)

h(n)

h(n) Is the general solution of the recursive equation , Prove that

h

(

n

)

h(n)

h(n) It's a Homogeneous general solution , add A special solution The sum of the ;

take

h

(

n

)

h(n)

h(n) Into the above recursive equation ,

①

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)

Special solution

H

∗

(

n

)

H^*(n)

H∗(n) It is also the solution of the recursive equation , take

H

∗

(

n

)

H^*(n)

H∗(n) Into the recursive equation , Both sides are equal ,

②

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)

Put the above ① ② Of two equations The left is subtracted from the left , The right part is subtracted from the right part ,

(

h

(

n

)

−

a

1

h

(

n

−

1

)

−

⋯

−

a

k

h

(

n

−

k

)

)

( h(n) - a_1h(n-1) - \cdots - a_kh(n-k) )

(h(n)−a1​h(n−1)−⋯−ak​h(n−k))

−

-

−

(

H

∗

(

n

)

−

a

1

H

∗

(

n

−

1

)

−

⋯

−

a

k

H

∗

(

n

−

k

)

)

( H^*(n) - a_1H^*(n-1) - \cdots - a_kH^*(n-k) )

(H∗(n)−a1​H∗(n−1)−⋯−ak​H∗(n−k))

=

0

=0

=0

Merge the items in the above formula :

[

h

(

n

)

−

H

∗

(

n

)

]

−

a

1

[

h

(

n

−

1

)

−

H

∗

(

n

−

1

)

]

−

⋯

−

a

k

[

h

(

n

−

k

)

−

H

∗

(

n

−

k

)

]

=

0

[ h(n) - H^*(n) ] - a_1[ h(n-1) - H^*(n-1) ] - \cdots - a_k[ h(n-k) - H^*(n-k) ] = 0

[h(n)−H∗(n)]−a1​[h(n−1)−H∗(n−1)]−⋯−ak​[h(n−k)−H∗(n−k)]=0

The above equation is homogeneous ,

h

(

n

)

−

H

∗

(

n

)

h(n) - H^*(n)

h(n)−H∗(n) Is the general solution of homogeneous equation ,

that

h

(

n

)

h(n)

h(n) Namely General solution of homogeneous equation And Special solution

H

∗

(

n

)

H^*(n)

H∗(n) Add up ;

therefore

H

(

n

)

=

H

(

n

)

‾

+

H

∗

(

n

)

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

H(n)=H(n)​+H∗(n) The format must be general ;