How many bit strings of length $n$ are there such that every initial segment has more $0$'s than $1$'s? For example, for $n=3$, there are two:
$$\begin{align}
000, 001
\end{align}$$
Let $T(n)$ be the amount of such strings for a given string length $n$. It's clear that $$\begin{align}
T(n) \le 2T(n-1)
\end{align}$$
This is because a new valid string can only be selected from the set of strings created by concatenating a $0$ or $1$ to the valid strings of length $n-1$.
Representing the problem with a binary tree has led me to postulate that if $n$ is odd, then $T(n) = 2T(n-1)$, however the case for $n$ being even is much less clear.
 A: As noted by Jack D'Aurizio, this is an instance of Bertrand's ballot theorem. This theorem proves that the proportion of all bit strings of length $n=p+q$ with $p$ zeroes and $q$ ones for which all initial segments have more zeroes than ones is $\frac{p-q}n$. Since there are ${n\choose q}$ strings all together, this implies that there are $\frac{p-q}n{n\choose q}$ strings including the biased initial segments condition.
The total number of bit strings for any choice of $p,q$ satisfying $p+q=n$ is then $$T(n)=\sum_{q=0}^{\lfloor n/2\rfloor}\frac{n-2q}n{n\choose q}=\sum_{q=0}^{\lfloor n/2\rfloor}{n-1\choose q}-{n-1\choose q-1}={n-1\choose\lfloor n/2\rfloor},$$
since the sum telescopes. And since $${2k\choose k}=\frac{2k}k{2k-1\choose k}=2\cdot{2k-1\choose k},$$
this verifies the claim that $T(2k+1)=2T(2k)$, with the corresponding relation for even $n$ being $T(2k)=(2-\frac1k)T(2k-1)$.
A: Thanks to Jack D'Aurizio for the tip.
Let $p$ be the number of $0$'s and $q$ the number of $1$'s in a string of length $n=p + q$, with $p \gt q$. The number of valid strings $V(p,q)$ is given by:
$$\begin{align}
V(p,q)={p+q-1 \choose p-1}-{p+q-1 \choose p}={n-1 \choose p-1}-{n-1 \choose p}\
\end{align}$$
Therefore to find all strings of length $n$, all valid pairs of $p$ and $q$ must be summed. Let $A(n) = \{\ (p,q) : p + q = n;\  p > q \  \}$. We then have:
$$\begin{align}
T(n)= \sum_{(p,q) \in A(n) }V(p,q)
\end{align}$$
Let $m$ be the lowest possible value for $p$ for a given $n$. We have:
$$\begin{align}
T(n)&=\sum_{i=m}^{n-1}\left({n-1 \choose i-1}-{n-1 \choose i}\right) + 1 \\
 &=\left({n-1 \choose m-1}-{n-1 \choose n-1}\right) + 1 \\
&= {n-1 \choose m-1}
\end{align}$$ 
Note that when $p = n$, $V(p,q)=1$, so instead of summing to $i=n$, we replaced it with $1$. 
For odd $n$, $m=\lceil\frac{n}{2}\rceil$, and for even $n$, $m=\frac{n}{2}+1$. 
This was a surprising answer to me, given how simple it ended up!
