# An inequality related to the number of binary strings with no fixed substring

Let $f \in \{0,1\}^k$ and let $S_n(f)$ be the number of strings from $\{0,1\}^n$ that do not contain $f$ as a substring. As an interesting example $S_n(11) = f_{n+2}$ where $f_n$ is the $n$'th Fibonacci number.

I would like to show that if $|f| > |f'|$ then $$S_n(f) > S_n(f')$$ where of course $n \geq \rm{max}(|f|,|f'|).$

I am trying to prove the claim by induction and get stuck in the inductive step. Let us suppose that for all $\rm{max}(|f|,|f'|) \leq n < k$ we have $S_n(f) < S_n(f')$ and let $n = k.$ Without loss of generality we may assume that both $f$ and $f'$ start with $0.$

Now let $S^{0}_n(f), S^{1}_n(f)$ be the number of binary strings of length $n$ that start with 0 or 1 respectively and do not contain $f.$ Then $S_n(f) = S^{1}_n(f) + S^{0}_n(f)$ and since $f$ starts with zero $S^{1}_n(f) = S_{n-1}(f).$ Hence we can apply induction hypothesis on $S_{n-1}(f)$ and $S_{n-1}(f')$ yet it remains to show that $S^{0}_n(f) \geq S^{0}_n(f')$ which does not appear to be any easier than the original inequality.

Hence I would like to ask

1.Is there a way to finish this inductive argument properly?

2.Is there any other way to show this claim, perhaps by using more advanced tools?

• @RossMillikan Observe that $S_n(f) = S_n(\overline{f})$ where $\overline{f}$ is the string obtained by inverting the bits in $f.$ Hence you can always assume both start with $0$ – Jernej Nov 27 '13 at 5:55
• Right you are. I was confused by thinking about the problem of which comes first. But that is not the case here. – Ross Millikan Nov 27 '13 at 6:00
• This is a great question. I think it would be more useful to have $S_n(f)$ be the number of $n$ bit strings that contain $f$ and $T_n(f,m)$ be the number of $n$ bit strings that do not contain $f$ but include as a prefix the last $m$ bits of $f$. Then if $f$ is $0000$'s and you draw a $1$ you are back to the beginning. If $f'$ is $01011$, you have the $1011$, and draw a $1$, you have the first two bits already. I don't know if this makes a counterexample, but it is where I would look. – Ross Millikan Nov 27 '13 at 6:12
• @RossMillikan I've checked the conjecture for all $n$ up to $12$ and $|f| \leq n$ and it appears to be true. – Jernej Nov 27 '13 at 8:09

Let $Q_n(f)$ be the number of bit strings of length $n$ that contain $f$ as a substring. Also let $B_n=2^n$ be the number of bit strings at all of length $n$. Then clearly $$B_n=Q_n(f)+S_n(f)$$ which just states that bit strings of length $n$ either does or does not contain $f$ as a substring. Furthermore, it is easy to see that $$S_n(f)>S_n(f')\iff Q_n(f)<Q_n(f')$$ Now assume $|f|=k$ and let us see what happens to $Q_n(f)$ for $n\geq k$. Quite obviously $$Q_k(f)=1$$ So what about $Q_{k+1}(f)$? We have four possible candidates for different bit strings of length $k+1$ containing $f$ as a substring, namely $0f,1f,f0,f1$. If $f$ consists of repeating digits, say $f=000...0$ then $0f=f0$ whereas the other two $1f,f1$ are different, so then $Q_{k+1}(f)=3$. If $f$ consists of mixed digits then we are guaranteed that all four are different. Then $Q_{k+1}(f)=4$.
Next case to consider is $Q_{k+2}(f)$: We have the twelve candidates \begin{align} 00f,&&01f,&&10f,&&11f\\ 0f0,&&0f1,&&1f0,&&1f1\\ f00,&&f01,&&f10,&&f11 \end{align} If again $f=000...0$ then $f$ commutes with zeros so that $00f=0f0=f00$ and $10f=1f0$ and $f01=0f1$. So in this case we only have eight distinct strings so $Q_{k+2}(f)=8$. Next, if $f=0101...01$ (even length) then $f$ commutes with $01$ so $f01=01f$ hence $Q_{k+2}(f)=11$. On the other hand if $f$ is symmetrical and $f=1010...0101$ (odd length) then $10f=f01$ and again $Q_{k+2}(f)=11$. In a way you can say the above examples are $f$'s consisting of repeated length $2$ substrings. So if $f$ cannot be constructed by repeating length-$2$-strings, all $12$ candidates above are different. Then $Q_{k+2}(f)=12$.
So far we have found that for $|f|=k$ some values of $Q_n(f)$ are: \begin{align} Q_{k}(f)&=1\\ Q_{k+1}(f)&\in\{3,4\}\\ Q_{k+2}(f)&\in\{8,11,12\} \end{align} In general for $|f|=k$ and $Q_{k+r}(f)$, I suspect we will have $2^r(r+1)$ candidates since $f$ can be placed in $r+1$ places in each of the $2^r$ possible bit strings of length $r$, and the case where the fewest of these produce different strings is when $f=00...0$ or $f=11...1$. So suppose $f=00...0$. Then $$00...0f=00...f0=0...f00=...=f00...0$$ are $r+1$ identical candidates thus removing $r$ candidates from the list. Similarly $$100..0f=100...f0=10...f00=...=1f00...0\\ \mbox{and}\\ 00...0f1=00...f01=0...f001=...=f00...01$$ are $r$ identical candidates and another $r$ identical candidates thus removing $2(r-1)$ candidates from the list.