# Counting binary strings with a weighted sum of 1s and 0s less than $L$.

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}$.