[combinatorics] recursive equation (outline of recursive equation content | definition of recursive equation | example description of recursive equation | Fibonacci Series)

One 、 Recurrence equation Contents summary

---

Recurrence equation Contents summary :

• Recursive equation definition
• Examples of recursive equations
• Constant coefficient linear recurrence equation
  • Definition of linear recurrence equation with constant coefficients
  • Formula solution
• Application of recurrence equation in counting problem

Two 、 Recurrence equation Definition

---

Sequence

a

0

,

a

1

,

⋯
 

,

a

n

,

⋯

a_0 , a_1 , \cdots , a_n , \cdots

a0​,a1​,⋯,an​,⋯ , Remember to do

{

a

n

}

\{a_n\}

{ an​} ,

take

a

n

a_n

an​ And some

a

i

  

(

i

<

n

)

a_i \ \ ( i < n )

ai​  (i<n) Connected equations ,

a

i

a_i

ai​ It can be

1

1

1 individual , It can be multiple ;

take

a

n

a_n

an​ Use the previous items

a

n

−

1

,

a

n

−

2

,

⋯

a_{n-1} , a_{n-2} , \cdots

an−1​,an−2​,⋯ Express it ,

be called About sequence

{

a

n

}

\{a_n\}

{ an​} Of Recurrence equation ;

The recursive equation consists of : below

3

3

3 One is a set ;

• The sequence
• Recurrence equation
• initial value

Given the recurrence equation , and initial value , Can Uniquely identify a sequence ;

• The relationship expressed by recurrence equation : Recurrence equation It only expresses Item is the same as the previous item The relationship between , If Different initial values , The resulting sequence is different ;

• The relationship between recurrence equation and sequence : Recursive equations do not represent a sequence , yes Several series Of Common dependencies ;

Recurrence equation , Is to count the result , Expressed as a sequence ,

{

a

n

}

\{a_n\}

{ an​} Is the general term formula ;

Sequence example : Such as selecting questions , from

n

n

n Of the elements

r

r

r Elements , If

n

n

n Given , that

r

r

r That's the parameter ,

• When $r=0$
• When $r=1$
• When $r=n$

The general term of the sequence , Represents some kind of counting result ;

3、 ... and 、 Recurrence equation Example

---

1 . Factorial calculation sequence :

1

!

,

2

!

,

3

!

,

4

!

,

5

!

,

6

!

,

⋯

1! , 2! , 3! , 4! , 5! , 6! , \cdots

1!,2!,3!,4!,5!,6!,⋯

In sequence The first

1

1

1 Item is

1

1

1 The factorial , The first

2

2

2 Item is

2

2

2 The factorial ,

⋯

\cdots

⋯ , The first

n

n

n Item is

n

n

n The factorial ;

2 . Recurrence equation :

F

(

n

)

=

n

F

(

n

−

1

)

F(n) = nF(n-1)

F(n)=nF(n−1)

Such as : The first

4

4

4 Item value

F

(

4

)

=

5

!

F(4) = 5!

F(4)=5! , It is equal to

4

−

1

=

3

4-1=3

4−1=3 Item value

F

(

4

−

1

)

=

F

(

3

)

=

4

!

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

F(4−1)=F(3)=4! multiply

5

5

5 ;

3 . initial value :

F

(

1

)

=

1

F(1) = 1

F(1)=1

according to

F

(

1

)

=

1

F(1) = 1

F(1)=1 You can calculate

F

(

2

)

F(2)

F(2) , according to

F

(

2

)

F(2)

F(2) You can calculate

F

(

3

)

F(3)

F(3) , according to

F

(

3

)

F(3)

F(3) Sure Calculation

F

(

4

)

F(4)

F(4) ,

⋯

\cdots

⋯ , according to

F

(

n

−

1

)

F(n-1)

F(n−1) You can calculate

F

(

n

)

F(n)

F(n) ;

Four 、 Fibonacci sequence ( Fibnacci )

---

1 . Fibonacci sequence :

1

,

1

,

2

,

3

,

5

,

8

,

13

,

⋯

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

1,1,2,3,5,8,13,⋯

2 . Recurrence equation :

F

(

n

)

=

F

(

n

−

1

)

+

F

(

n

−

2

)

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

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

describe : The first

n

n

n Item equal to

n

−

1

n-1

n−1 term and The first

n

−

2

n-2

n−2 Sum of items ;

Such as : The first

4

4

4 Item value

F

(

4

)

=

5

F(4) = 5

F(4)=5 , Is equal to

The first

4

−

1

=

3

4-1=3

4−1=3 Item value

F

(

4

−

1

)

=

F

(

3

)

=

3

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

F(4−1)=F(3)=3

add The first

4

−

2

=

2

4-2=2

4−2=2 Item value

F

(

4

−

2

)

=

F

(

2

)

=

2

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

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

according to

F

(

0

)

=

1

,

F

(

1

)

=

1

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

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

F

(

2

)

F(2)

F(2) , according to

F

(

1

)

,

F

(

2

)

F(1),F(2)

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

F

(

3

)

F(3)

F(3) , according to

F

(

2

)

F

(

3

)

F(2)F(3)

F(2)F(3) Sure Calculation

F

(

4

)

F(4)

F(4) ,

⋯

\cdots

⋯ , according to

F

(

n

−

2

)

,

F

(

n

−

1

)

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

F(n−2),F(n−1) You can calculate

F

(

n

)

F(n)

F(n) ;