This is basically a repost of [this](https://math.stackexchange.com/questions/582835/an-inequality-related-to-the-number-of-binary-strings-with-no-fixed-substring) math.se question. At the time I was writing this I thought it has to have a straightforward solution so I posted it there. Now I am not so sure about it being so easy. The problem is as follows.


Let $f \in \{0,1\}^k$ and let $S\_n(f)$ be the number of strings of $\{0,1\}^n$ that do not contain $f$ as a substring. Is it true that $$|f| > |f'| \implies S\_n(f) > S\_n(f')$$


I am aware that the transfer-matrix method could be used to compute $S\_n(f)$ given a concrete $f.$ I don't know though if it offers a solution to this problem or perhaps if there's any other obvious reason why this is true.



An inequality related to the number of binary strings with no fixed substring
Your conjecture is true. Here is a proof.


Define $\operatorname{Av}\_n(w)$ to be the number of binary words of length $n$ which avoid the pattern $w$.


Let $u$ and $v$ be binary words with $|u| = k$ and $|v|=m$ with $k < m$. We will show that $\operatorname{Av}\_n(u) < \operatorname{Av}\_n(v)$ for all $n$.


Define the special words
 $$M\_n = \overbrace{00\cdots00}^n\qquad\text{and}\qquad L\_n = \overbrace{00\cdots01}^n.$$


We can show fairly easily using the cluster method of Goulden and Jackson (and other ways as well, though the cluster method works easily for any pattern) that words avoiding $M\_n$ and words avoiding $L\_n$ have the generating functions
 $$m\_n(x) = \sum\_{r \geq 0}\operatorname{Av}\_r(M\_n)x^r = \frac{1-x^n}{1-2x+x^{n+1}}$$
and
 $$\ell\_n(x) = \sum\_{r\geq 0} \operatorname{Av}\_r(L\_n)x^r = \frac{1}{1-2x+x^n}.$$


Moreover, of all words $w$ with $|w|=n$, $M\_n$ is the most avoided word and $L\_n$ is the least avoided word. Formally, for $w$ with $|w|=n$ and all $r$
 $$\operatorname{Av}\_r(L\_n) \leq \operatorname{Av}\_r(w) \leq \operatorname{Av}\_r(M\_n).$$


This can be seen probabilistically by observing that the number of occurrences of a pattern of length $n$ in *all* words of length $r$ is independent of what the pattern is. Since $M\_n$ "packs" the most easily (i.e., has a lot of overlaps) and $L\_n$ does not "pack" at all (i.e., cannot overlap itself), it follows that $M\_n$ appears as a pattern in less words overall than any other pattern and $L\_n$ appears as a pattern in more words overall than any other pattern.


It should also be obvious that $\operatorname{Av}\_r(L\_n) \leq \operatorname{Av}\_r(L\_{n+1})$ for all $r$.


We need to prove one more fact: $\operatorname{Av}\_r(M\_{s-1}) < \operatorname{Av}\_r(L\_s)$ for all $r \geq s-1$. 


**Edit:** As @DavidSpeyer pointed out in a comment, this is easily proved by observing that $M\_{s-1}$ is a subword of $L\_s$. I've removed my lengthier argument, but left the generating functions $m\_n(x)$ and $\ell\_n(x)$ defined above.


We now combine all of our results: for $r \geq k$
 $$\operatorname{Av}\_r(u) \leq \operatorname{Av}\_r(M\_k) < \operatorname{Av}\_r(L\_{k+1}) \leq \operatorname{Av}\_r(L\_m) \leq \operatorname{Av}\_r(v).\;\;\square$$


