I'm trying to solve a university question we were asked to find the recursive relation between number of possible bit strings of length n containing sequence 0,1. I tried to reason logically and given in a lot of similar question it was useful to make case distinction by the value of last bit came up with the following relation: $T_n = (T_{n-2} + 1) + T_{n-1}$ as the first part of the sum represents the case where the last bit is 1 and hence there is just single way those last 2 bits can form a sequence so its the value from the term 2 iterations before plus that one variant. And if it's zero then we know that the same number of variants is for bit string of that length as for the one without that zero. However after charting some truth tables up to $T_5$ I've noticed that my results differ by a whole lot from what can be acquired from formula and I'm not sure why as the logic does make sense to me.

P.S. I've decided to make my initial conditions $T_0 = 0, T_1 = 0$ as it seemed logical enough.

  • $\begingroup$ You just mean it has to contain $01$ as a block? But the only words that don't contain that block are of the form $1^a0^b$. $\endgroup$
    – lulu
    Commented Dec 11, 2021 at 22:30
  • $\begingroup$ @lulu yes, that what is implied $\endgroup$ Commented Dec 11, 2021 at 22:31
  • $\begingroup$ Ok...but it is really easy to count those. If you want length $n$, we must have $a\in \{0, \cdots, n\}$ so there are $n+1$ bad words of length $n$. $\endgroup$
    – lulu
    Commented Dec 11, 2021 at 22:31
  • $\begingroup$ but i cannot define a general sequence, or come up with other combinatoric solution. It has to be recursive relation and hence I'm not sure how to preserve the number of bad words without using the terms idx or having 2 sequences $\endgroup$ Commented Dec 11, 2021 at 22:34
  • $\begingroup$ I don't understand. What I wrote is a complete solution and it certainly uses combinatorics. Anyway, given the easily found solution to the problem, it is easy to see what recursion it satisfies. $\endgroup$
    – lulu
    Commented Dec 11, 2021 at 22:37

1 Answer 1


To summarize the discussion in the comments:

The bad sequences are all of the form $1^a0^b$ so there are $n+1$ of them of length $n$. Thus the total number of good sequences of length $n$ is $$T_n=2^n-(n+1)$$

Now, using this, we can work out recursions that it satisfies. For instance, $$T_n=2T_{n-1}+n-1$$ works.

If one wants a recursion of the form $T_n=\sum_{i=1}^k\lambda_iT_{n-k}$, that's available as well though it appears to be less than intuitive. Guessing that $k=3$ will suffice we simply match terms and solve the resulting linear system to deduce that $$T_n=4T_{n-1}-5T_{n-2}+2T_{n-3}$$

Off hand, I do not see a sensible combinatorial way to spot the recursion directly (though of course there might be one).


You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .