How many such strings are there? How many 50($=n$) digit strings($=f(n)$) composed of only zeros and ones are there such that all "ones" should be in groups of at least 3(The grouping should be explicit), if they occur and must be separated by atleast one "zero".
Valid Examples:
$$(111)0(111),\;\;\;(1111)00(111)0(11111)0(111)000$$
InValid Examples:
$$(111)(11),\;\;(111)(111),\;\;(111)0(11)$$
It is easy to find it by explicitly writing for lower n. Also it seems that $f(n)$ follows recursion but I can't write it.
I also tried using stars and bars with no progress.
An Explanatory Example:
$$f(7)=17$$
$$\begin{array}{|c|c|c|c|}\hline 1&0000000&10&00(1111)0\\2&(111)0000&11&000(1111)\\3&0(111)000&12&0(1111)00\\4&00(111)00&13&00(1111)0\\5&000(111)0&14&000(1111)\\6&0000(111)&15&(11111)00\\7&(111)0(111)&16&0(11111)0\\8&(1111)000&17&1111111\\9&0(1111)00&&\\\hline\end{array}$$
 A: Let $f_0(n),f_1(n),f_2(n),f_{\ge3}(n)$ be the number of such strings ending in $0,1,2,,\ge3$ ones. Then we have recursions
$$\begin{align} f_0(n+1)&=f_0(n)+f_{\ge3}(n)\\
f_1(n+1)&=f_0(n)\\
f_2(n+1)&=f_1(n)\\
f_{\ge3}(n+1)&=f_2(n)+f_{\ge3}(n)
\end{align}$$
or in matrix form: We multiply $(f_0(n),f_1(n)f_2(n),f_{\ge3}(n))^T$ by
$$A=\begin{pmatrix}1&0&0&1\\1&0&0&0\\0&1&0&0\\0&0&1&1\end{pmatrix} $$
and find from this that
$$f(n)=f_0(n)+f_{\ge3}(n)=\alpha_1\lambda_1^n+\alpha_2\lambda_2^n+\alpha_3\lambda_3^n+\alpha_4\lambda_4^n $$
where the $\lambda_i$ are the eigenvalues of $A$ and the $\alpha_i$ can be obtained from $f(0),f(1),f(2),f(3)$.
It turns out that the eignevalues are $\frac{1\pm\sqrt 5}{2}$ and $\frac{1\pm i\sqrt 3}2$ and using $f(0)=f(1)=f(2)=1$, $f(3)=2$ we arrive after a bit of playing around at
$$ f(n)=\underbrace{\frac1{2\sqrt 5}\left(\frac{1+\sqrt 5}{2}\right)^{n+2}-\frac1{2\sqrt 5}\left(\frac{1-\sqrt 5}{2}\right)^{n+2}}_{=\frac12F_{n+2}}+\frac1{\sqrt 3}\sin\frac{(n+2)\pi}{3}$$
For example
$$f(7)=\frac12 F_9+\frac1{\sqrt 3}\sin3\pi=17. $$
A: So here's a more elementary way to find a recursion:
Denote $a(n)$ be the number of such strings that end up with a 0.
Denote $b(n)$ the number of strings that end up with a 1.
Now, we find $f(n)=a(n)+b(n)$.
Also, easily we obtain $a(n+1)=f(n)=a(n)+b(n)$ since we can add a 0 to any string.
Now, we are left to find a recursion for $b(n+1)$.
For any such string, the last three digits need to be "ones". So if at the end we have exactly $k$ "ones" (here $k \ge 3$) we have $a(n+1-k)$ ways to choose the remaining string.
So $b(n+1)=a(n-2)+a(n-3)+\dotsc+a(1)+1$ i.e. $b(n+1)=b(n)+a(n-2)$.
Now, we are able to solve for $f(n)$.
Using our first recursion, we find $b(n)=a(n+1)-a(n)$.
Plugging this into the second recursion, we find
$$a(n+2)=2a(n+1)-a(n)+a(n-2)$$
Since we established $a(n)=f(n-1)$ above, we further conclude
$$f(n+2)=2f(n+1)-f(n)+f(n-2)$$
This together with the starting values $f(0)=f(1)=f(2)=1, f(3)=2$ gives the correct values
$f(4)=4, f(5)=7, f(6)=11, f(7)=17$ so it seems to work...
Of course, solving the characteristic equation $x^4-2x^3+x^2-1=0$ we can find a closed formula for $f(n)$ but this does not give much more insight than the recursion.
