# Math Help - bit strings and substring

1. ## bit strings and substring

How many bit strings of length 16 do not contain 00 as a substring? How can I set up a recurrence relation to answer this questiong?
Any help will be appreciated, Thanks.

2. Originally Posted by peng783
How many bit strings of length 16 do not contain 00 as a substring? How can I set up a recurrence relation to answer this questiong? Thanks.
$\sum\limits_{k = 0}^8 {\binom{17-k}{k}}$