Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

This question already has an answer here:

Refer to the sequence $S$ where $S_n$ denotes the number of n-bit strings that do not contain the pattern 00. By considering the number of n-bit strings with exactly i 0's, show that

$\displaystyle f_{n+2} = \sum_{i=0}^{\frac{n+1}{2}} \binom{n+1 - i}{i}$ for $n=1,2,\dots$ where $f$ denotes the Fibonacci sequence.

So I know the Fibonacci sequence consists of $0, 1, 1, 2, 3,\dots$ And $S_n=f_{n+2}$. But what else?

Any help is appreciated. Thanks!

share|improve this question

marked as duplicate by Grigory M, Michael Lugo, Mark Bennet, Adam Hughes, BlackAdder Jan 7 at 0:30

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

By $C$ do you mean binomial coefficient? –  rubik Jul 12 '12 at 10:05
I've formatted your question with $\LaTeX$, it'll be applied when someone will approve it. –  rubik Jul 12 '12 at 10:05
This seems to be the same question as this one (or at least very similar): How to show that this binomial sum satisfies the Fibonacci relation?. Only one answer there, perhaps it would deserve adding something more. –  Martin Sleziak Jul 12 '12 at 10:27

1 Answer 1

up vote 1 down vote accepted

How many strings of length $n$ which do not contain "00" and contains precisely $i$ zeroes are there?

Notice that any zero must be followed by 1 or be at the and. For the sake of simplicity, let us consider string of length $n+1$ which is obtained by adding 1 to the original string.

So no we are counting the strings of length $n+1$ which are obtained from $i$ strings of the form "01" with 1's on the remaining position.

If we regard the whole string "01" as one character, then there are only $n+1-i$ positions and we have to place this "combined character" on $i$ of them. So we have $\binom{n+1-i}i$ positions.

BTW this can be regarded as a more detailed solution based on the hint from this answer.

share|improve this answer

Not the answer you're looking for? Browse other questions tagged or ask your own question.