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.