当前位置：网站首页>[combinatorics] recursive equation (example of solving recursive equation without multiple roots | complete process of solving recursive equation without multiple roots)

[combinatorics] recursive equation (example of solving recursive equation without multiple roots | complete process of solving recursive equation without multiple roots)

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

List of articles

One 、 Fibonacci sequence solution
Two 、 Complete process of solving recursive equations without multiple roots

One 、 Fibonacci sequence solution

1 . Fibonacci sequence example :

( 1 ) Fibonacci sequence :

⋯

1 , 1 , 2 , 3 , 5 , 8 , 13 , \cdots

$1, 1, 2, 3, 5, 8, 13, \dots$

( 2 ) Recurrence equation :

(

)

(

−

)

(

−

)

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

$F (n) = F (n - 1) + F (n - 2)$

describe : The first

$n$ Item equal to

−

n-1

$n - 1$ term and The first

−

n-2

$n - 2$ Sum of items ;

Such as : The first

$4$ Item value

(

)

F(4) = 5

$F (4) = 5$ , Is equal to

The first

−

4-1=3

$4 - 1 = 3$ Item value

(

−

)

(

)

F(4-1)=F(3) = 3

$F (4 - 1) = F (3) = 3$

add The first

−

4-2=2

$4 - 2 = 2$ Item value

(

−

)

(

)

F(4-2) = F(2) =2

$F (4 - 2) = F (2) = 2$ ;

( 3 ) initial value :

(

)

(

)

F(0) = 1 , F(1) = 1

$F (0) = 1, F (1) = 1$

according to

(

)

(

)

F(0) = 1, F(1) = 1

$F (0) = 1, F (1) = 1$ You can calculate

(

)

F(2)

$F (2)$ , according to

(

)

(

)

F(1),F(2)

$F (1), F (2)$ You can calculate

(

)

F(3)

$F (3)$ , according to

(

)

(

)

F(2)F(3)

$F (2) F (3)$ Sure Calculation

(

)

F(4)

$F (4)$ ,

⋯

\cdots

$\dots$ , according to

(

−

)

(

−

)

F(n-2) , F(n-1)

$F (n - 2), F (n - 1)$ You can calculate

(

)

F(n)

$F (n)$ ;

2 . Write the characteristic equation of Fibonacci sequence and solve the characteristic root :

Recurrence equation :

(

)

(

−

)

(

−

)

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

$F (n) = F (n - 1) + F (n - 2)$

( 1 ) The standard form of recurrence equation :

(

)

−

(

−

)

−

(

−

)

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

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

( 2 ) Recursive equation writing :

① First determine the number of terms of the characteristic equation : The same number of terms as the recursive equation ,

$3$ term ;

② In determining the characteristic equation

$x$ Power of power : from

−

3-1=2

$3 - 1 = 2$ To

$0$ ;

③ Write a recurrence equation without coefficients :

x^2 + x^1 + x^0 = 0

$x^{2} + x^{1} + x^{0} = 0$

④ Filling factor : Then the characteristic equation without coefficients

x^2 + x^1 + x^0 = 0

$x^{2} + x^{1} + x^{0} = 0$ And

(

)

−

(

−

)

−

(

−

)

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

$F (n) - F (n - 1) - F (n - 2) = 0$ The coefficients of corresponding bits are filled into the characteristic equation :

$x^2x2 The coefficient before Corresponding F ( n ) F(n)F(n) Coefficient before item 1 11 ;$
$x^1x1 The coefficient before Corresponding F ( n − 1 ) F(n-1)F(n−1) Coefficient before item − 1 -1−1 ;$
$x^0x0 The coefficient before Corresponding F ( n − 2 ) F(n-2)F(n−2) Coefficient before item − 1 -1−1 ;$

Then the final The characteristic equation is

(

−

)

(

−

)

1 x^2 + (-1)x^1 + (-1)x^0 = 0

$1 x^{2} + (- 1) x^{1} + (- 1) x^{0} = 0$ , It is reduced to :

−

