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