Warning: count(): Parameter must be an array or an object that implements Countable in /home/customer/www/thegatebook.in/public_html/qa/qa-include/qa-theme-base.php on line 177

# DM-Probability -Q15

Warning: count(): Parameter must be an array or an object that implements Countable in /home/customer/www/thegatebook.in/public_html/qa/qa-include/qa-theme-base.php on line 177

A recurrence relation for the number of bit strings of length that do not contain three consecutive 0s. represents number of such bit strings of length .

reshown Jul 10, 2020

Easiest way is

f(1) is 2 namely 0 and 1

f(2) is 4 namely 00, 01, 10 and 11

f(3) is 001, 010,011,100,101,110,111 which is 7 as we didn't include 000

f(4) = all strings except for 0000,1000 and 0001 which is 16-3 = 13

Also, I am able to see a recurrence relatIon here

f(4) = f(3) + f(2) + f(1)

For fun, solving for f(5)

All 5 bit strings except for 00000,00001,00010,00011,01000,10000,10001,11000

which is 32-8 which is 24

Now you can see it is 13+7+4 = 24

Yippie,