

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer

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|cite|improve this question

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


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
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|cite|improve this answer
