I want to count the number of binary strings which meet the following three conditions:
How many strings of length $n$ meet those conditions?
On
HINT: Suppose that there are $k$ ones. Then there are $k+4$ zeroes, so $n=2k+4$. In particular, $n$ must be even, so if $a_n$ is the number of acceptable strings of length $n$, then $a_n=0$ when $n$ is odd. Now it’s just a matter of counting the ways to place $k$ ones in a string of length $2k+4$ in such a way that no two of them are adjacent, and at least one of the end characters is a zero.
Think of the ones as dividers; your task is to distribute the $k+4$ zeroes in the $k+1$ spaces before, between, and after the ones in such a way that each of the $k-1$ internal spaces gets at least one zero, and at least one of the end spaces gets a zero. This is a slight variation of a standard stars and bars problem.
On
Suppose we seek to count binary string of length $n$ that meet these conditions:
Use $z$ to represent the zeros and $w$ to represent the ones.
We have for the case of the string that starts and ends in zero the generating function
$$G(z,w) = \frac{z}{1-z} \sum_{k\ge 0} \left(w \frac{z}{1-z}\right)^k = \frac{z}{1-z} \frac{1}{1-wz/(1-z)} \\ = \frac{z}{1-z-wz}.$$
There are two more possibilities corresponding to a leading or trailing one but not both. This gives
$$H(z,w) = G(z,w) + wG(z,w) + G(z,w)w = \frac{z}{1-z-wz} (1+2w).$$
Now observe that
$$[z^n] F(z) = \frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{1}{z^{n+1}} F(z) \; dz$$
so that we get for the cofficient $[z^{q+t} w^q] H(z,w)$ (the initial representation of $G(z,w)$ is more useful here)
$$\frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{1}{z^{q+t+1}} \frac{1}{2\pi i} \int_{|w|=\epsilon} \frac{1}{w^{q+1}} \frac{z}{1-z-wz} (1+2w) \; dw\; dz \\ = \frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{1}{1-z} \frac{1}{z^{q+t+1}} \frac{1}{2\pi i} \int_{|w|=\epsilon} \frac{1}{w^{q+1}} \frac{z}{1-wz/(1-z)} (1+2w) \; dw\; dz.$$
Extracting coefficients in $w$ yields
$$\frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{1}{1-z} \frac{1}{z^{q+t+1}} \left(\frac{z^{q+1}}{(1-z)^q} + 2 \frac{z^{q}}{(1-z)^{q-1}} \right) \; dz.$$
This has two pieces call them $X_1$ and $X_2.$ We obtain for $X_1$
$$\frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{1}{(1-z)^{q+1}} \frac{1}{z^{t}} \; dz = {t-1+q\choose q}$$
and for $X_2$
$$2\frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{1}{(1-z)^q} \frac{1}{z^{t+1}} \; dz = 2{t+q-1\choose q-1}.$$
Collecting $X_1$ and $X_2$ yields
$$\frac{t}{q} {t+q-1\choose q-1} + 2 {t+q-1\choose q-1} = \frac{2q+t}{q} {t+q-1\choose q-1}.$$
Given that $2q+t=n$ we can re-write this as $$\frac{n}{(n-t)/2} {t+(n-t)/2-1\choose t} = \frac{2n}{n-t} {(n+t)/2-1\choose t}.$$
Further re-arrangeing yields
$$\frac{2n}{n-t} \frac{(n-t)/2}{(n+t)/2} {(n+t)/2\choose t} = \frac{2n}{n+t} {(n+t)/2\choose t}.$$
Remark. Admittedly we don't need complex variables here, we can just use the Newton binomial. E.g.
$$[w^q] \frac{z}{1-z-wz} = \frac{1}{1-z} [w^q] \frac{z}{1-wz/(1-z)} = \frac{1}{1-z} \frac{z^{q+1}}{(1-z)^q}$$
and so on.
Let $S_{n,t}$ be the number of strings of length $n$ that have exactly $t$ more $0s$ than $1s$, with no two consecutive $1s$, and end with $0$. Then, each $1$ will have a companion $0$ at its right. We have $p$ such "$10$" pairs, with $2 p +t = n$ (this implies $n-t$ must be even).
Then $S_{n,t}$ counts all the possible arrangements of these pseudo $p+t$ elements ($p$ $01$ pairs and $t$ $0$s), which is $$ S_{n,t}={p+t \choose t}={\frac{1}{2}(n+t) \choose t}$$
We are left with the strings that, again, have exactly $t$ more $0s$ than $1s$, no two consecutive $1s$, but now end with $1$ (hence they must start with $0$). Considering the effect of removing these extreme elements, the shortened string fullfills the condition of the previous case, so the counting is $S_{n-2,t}$
Then the total number is
$$ S_{n,t}+S_{n-2,t}={\frac{1}{2}(n+t) \choose t}+{\frac{1}{2}(n+t)-1 \choose t} ={\frac{1}{2}(n+t) \choose t} \frac{2\,n}{n+t}$$