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.

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
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
add comment

1 Answer

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
add comment

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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