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?

  • $\begingroup$ @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$ $\endgroup$ – Jernej Nov 27 '13 at 5:55
  • $\begingroup$ Right you are. I was confused by thinking about the problem of which comes first. But that is not the case here. $\endgroup$ – Ross Millikan Nov 27 '13 at 6:00
  • $\begingroup$ 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. $\endgroup$ – Ross Millikan Nov 27 '13 at 6:12
  • $\begingroup$ @RossMillikan I've checked the conjecture for all $n$ up to $12$ and $|f| \leq n$ and it appears to be true. $\endgroup$ – 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.

| cite | improve this answer | |

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.