[combinatorics] recursive equation (example 1 of recursive equation | list recursive equation)

One 、 Examples of recursive equations 1

---

The coding system uses

8

8

8 Hexadecimal Numbers , Code the information ,

8

8

8 Hexadecimal digits can only be taken

0

,

1

,

2

,

3

,

4

,

5

,

6

,

7

0,1,2,3,4,5,6,7

0,1,2,3,4,5,6,7 ,

Only when a code contains Even number

7

7

7 when , This code is valid ,

seek

n

n

n The number of valid codes in the coding of bits ?

analysis :

n

n

n Bit length encoding , Sure from

n

−

1

n-1

n−1 Bit length encoding , Followed by a

8

8

8 Hexadecimal Numbers constitute ;

For each

n

−

1

n-1

n−1 Bit length encoding , Add a digit after it , Make the final coding Satisfy Requirements for effective coding , It contains an even number

7

7

7 , You can get an effective

n

n

n Bit length encoding ;

1 . set up

n

n

n The number of effective codes of bit length is

a

n

a_n

an​ individual ;

Then there are

n

−

1

n-1

n−1 The number of effective codes of bit length is

a

n

−

1

a_{n-1}

an−1​ individual ;

Now consider

n

n

n Bit length encoding And

n

−

1

n-1

n−1 The correlation between bit length codes ;

( 1 ) Even number

7

7

7 : Suppose there is already one

n

−

1

n-1

n−1 Bit long

8

8

8 Hexadecimal encoding string , It happens to contain an even number

7

7

7 , That is, the code has met the requirements of effective coding , Add a digit :

• Figures that cannot be added : Cannot add $7$
• Numbers that can be added : Can only add $0,1,2,3,4,5,6$

  7 Ways of planting ;

By a

n

−

1

n-1

n−1 Bit long , Code that meets the requirements , Yes

7

7

7 There are ways to generate one

n

n

n Bit length encoding ;

( 2 ) An odd number

7

7

7 : Suppose there is already one

n

−

1

n-1

n−1 Bit long

8

8

8 Hexadecimal encoding string , It happens to contain an odd number

7

7

7 , That is, the code does not meet the requirements of effective coding , Add a digit :

• Figures that cannot be added : Cannot add $0,1,2,3,4,5,6$
• Numbers that can be added : Can only add $7$

  7 , Become a valid code ;

By a

n

−

1

n-1

n−1 Bit long , Codes that do not meet the requirements , Yes

1

1

1 There are ways to generate one

n

n

n Bit length encoding ;

3 . Total number

8

n

−

1

8^{n-1}

8n−1 :

n

−

1

n-1

n−1 The total number of bit length encodings is

8

n

−

1

8^{n-1}

8n−1 individual , Every position has

8

8

8 Two possible options , Yes

n

−

1

n-1

n−1 A place ;

It can also be expressed as :

n

−

1

n-1

n−1 Bits long include , An odd number

7

7

7 , Even number

7

7

7 , The total number of codes is

8

n

−

1

8^{n-1}

8n−1

If there is no

7

7

7 , yes

0

0

0 individual

7

7

7 , Count even numbers

7

7

7 ;

4 .

n

−

1

n-1

n−1 The effective number of bit codes

a

n

−

1

a_{n-1}

an−1​ :

n

−

1

n-1

n−1 In a , Even number

7

7

7 The number of , Is the number of effective codes , That is, the above hypothetical

“ set up

n

n

n The number of effective codes of bit length is

a

n

a_n

an​ individual ” , Then there are

"

n

−

1

n-1

n−1 The number of effective codes of bit length is

a

n

−

1

a_{n-1}

an−1​ individual "

5 .

n

−

1

n-1

n−1 Invalid number of bit codes

8

n

−

1

−

a

n

−

1

8^{n-1} - a_{n-1}

8n−1−an−1​ :

n

−

1

n-1

n−1 Bits long include An odd number

7

7

7 , Even number

