当前位置：网站首页>[combinatorics] recursive equation (special solution form | special solution solving method | special solution example)

[combinatorics] recursive equation (special solution form | special solution solving method | special solution example)

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

List of articles

One 、 Special solution form and solution
Two 、 Special solution form and solution Example

One 、 Special solution form and solution

(

)

−

(

−

)

−

⋯

−

(

−

)

(

)

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

$H (n) - a_{1} H (n - 1) - \dots - a_{k} H (n - k) = f (n)$ ,

≥

≠

(

)

≠

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

$n \geq k, a_{k} \neq = 0, f (n) \neq = 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$ , It's based on

$n$ Of function

(

)

f(n)

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

(

)

‾

\overline{H(n)}

$\overline{H (n)}$ Is corresponding to the above recursive equation “ Linear homogeneous recurrence equation with constant coefficients ”

(

)

−

(

−

)

−

⋯

−

(

−

)

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

$H (n) - a_{1} H (n - 1) - \dots - a_{k} H (n - k) = 0$ A general understanding of ,

∗

(

)

H^*(n)

$H^{*} (n)$ Is a special solution ,

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

(

)

(

)

‾

∗

(

)

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

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

stay 【 Combinatorial mathematics 】 Recurrence equation ( Example of solving recurrence equation without multiple roots | Complete process of solving recursive equations without multiple roots ) The blog introduces “ Linear homogeneous recurrence equation with constant coefficients ” The general solution of ;

This blog begins with Special solution

∗

(

)

H^*(n)

$H^{*} (n)$ The way of seeking ;

Special solutions and “ Linear Nonhomogeneous recurrence equation with constant coefficients ” The right part of

(

)

f(n)

$f (n)$ of ,

(

)

f(n)

$f (n)$ by

$n$ Of

$t$ Sub polynomial ,

Special solution

∗

(

)

H^*(n)

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

$n$ Of

$t$ Sub polynomial ;

1 . Special solution form :

( 1 ) Special solution form : Special solution

∗

(

)

H^*(n)

$H^{*} (n)$ yes

$n$ Of

$t$ Sub polynomial ,

$n$ The power of is taken from

$0$ To

$t$ , Therefore, its Number of items

t+1

$t + 1$ term ;

( 2 ) Understand each component :

① Number of items :
② form : The special solution term consists of constant multiply
$n$ Power of power form , Constants are unknown ;
③ constant :
$t + 1$ It's a constant , Use subscripts to identify ;
④ $00 0 To t t t;$
$n$ The power of : The power value is from

( 3 ) give an example : Special solution

∗

(

)

H^*(n)

$H^{*} (n)$ yes

$n$ Of

$2$ Sub polynomial ;

Number of special solutions : be Number of special solutions yes

2 + 1 = 3

$2 + 1 = 3$ term ;

Understand each component : Each term is explained by constant multiply

$n$ Power of power form ,

3
3
$3$ It's a constant Set to
P
1
,
P
2
,
P
3
P_1, P_2, P_3
$P_{1}, P_{2}, P_{3}$ ,
3
3
$3$ individual
n
n
$n$ Power of power , Power value from
0
0
$0$ To
2
2
$2$ ,

Therefore, the form of the special solution is

∗

(

)

H^*(n) = P_1n^2 + P_2n^1 + P_3n^0

$H^{*} (n) = P_{1} n^{2} + P_{2} n^{1} + P_{3} n^{0}$ ,

It is reduced to :

∗

(

)

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

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

2 . Special solution method :

( 1 ) First write the form of the special solution : Special solution

∗

(

)

H^*(n)

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

$n$ Of

$t$ Sub polynomial ; Such as :

(

)

f(n)

$f (n)$ by

$n$ Of

$2$ Sub polynomial , The special solution is

∗

(

)

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

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

( 2 ) The special solution is substituted into the recursive equation : Then the special solution is substituted into the recursive equation , Determine the coefficients in the special solution ;

Two 、 Special solution form and solution Example

Recurrence equation :

−

a_n + 5a_{n-1} + 6a_{n-2}=3n^2

$a_{n} + 5 a_{n - 1} + 6 a_{n - 2} = 3 n^{2}$ ;

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

3n^2

