当前位置：网站首页>[combinatorics] recursive equation (four cases where the non-homogeneous part of a linear non-homogeneous recursive equation with constant coefficients is the general solution of the combination of po

[combinatorics] recursive equation (four cases where the non-homogeneous part of a linear non-homogeneous recursive equation with constant coefficients is the general solution of the combination of po

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

List of articles

One 、 Linear Nonhomogeneous recurrence equation with constant coefficients Of The nonhomogeneous part is polynomial And Index combination
Two 、 Four cases of general solution of recurrence equation

One 、 Linear Nonhomogeneous recurrence equation with constant coefficients Of The nonhomogeneous part is polynomial And Index combination

If “ Linear Nonhomogeneous recurrence equation with constant coefficients ” Nonhomogeneous part of , yes

$n$ Of

$t$ Sub polynomial , And

\beta^n

$β^{n}$ The index of , The combination of ;

Then the form of its special solution , yes

$n$ Of

$t$ Sub polynomial , And

P\beta^n

$P β^{n}$ Of and ;

Recurrence equation :

−

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

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

initial value :

a_0 = 0

$a_{0} = 0$

General form ( important ) :

① The nonhomogeneous part is

$n$ Of

$t$ Sub polynomial :

The characteristic root is not
If the characteristic root is

② The nonhomogeneous part is

P\beta^n

$P β^{n}$ :

The characteristic root cannot be the bottom $\betaβ , The special solution is P β n P\beta^nPβn ;$
The characteristic root is the bottom $\betaβ , The multiplicity of the characteristic root is e ee , The special solution is P n e β n Pn^e\beta^nPneβn ;$

③ Homogeneous parts have no double roots :

(

)

⋯

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

④ Homogeneous parts have double roots : General explanation

$i$ term , Characteristic root

q_i

$q_{i}$ , Multiplicity

e_i

$e_{i}$ ,

(

)

(

⋯

−

)

H_i(n) = (c_{i1} + c_{i2}n + \cdots + c_{ie_i}n^{e_i - 1})q_i^n

$H_{i} (n) = (c_{i 1} + c_{i 2} n + \dots + c_{i e_{i}} n^{e_{i} - 1}) q_{i}^{n}$ , Final general solution

(

)

∑

(

)

H(n) = \sum\limits_{i=1}^tH_i(n)

$H (n) = i = 1 \sum t H_{i} (n)$ ;

Reference blog : 【 Combinatorial mathematics 】 Recurrence equation ( Linear Nonhomogeneous recurrence equation with constant coefficients Of The nonhomogeneous part is polynomial And Index combination | Four cases of general solution )

Calculate the homogeneous partial general solution :

Homogeneous partial standard form of recurrence equation :

−

a_n - 2a_{n-1} = 0

$a_{n} - 2 a_{n - 1} = 0$

Characteristic equation :

−

x - 2 = 0

$x - 2 = 0$

Characteristic root :

x=2

$x = 2$

Homogeneous partial general solution :

‾

\overline{a_n} =c2^n

$\overline{a_{n}} = c 2^{n}$

Calculate the non-homogeneous partial general solution :

The non-homogeneous part of the above recursive equation is

n + 3^n

$n + 3^{n}$ , It consists of two parts :

$n$ Of

$t$ Sub polynomial :

$n$ , The characteristic root is not

$1$ , The corresponding special solution is

$n$ Of

$t$ Sub polynomial , In the form of

P_1n + P_2

$P_{1} n + P_{2}$ ;

\beta^n

$β^{n}$ Index :

3^n

$3^{n}$ , The characteristic root is not the bottom

$3$ , The corresponding special solution is

P\beta^n

$P β^{n}$ form , In the form of

P_33^n

$P_{3} 3^{n}$ ;

Complete special solution :

∗

a^*_n = P_1n + P_2 + P_33^n

$a_{n}^{*} = P_{1} n + P_{2} + P_{3} 3^{n}$

Put the special solution into the recursive equation :

(

)

−

[

(

−

)

−

]

(P_1n + P_2 + P_33^n) - 2[P_1(n-1) + P_2 + P_33^{n-1}] = n + 3^n

$(P_{1} n + P_{2} + P_{3} 3^{n}) - 2 [P_{1} (n - 1) + P_{2} + P_{3} 3^{n - 1}] = n + 3^{n}$

Expand the formula on the left :

−

(

−

)

−

-P_1n + (2P_1 - P_2) + P_33^{n-1}=n+3^n

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

According to the analysis of

$n$ The power of , Constant term ,

3^n

$3^{n}$ Correspondence of items , The following equations can be obtained :

{

−

\begin{cases} -P_1 = 1 \\\\ 2P_1 - P_2 = 0 \\\\ \cfrac{P_3}{3} =1 \end{cases}

$⎩ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎨ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎧ - P_{1} = 1 2 P_{1} - P_{2} = 0 \frac{P _{3}}{3} = 1$

Solve the above equations , The result is :

{

−

\begin{cases} P_1 = -1 \\\\ P_2 = -2 \\\\ P_3 =3 \end{cases}

$⎩ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎨ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎧ P_{1} = - 1 P_{2} = - 2 P_{3} = 3$

Special solution : Substitute the above constant into

∗

a^*_n = P_1n + P_2 + P_33^n

$a_{n}^{*} = P_{1} n + P_{2} + P_{3} 3^{n}$ in , Get the final special solution :

∗

−

a^*_n = -n - 2 + 3^{n+1}

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

Homogeneous partial general solution form :

‾

\overline{a_n} =c2^n

$\overline{a_{n}} = c 2^{n}$

Complete general solution :

‾

∗

−

a_n = \overline{a_n} + a^*_n = c2^n -n - 2 + 3^{n+1}

$a_{n} = \overline{a_{n}} + a_{n}^{*} = c 2^{n} - n - 2 + 3^{n + 1}$

Initial value

a_0 = 0

$a_{0} = 0$ Substitute the above general solution :

−

c2^0 - 0 - 2 + 3^{0+1} = 0

$c 2^{0} - 0 - 2 + 3^{0 + 1} = 0$

−

c - 2 + 3 = 0

$c - 2 + 3 = 0$

−

c=-1

$c = - 1$

The general solution of the final recursive equation is

−

a_n = 2^n -n - 2 + 3^{n+1}

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

Two 、 Four cases of general solution of recurrence equation

General form ( important ) :

① The nonhomogeneous part is

$n$ Of

$t$ Sub polynomial :

The characteristic root is not
If the characteristic root is

② The nonhomogeneous part is

P\beta^n

$P β^{n}$ :

The characteristic root cannot be the bottom $\betaβ , The special solution is P β n P\beta^nPβn ;$
The characteristic root is the bottom $\betaβ , The multiplicity of the characteristic root is e ee , The special solution is P n e β n Pn^e\beta^nPneβn ;$