7

7

7 Of The total number of codes is

8

n

−

1

8^{n-1}

8n−1

n

−

1

n-1

n−1 In a , Even number

7

7

7 The number of , Namely Number of valid codes , That is, the above hypothetical

a

n

−

1

a_{n-1}

an−1​

be

n

−

1

n-1

n−1 In a , An odd number

7

7

7 The number of , Is the number of invalid codes , The aforementioned Subtract the number of effective codes from the total number , The result is :

8

n

−

1

−

a

n

−

1

8^{n-1} - a_{n-1}

8n−1−an−1​

6 . Analysis section

n

n

n Item and

n

−

1

n-1

n−1 The relationship between items , namely

n

n

n Number of bit effective codes And

n

−

1

n-1

n−1 Number of bit effective codes :

The number of adding methods corresponding to the number of effective codes :

n

−

1

n-1

n−1 The effective number of bit codes

a

n

−

1

a_{n-1}

an−1​ , Contains an even number of

7

7

7 , Each valid code , Add one digit , form

n

n

n Bit valid encoding , Yes

7

7

7 Corresponding addition methods , Add

0

,

1

,

2

,

3

,

4

,

5

,

6

0,1,2,3,4,5,6

0,1,2,3,4,5,6 Numbers , Seven ways ; The number of methods is

7

a

n

−

1

7a_{n-1}

7an−1​

The number of adding methods corresponding to the number of invalid codes :

n

−

1

n-1

n−1 Invalid number of bit codes

8

n

−

1

−

a

n

−

1

8^{n-1} - a_{n-1}

8n−1−an−1​ , There are also odd numbers

7

7

7 , Each invalid code , Only one number can be added

7

7

7 , form

n

n

n Bit valid encoding , There is only one way ; The number of methods is

8

n

−

1

−

a

n

−

1

8^{n-1} - a_{n-1}

8n−1−an−1​

So here we can write

n

n

n The effective number of bit codes

a

n

a_n

an​ And

n

−

1

n-1

n−1 Effective number of bit codes

a

n

−

1

a_{n-1}

an−1​ The relationship between :

a

n

a_n

an​

=

=

=

7

a

n

−

1

7a_{n-1}

7an−1​

+

+

+

8

n

−

1

−

a

n

−

1

8^{n-1} - a_{n-1}

8n−1−an−1​

After simplification, we get :

a

n

a_n

an​

=

=

=

6

a

n

−

1

6a_{n-1}

6an−1​

+

+

+

8

n

−

1

8^{n-1}

8n−1

7 . Initial value discussion

If only

1

1

1 Bit code , It can't be

7

7

7 , This will contain an odd number (

1

1

1 individual )

7

7

7 , Is an invalid code ;

Can only be

0

,

1

,

2

,

3

,

4

,

5

,

6

0,1,2,3,4,5,6

0,1,2,3,4,5,6 this

7

7

7 Kind of , So there is

1

1

1 Bit encoding , The number of effective codes is

7

7

7 individual ,

produce Initial value of recurrence equation

a

1

=

7

a_1 = 7

a1​=7

8 . The resulting recursive equation :

Recurrence equation :

a

n

a_n

an​

=

=

=

6

a

n

−

1

6a_{n-1}

6an−1​

+

+

+

8

n

−

1

8^{n-1}

8n−1

initial value :

a

1

=

7

a_1 = 7

a1​=7

The general term formula for solving the above recursive equation :

a

n

=

6

n

+

8

n

2

a_n = \cfrac{6^n + 8^n}{2}

an​=26n+8n​

Two 、 Summary of recursive equation examples

---

This problem is a specific counting problem , The above problem is not simply counting ,

This count has parameters

n

n

n ,

This type of counting , Can be seen as a Sequence count result ,

If you can find the sequence , consequent , the aforesaid , Dependency of ,

And know initial value ,

Can Solve the general term formula of the sequence ,

The general term formula just corresponds to the counting result ;