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?

 A: 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.