x^2 - x - 1 = 0

$x^{2} - x - 1 = 0$

The characteristic root of the characteristic equation is : The solution of the above equation is the characteristic root , Generally, it is a quadratic equation with one variable ;

x = \cfrac{1 \pm \sqrt{5}}{2}

$x = \frac{1 \pm 5}{2}$

Reference resources : Univariate quadratic equation form
a
x
2
+
b
x
+
c
=
0
ax^2 + bx + c = 0
$a x^{2} + b x + c = 0$
The solution is :
x
=
−
b
±
b
2
−
4
a
c
2
a
x = \cfrac{-b \pm \sqrt{b^2 - 4ac}}{2a}
$x = \frac{- b \pm b ^{2} - 4 a c}{2 a}$

3 . Write the general solution of Fibonacci sequence :

The characteristic root of Fibonacci series recurrence equation is :

\cfrac{1 \pm \sqrt{5}}{2}

$\frac{1 \pm 5}{2}$ ;

q_1 = \cfrac{1 + \sqrt{5}}{2}

$q_{1} = \frac{1 + 5}{2}$ ,

−

q_2 =\cfrac{1 - \sqrt{5}}{2}

$q_{2} = \frac{1 - 5}{2}$

The general solution is in the form of

(

)

⋯

F(n) = c_1q_1^n + c_2q_2^n + \cdots + c_kq_k^n

$F (n) = c_{1} q_{1}^{n} + c_{2} q_{2}^{n} + \dots + c_{k} q_{k}^{n}$

Set feature root

q_1 , q_2

$q_{1}, q_{2}$ After substituting the above general solution form, it becomes :

(

)

(

)

(

−

)

F(n) = c_1 ( \cfrac{1 + \sqrt{5}}{2} ) ^n + c_2 ( \cfrac{1 - \sqrt{5}}{2} ) ^n

$F (n) = c_{1} (\frac{1 + 5}{2})^{n} + c_{2} (\frac{1 - 5}{2})^{n}$

4 . Substitute the initial value of the recurrence equation into general solution , Solve the constants in the general solution :

Fibonacci sequence Initial value of recurrence equation :

(

)

(

)

F(0) = 1 , F(1) = 1

$F (0) = 1, F (1) = 1$

Substitute the above initial value

(

)

(

)

F(0) = 1 , F(1) = 1

$F (0) = 1, F (1) = 1$ To General solution of recurrence equation

(

)

(

)

(

−

)

F(n) = c_1 ( \cfrac{1 + \sqrt{5}}{2} ) ^n + c_2 ( \cfrac{1 - \sqrt{5}}{2} ) ^n

$F (n) = c_{1} (\frac{1 + 5}{2})^{n} + c_{2} (\frac{1 - 5}{2})^{n}$ in , The following equations are obtained :

