Question

) Let an denote number of n-digit ternary sequences (sequences of 0,1 and 2) which have no consecutive 0’s in them. Find a recurrence relation for an. (Do not solve the recurrence. However, depending on the order of the recurrence, provide a sufficient number of initial conditions. )

Answer 1

The recurrence relation for aₙ is aₙ = 2aₙ - 1 + 2aₙ -2 ; is n≥ 3 with the initial conditions as a₁ =3; a₂ = 8

Explanation:

Solution

Recurrence relation for n - digit ternary sequence with no occurrence of consecutive 0's in them.

Ternary sequence is sequence with each of digits either 0, 1 or 2.

Now

Let aₙ = denote the number of n - digit ternary sequence with no occurrence of consecutive 0's in them.

Let us first find few initial values of aₙ

For n = 1

a₁ represent the number of 1- digit ternary sequence with no occurrence of consecutive 0's in them.

This 1-digit sequence can be either 0 or 1 or 2.

Thus,

a₁ = 3

For n =2

a₂ represent the number of 2- digit ternary sequence with no occurrence of consecutive 0's in them.

This 2-digit sequence can have either 0 or 1 or 2 as each of its two digit, but making sure that there are no two consecutive 0 in the sequence.

here are " 9 " 2-digit ternary sequence ........... (three choices for 1st digit and three choices for 2nd digit)

But one of these 9 sequence there are consecutive 0's .... (00)

So we eliminate this one sequence.

So, a₂ = 8

Now

let us find the recurrence relation

Fir n ≥ 3

aₙ s the number of n - digit ternary sequence with no occurrence of the consecutive 0's in them.

For the first case: if 1st digit of this n - digit ternary sequence is 1 or 2

Let assume the 1st digit of this n - digit ternary sequence is 1.

Then for remaining n - 1 digits of this n - digit ternary sequence we have to make sure that there is no consecutive 0's in them.

For example, we have to form a n-1-digit ternary sequence with no occurrence of consecutive 0's in them which is by definition aₙ -1

So,

The number of n - digit ternary sequence with no occurrence of consecutive 0's in them if 1st digit of this sequence is 1 is aₙ -1.

Likewise, the number of n - digit ternary sequence with no occurrence of consecutive 0's in them if 1st digit of this sequence is 2 is aₙ -1.

So

If 1st digit of this n - digit ternary sequence is 1 or 2, then the number of n - digit ternary sequence with no occurrence of consecutive 0's in them is shown as:

aₙ-1 + aₙ -1 = 2aₙ -1

For the second case: if 1st digit of this n - digit ternary sequence is 0

If 1st digit of this n - digit ternary sequence is 0, then the next digit cannot be 0 as well because that would make two consecutive 0's in the sequence Thus,

If 1st digit of this n - digit ternary sequence is 0, the next term can be either 1 or 2.

So there are 2 choices for 2nd digit.

After this there are more n-2 digits.

Then

For remaining n - 2 digits of this n - digit ternary sequence we have to make sure that there is no consecutive 0's in them

For example, we have to form a n-2-digit ternary sequence with no occurrence of consecutive 0's in them. which is by definition aₙ - 2.

Now,

The total number of sequence in this case is given as:

2aₙ -2........... (2 choices for 2nd digit and aₙ - 2 choices for remaining n-2 digit)

Hence

The number of n - digit ternary sequence with no occurrence of consecutive 0's in them if 1st digit of this sequence is 0 is aₙ = 2aₙ - 1 + 2aₙ -2 which is n≥ 3

Now,

The recurrence relation for aₙ is shown below:

aₙ = 2aₙ - 1 + 2aₙ -2; is n≥ 3

With the initial conditions as a₁ =3; a₂ = 8