Let $b_k \cdots b_0$ be the binary string $b$ and let $m$ be the number of $0$s and $n$ be the number of $1$s in this representation. How do I count all strings $b$ such that $m+2n \leq L$?

I came up with $$\sum_{n=0}^{\lfloor L/2 \rfloor} \sum_{m=0}^{L-2n} {n+m \choose n}$$ but I am hoping someone can come up with a better expression with a better argument.


For a nonzero binary number with $m$ zeros and $n$ ones, the most significant bit must be $1$; the other $m+n-1$ bits can be any combination of zeros and $1$'s, and there are ${m+n-1 \choose m}$ of them. Now you want $m+2n \le L$, i.e. for any $n$ with $1 \le n \le \lfloor N/2 \rfloor$, $m$ can be anything from $0$ to $L - 2 n$. Counting also $0$, the result is

$$ 1 + \sum_{n=1}^{\lfloor L/2 \rfloor} \sum_{m=0}^{L-2n} {m+n-1 \choose m} $$

But $$ \sum_{m=0}^{L-2n} {m+n-1 \choose m} = {L-n \choose n} $$ so you can write this as $$1 + \sum_{n=1}^{\lfloor L/2 \rfloor]} {L-n \choose n} $$

And then this turns out to be the Fibonacci number $F_{L+1}$.

EDIT: The recurrence relation, once you look for it, comes about in this way. Let $f(x) = m(x) + 2 n(x)$ where $m(x)$ and $n(x)$ are the numbers of $0$'s and $1$'s in $x$. Let $b(L)$ be the number of nonnegative integers $x$ with $f(x) = L$. Then $b(1) = b(2) = b(3) = 1$ (the only numbers $x$ with $f(x)=1$ being $0$, the only one with $f(x) = 2$ being $1$, the only one with $f(x)=3$ being $2$). To get a number with $f(x) = L \ge 4$, you either append a $0$ to the binary representation of a number with $f(x) = L-1$ or a $1$ to one with $f(x) = L-2$. Thus $b(L) = b(L-1) + b(L-2)$ for $L \ge 4$. Using induction, we get $b(L) = F_{L-2}$ for $L \ge 2$. Next use induction to show that $\sum_{j=1}^L b(j) = F_{L+1}$.

  • $\begingroup$ Oh, once you mention the fibonacci number it seems obvious to have used a recurrence relation! $\endgroup$ – abnry Jun 7 '17 at 17:30

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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