{

(

)

(

−

)

(

)

(

)

(

−

)

(

)

\begin{cases} c_1 ( \cfrac{1 + \sqrt{5}}{2} ) ^0 + c_2 ( \cfrac{1 - \sqrt{5}}{2} ) ^0 = F(0) = 1 \\\\ c_1 ( \cfrac{1 + \sqrt{5}}{2} ) ^1 + c_2 ( \cfrac{1 - \sqrt{5}}{2} ) ^1 = F(1) = 1 \end{cases}

$⎩ ⎪ ⎪ ⎪ ⎪ ⎨ ⎪ ⎪ ⎪ ⎪ ⎧ c_{1} (\frac{1 + 5}{2})^{0} + c_{2} (\frac{1 - 5}{2})^{0} = F (0) = 1 c_{1} (\frac{1 + 5}{2})^{1} + c_{2} (\frac{1 - 5}{2})^{1} = F (1) = 1$

After simplification, we get :

{

(

)

(

−

)

\begin{cases} c_1 + c_2 = 1 \\\\ c_1 ( \cfrac{1 + \sqrt{5}}{2} ) + c_2 ( \cfrac{1 - \sqrt{5}}{2} ) = 1 \end{cases}

$⎩ ⎪ ⎪ ⎨ ⎪ ⎪ ⎧ c_{1} + c_{2} = 1 c_{1} (\frac{1 + 5}{2}) + c_{2} (\frac{1 - 5}{2}) = 1$

Solve the above equations :

−

c_1 =\cfrac{1}{\sqrt{5}} \cfrac{1 + \sqrt{5}}{2}, \ \ c_2 =-\cfrac{1}{\sqrt{5}} \cfrac{1 - \sqrt{5}}{2}

$c_{1} = \frac{1}{5} \frac{1 + 5}{2}, c_{2} = - \frac{1}{5} \frac{1 - 5}{2}$

Will constant

−

c_1 =\cfrac{1}{\sqrt{5}} \cfrac{1 + \sqrt{5}}{2}, \ \ c_2 =-\cfrac{1}{\sqrt{5}} \cfrac{1 - \sqrt{5}}{2}

$c_{1} = \frac{1}{5} \frac{1 + 5}{2}, c_{2} = - \frac{1}{5} \frac{1 - 5}{2}$ Substitute into the general solution

(

)

(

)

(

−

)

F(n) = c_1 ( \cfrac{1 + \sqrt{5}}{2} ) ^n + c_2 ( \cfrac{1 - \sqrt{5}}{2} ) ^n

$F (n) = c_{1} (\frac{1 + 5}{2})^{n} + c_{2} (\frac{1 - 5}{2})^{n}$ in , You can get a general solution :

(

)

(

)

−

(

−

)

F(n) = \cfrac{1}{\sqrt{5}} \cfrac{1 + \sqrt{5}}{2} ( \cfrac{1 + \sqrt{5}}{2} ) ^n - \cfrac{1}{\sqrt{5}} \cfrac{1 - \sqrt{5}}{2} ( \cfrac{1 - \sqrt{5}}{2} ) ^n

$F (n) = \frac{1}{5} \frac{1 + 5}{2} (\frac{1 + 5}{2})^{n} - \frac{1}{5} \frac{1 - 5}{2} (\frac{1 - 5}{2})^{n}$

It is reduced to :

(

)

(

)

−

(

−

)

F(n) = \cfrac{1}{\sqrt{5}}( \cfrac{1 + \sqrt{5}}{2} ) ^{n+1} - \cfrac{1}{\sqrt{5}} ( \cfrac{1 - \sqrt{5}}{2} ) ^{n+1}

$F (n) = \frac{1}{5} (\frac{1 + 5}{2})^{n + 1} - \frac{1}{5} (\frac{1 - 5}{2})^{n + 1}$

Two 、 Complete process of solving recursive equations without multiple roots

Complete process of solving recursive equations without multiple roots :

1 . Write the 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$ ;
- ( 2 ) Number of terms of characteristic equation : determine Number of terms of characteristic equation , And The recurrence equation has the same number of terms ;
- ( 3 ) The characteristic equation is sub idempotent : The highest power is Number of terms of characteristic equation $00 0;$
  $- 1$ , Lowest power
- ( 4 ) Write There is no coefficient The characteristic equation of ;
- ( 5 ) The coefficients of the recursive equation will be deduced bit by bit Copy Into the characteristic equation ;
2 . Solution characteristic root : take The eigenvalue of the characteristic equation is solved , $\cfrac{-b \pm \sqrt{b^2 - 4ac}}{2a}$
$x = \frac{- b \pm b ^{2} - 4 a c}{2 a}$
3 . Construct the general solution of recurrence equation : 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 , The linear combination is the solution of the recursive equation ;
4 . Find the constant in the general solution : Substitute the initial value of the recursive equation into the general solution , obtain
k
k
$k$ individual
k
k
$k$ Finite element equations , By solving the equations , Get the constant in the general solution ;
- ( 1 ) The constant is substituted into the general solution : Get the final solution of the recursive equation ;

Recurrence equation -> Characteristic equation -> Characteristic root -> general solution -> Substitute the initial value to find the general solution constant

原网站

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