Problem 26 Section 5.1

Recall that we set t_n to be the number of ternary strings of length n which do contain 00 or 11. We were trying to develop a recurrence relation for the sequence t_n.

It turns out that the book's answer was right (thus mine wrong) and thanks to Mr. Kenworthy for indicating the problem in class. My apologies to everyone but you will see that the ideas we discussed are all sound there was a little slip at the end.

The expression we are after is

t_n = 2*t_(n-1) + t_(n-2) + 2*3^(n-2)

As I indicated and as we learned in combinatorial proofs, we do not want to really think of these t_n's but rather the sets whose size they represent. Thus in the above expression, t_(n-1) and t_(n-2) should somehow be the collection of ternary strings of length n-1 and n-2 respectively which do contain 00 and 11. Similarly it is natural to remember that 3^(n-2) is the size of the collection of all ternary strings of length n-2. Let us see if we can establish the recurrence relation with these identifications.

To be more formal than I was in class: Let us let T_k denote the actual set of ternary strings of length k which contain either 00 or 11. To prove the above identity, we will divide T_n into several sets (disjoint naturally) and determine the size of these sets.

Let A denote the subset of T_n consisting of those that start with a 2.

Let B denote the subset of T_n consisting of those that start with either 00 or 11.

Let C denote the subset of T_n consisting of those that start with either 02 or 12.

Finally let D denote the subset of T_n consisting of those that start with 01 or 10.

We first check that this collection of subsets of T_n has the property that every member of T_n is in precisely one of them, i.e. they form a partition of T_n.

Now we just want to compute the size of each of them and hope that the above recurrence relation results. Actually this is the cart before the horse. If we can find a nice formula involving only t_(n-1),t_(n-2) etc for the sizes of each of A,B,C,D then we have a recurrence relation. I only gave the answer first to guide us in how to think about the problem. The above partition is also the cart before the horse. We just try to think of nice ways to get all members of T_n by doing something natural to shorter strings in such a way that we can count the sizes.

What is in A? Think about this how best you can: there is a 1-1 correspondence between the members of A (i.e. those members of T_n that start with a 2) and the entire collection T_(n-1). This correspondence is simply REMOVE 2 from the front of the string. Therefore A has the same size as T_(n-1), i.e. size t_(n-1) by the definition of t_(n-1).

Now turn to B. If we take any string of length n-2 and stick either 00 or 11 in front of it, we get a member of B. Therefore B is the disjoint union of those that start with 00 and those that start with 11 and both of these obviously have size 3^(n-2) since each can be put in 1-1 correspondence with the collectioin of ALL ternary strings of length n-2. Thus B has size 2*3^(n-2).

What about C. We also partition C into 2 sets, those that start out 02 and those that start out 12. Each of these subsets can be put in 1-1 correspondence (just by removing the first two digits) with T_(n-2). Why? Well a string that starts out 02 for example and is in T_n must have either 00 or 11 occuring from position 3 or later, therefore the removal of 02 results in a member of T_(n-2). Also conversely, take any member of T_(n-2) and stick 02 at the front and we end up with a member of T_n, hence C. This verifies the correspondence and the fact that C has size 2*t_(n-2).

Finally we come to the tricky one: D. I had the right idea in class but I just stupidly started thinking about bit strings instead of ternary strings.

Anyway, D consists of those that start out 01 or 10 and we want to count them. As we said if we take a string starting out with 01 and then having n-2 more terms we obviously cannot assume that the remaining n-2 terms contain a 00 or a 11 since we could have a string like 0112222222.
I said let's take any string from T_(n-1) and if it starts with a 1 put a 0 in front (to get a string starting with 01) whereas if it starts with a 0 put a 1 in front (to get a string starting with 10). Whoops, what if it starts with a 2? Well these were already counted in our 02 and 12 set C so we can't count them again. But, we know how many there are! So just take those members of T_(n-1) that start with either a 0 or a 1, for each one of these stick the opposite bit at the front. In this way we can see we get a 1-1 correspondence between the members of T_n which start out with either 10 or 01.
Fortunately, it is easy to count how many members of T_(n-1) start with either a 0 or a 1. Just count those that start with a 2!. By our argument for the set C we already know there are t_(n-2) that start with a 2. Thus there are t_(n-1) - t_(n-2) that start with a 0 or a 1. This then is the size of D.

Finally we get t_n = |T_n| = |A| + |B| + |C| + |D| = t_(n-1) + 2*3^(n-2) + 2*t_(n-2) + (t_(n-1) - t_(n-2) ). Hooray.