Q2. [9 marks] Here we work with the set of sequences of 0’s and 1’s of length n. we will call such a sequence good if it
Posted: Sat Feb 26, 2022 10:59 am
Q2. [9 marks] Here we work with the set of sequences of 0’s and
1’s of length n. we will call such a sequence good if it never has
three 1’s in a row. Otherwise it is bad. Let 𝐺𝑛 and 𝐵𝑛 be the
number of good and bad sequences of length n. For example, of the
following sequences of length 9, the first two are good and the
second two are bad:
101101000 110110110 100111000 000011111
Construct a recursive equation that generates the 𝐺𝑛––that is,
find a formula for 𝐺𝑛 in terms of some of the preceding 𝐺𝑘. Use a
careful argument to justify your equation. Note that you are not
asked to solve the recursion, but to make an argument, based on the
property of the sequences, that your recursive formula must hold.
If you don’t want to work with a general n, you can do what I often
do in class and work with particular numbers, for example, taking n
= 7.
1’s of length n. we will call such a sequence good if it never has
three 1’s in a row. Otherwise it is bad. Let 𝐺𝑛 and 𝐵𝑛 be the
number of good and bad sequences of length n. For example, of the
following sequences of length 9, the first two are good and the
second two are bad:
101101000 110110110 100111000 000011111
Construct a recursive equation that generates the 𝐺𝑛––that is,
find a formula for 𝐺𝑛 in terms of some of the preceding 𝐺𝑘. Use a
careful argument to justify your equation. Note that you are not
asked to solve the recursion, but to make an argument, based on the
property of the sequences, that your recursive formula must hold.
If you don’t want to work with a general n, you can do what I often
do in class and work with particular numbers, for example, taking n
= 7.