A block in a bitstring s is a maximal sequence of consecutive 1\'s. For example,

Question

A block in a bitstring s is a maximal sequence of consecutive 1's. For example, the bitstring s = 11011101000 contains the three blocks 11 0 111 0 I 000. A bitstring is called awesome, if each of its blocks has an even length. Thus, the bitstring above is not awesome, whereas both bitstrings 00011011110 and 0000000 are awesome. For any integer n > 1. let An denote the number of awesome bitstrings of length n. Determine A_1, A_2, A_3 and A_4. Determine the value of A_n, i.e., express A_n in terms of numbers that we have seen in class.

Explanation / Answer

Binary string length 1 with even amount of 1s : A1 = 0

Binary string length 2 with even amount of 1s : A2 = 11,00;

Binary string length 3 with even amount of 1s : A3 = 000;011;110;

Binary string length 4 with even amount of 1s : A4 = 0000;0011;1111;1100,0110,

Binary string length with even amount of 1s : we get total of 8 such bitstrings

Now as we can see the trend follows Fibonacci series

So now An will be the nth Fibonacci number

So now we will use Binet's Formula for the nth Fibonacci number and we get the answer as

..

An = Fib(n) = (1.6180339..)^n – (–0.6180339..)^n / 2.236067977..

Related Questions

Navigate

• Browse (All)
• Browse A
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.