hello!
well I need help with this problem:
Find a recurrence relation for the number of bit strings of length n that contain three consecutive 0's
ok the answer is:
Let
sn be the number of n-bit strings that contain three consecutive zeros. Such strings can start with
1 (there are sn−1 of these), or with 01 (there are sn−2 of these), or with 001 (there are sn−3 of these), or
with 000 (there are 2n−3 of these). Therefore sn = sn−1 + sn−2 + sn−3 + 2n−3, for n 3.
http://www.ics.uci.edu/~stasio/fall07/6D/sol8.pdf
Ok but can someone explain to me why did they say: such strigns can start with 1,01,001 or 000?
from where did they get these?
thank you