$3 n^{2}$ Related to special solutions ,

3n^2

$3 n^{2}$ by

$n$ Of

$2$ Sub polynomial ,

Therefore, the special solution

∗

(

)

H^*(n)

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

$n$ Of

$2$ Sub polynomial ;

2 . Write the special solution form :

Number of special solutions : be Number of special solutions yes

2 + 1 = 3

$2 + 1 = 3$ term ;

Understand each component : Each term is explained by constant multiply

$n$ Power of power form ,

3
3
$3$ It's a constant Set to
P
1
,
P
2
,
P
3
P_1, P_2, P_3
$P_{1}, P_{2}, P_{3}$ ,
3
3
$3$ individual
n
n
$n$ Power of power , Power value from
0
0
$0$ To
2
2
$2$ ,

Therefore, the form of the special solution is

∗

(

)

H^*(n) = P_1n^2 + P_2n^1 + P_3n^0

$H^{*} (n) = P_{1} n^{2} + P_{2} n^{1} + P_{3} n^{0}$ ,

It is reduced to :

∗

(

)

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

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

3 . Put the special solution into the recursive equation :

Will explain

∗

(

)

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

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

Into the recursive equation

−

a_n + 5a_{n-1} + 6a_{n-2}=3n^2

$a_{n} + 5 a_{n - 1} + 6 a_{n - 2} = 3 n^{2}$ in ,

obtain :

(

)

(

−

)

(

−

)

(

−

)

(

−

)

(P_1n^2 + P_2n + P_3) + 5(P_1(n-1)^2 + P_2(n-1) + P_3) + 6(P_1(n-2)^2 + P_2(n-2) + P_3)=3n^2

$(P_{1} n^{2} + P_{2} n + P_{3}) + 5 (P_{1} (n - 1)^{2} + P_{2} (n - 1) + P_{3}) + 6 (P_{1} (n - 2)^{2} + P_{2} (n - 2) + P_{3}) = 3 n^{2}$

4 . 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}$ Coefficient analysis : The right side is
$n^1$
$n^{1}$ Coefficient analysis : There's no on the right
$n^0$
$n^{0}$ Coefficient analysis : There's no on the right

Finally, we get the equations :

{

−

\begin{cases} 12P_1 = 3 \\\\ -34P_1 + 12P_2 = 0 \\\\ 29P_1 - 17P_2 + 12 P_3 = 0 \end{cases}

$⎩ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎨ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎧ 12 P_{1} = 3 - 34 P_{1} + 12 P_{2} = 0 29 P_{1} - 17 P_{2} + 12 P_{3} = 0$

Solve the above equations , Get the results :

{

115

288

\begin{cases} P_1 = \cfrac{1}{4} \\\\ P_2 = \cfrac{7}{24} \\\\ P_3 = \cfrac{115}{288} \end{cases}

$⎩ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎨ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎧ P_{1} = \frac{1}{4} P_{2} = \frac{7}{2 4} P_{3} = \frac{1 1 5}{2 8 8}$

The special solution is :

∗

(

)

115

288

H^*(n) = \cfrac{1}{4} n^2 + \cfrac{7}{24}n + \cfrac{115}{288}

$H^{*} (n) = \frac{1}{4} n^{2} + \frac{7}{2 4} n + \frac{1 1 5}{2 8 8}$

The final general solution is :

(

)

(

−

)

(

−

)

115

288

H(n) = c_1(-2)^n + c_2(-3)^n + \cfrac{1}{4} n^2 + \cfrac{7}{24}n + \cfrac{115}{288}

$H (n) = c_{1} (- 2)^{n} + c_{2} (- 3)^{n} + \frac{1}{4} n^{2} + \frac{7}{2 4} n + \frac{1 1 5}{2 8 8}$

原网站

版权声明
本文为[Programmer community]所创，转载请带上原文链接，感谢
https://yzsam.com/2022/02/202202150355136910.html

当前位置：网站首页>[combinatorics] recursive equation (special solution form | special solution solving method | special solution example)

[combinatorics] recursive equation (special solution form | special solution solving method | special solution example)

List of articles

One 、 Special solution form and solution

Two 、 Special solution form and solution Example

边栏推荐

猜你喜欢

随机推荐