0

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.

Nikolai Savulkin
  • 187
  • 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$. – lulu Dec 11 '21 at 22:30
  • @lulu yes, that what is implied – Nikolai Savulkin Dec 11 '21 at 22:31
  • 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$. – lulu Dec 11 '21 at 22:31
  • 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 – Nikolai Savulkin Dec 11 '21 at 22:34
  • 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. – lulu Dec 11 '21 at 22:37
  • But it defines $T_n$ in terms of n, while in the assigment $T_n$ should be defined by $Q \in { T_z | z < n }$ – Nikolai Savulkin Dec 11 '21 at 22:39
  • Unless I'm blind and don't see how that relation can be expressed recursively, in which case I apologize. – Nikolai Savulkin Dec 11 '21 at 22:40
  • Again, I am not sure what you want. The count is straight forward, but the associated recursions contain an $n$ term (which I don't see as a problem, but which you might): $T_n=2T_{n-1}+n-1$ works. The relevant sequence is A000295. That link contains many equivalent definitions and formulas, though no recursion without an $n$ term. – lulu Dec 12 '21 at 00:02
  • Are constant terms ok? That's doable. $T_n=3T_{n-1}-2T_{n-2}+1$ works, for example. – lulu Dec 12 '21 at 00:10
  • Or, if you insist, $T_n=4T_{n-1}-5T_{n-2}+2T_{n-3}$ does the job. Again, that's reverse engineered from the obvious closed form solution. Maybe there's a sensible combinatorial way to spot that from the start but nothing jumps out at me. – lulu Dec 12 '21 at 00:16

1 Answers1

2

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).

lulu
  • 70,402