An inequality related to the number of binary strings with no fixed substring This is basically a repost of this 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.
 A: 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$$
A: This is not quite a proof yet, but might be enough for you to finish it off.
In a random string of length $n$, the expected number of substrings equal to $f$ depends only on the length of $f$.  So the number of strings containing $f$ depends on how much we lose from the expectation by having multiple copies of $f$ in each string.  But the easiest substring to pack is a constant substring; and any substring that cannot overlap with itself under any circumstances is equally hard to pack.  So take $f'$ to be $k$ $0$'s and $f$ to be a $1$ followed by $k$ $0's$: this should be a worst case.  But in this case it is clear that $|S_n(f)| > |S_n(f')|$.
A: You may always assume that $f$ starts with a zero. For each $i = 1,\ldots, n-k+1$, let $S_i$ be the set of strings whose the substring from position $i$ to position $i+k-1$ is equal to $f$. It is trivial that $|S_i| = 2^{n-k}$. The set of strings whose have a substring equal to $f$ is the union of these sets. Therefore, one has the inequality
$$M_n(k) \le (n-k+1)\cdot 2^{n-k}$$
where $M_n(k) = \max Q_n(f)$, and $Q_n(f)$ denotes the number of strings whose have a substring equal to $f$.
Moreover, note that $S_{ij} = S_i \cap S_j$ has the same cardinality $2^{n-2k}$ when $|i - j| \ge k$, and is empty for all $i, j$ such that $|i-j| < k$ if and only if $f$ is not invariant under any translations. (A string is invariant under some translation if any only if it is decomposable (i.e., $f = g \ldots g$ for some string $g$.) Therefore, one can see that $Q_n(f)$ is maximum when $f$ is not invariant under any translations, e.g. $f = 0\ldots 01$. The formula for $M_n(k)$ is possible given that one write $n = k d + r$, and then find out exactly how many $S_I = \cap_{i\in I} S_i$ is non-empty. But for the purpose of proving the inequality the question ask the rough bound above is enough.
Now, $S_{ij}$ has maximum cardinality (the same as being non-empty) for all $|i-j| < k$ if and only if $f$ is invariant under any translations. In other words, $f = 0\ldots 0$. Note that if $S_{ij}$ is empty for some $|i-j| < k$, then it is non-empty for quite a few more, and the $S_{ijk}$ cannot recover much, thus the minimum value of $Q_n(f)$ is obtained at $m_n(k) = Q_n(0\ldots 0).$
Now the $m_n(k)$ follows the following recursive formulas:
For $n = k + i$, with $1\le i \le k-1$, we have 
$$m_{k+i}(k) = m_{k+i-1}(k) + \cdots + m_k(k) + 2^{n-k}.$$
The reason for this recursive formula is that if the last entry of your string is $1$, then you have $m_{k+i-1}$ of the strings, if then the last two entries of your string is $10$, then you have $m_{k+i-1}$, etc, until if the last $i$ entries is $0\cdots 0$, then its last $k$ entries must all be zero, thus the factor of $2^{n-k}$ at the end.
From this recursive formula one deduces that 
$$m_{k+i} = i\cdot 2^{i-1} + 2^i$$
for $i= 0, \ldots, k-1$. 
For $i \ge k$, similarly one has the formula 
$$m_{k+i} = m_{k+i-1} + \cdots + m_{i+1} + 2^i.$$
In particular, $m_{2k} = k\cdot 2^{k-1} + 2^k - 1$ and $m_{k +i} > i\cdot 2^{i-1}$. (Each of the term in the recursive formula for $m_{k+i}$ is larger than $2^i$ (it is actually much larger).  
To prove your inequality, obviously from the explicit formula, it is true when $n \le 2k$. And for $i > k$, it follows from the previous inequality $i\cdot 2^{i-1} < m_{k+i}.$
