# Cardinality of set of length-$n$ binary vectors without adjacent zeroes

Let $T_n$ be the set

$$T_n = \left\{(a_1,\dots,a_n) \in \{0,1\}^n \middle\vert \text{ no two 0s can appear in two adjacent components}\right\}.$$

Let $t_n = \#T_n$ be the cardinality of $T_n$.

How would I go about finding $t_1, t_2, t_3$, and their their relationship to each other?

-
There isn't really anything to do other than write down what T1, T2, and T3 are. What exactly are you stuck on? Also, is this homework? If so you should add the "homework" tag to your question. –  Zev Chonoles Apr 11 '11 at 0:17
I agree with Zev. What have you tried so far? For example, what problem are having with finding the cardinality of $T1$? Also, for future reference, please do not post in the imperative mode. Please word your post as a question. –  JavaMan Apr 11 '11 at 0:26
Why did you edit your question to gibberish? –  Zev Chonoles Apr 11 '11 at 0:41
Can you please explain your answer. I do not understand how t1= 2? Shouldn't it equal 1. –  user9422 Apr 11 '11 at 0:49
$T_1=\{(0),(1)\}$. –  GWu Apr 11 '11 at 1:28

Hint: If you let $T0(n)$ be the number of strings of length $n$ ending in $0$ without two $0$'s in a row, and $T1(n)$ the number of strings of length $n$ ending in $1$ without two $0$'s in a row, then $tn=T0(n)+T1(n)$ and you can find recurrences $T1(n+1)=T1(n)+T0(n)$ because you can add a $1$ to any string and $T0(n+1)=T1(n)$ because you can only add a zero to a string ending in $1$. Coupled with $T0(1)=T1(1)=1$ you should be there.
From $T1(n+1)=T1(n)+T0(n)$ we have $T1(n+1)=T_n$. Add this to $T0(n+1)=T1(n)$ we have $T_{n+1}=T_n+T1(n)$. But $T1(n)=T_{n-1}$. Hence $$T_{n+1}=T_n+T_{n-1}\qquad T_1=2$$. –  user9077 Apr 11 '11 at 4:51
$T_1=\{(a_1)\in \{0,1\}|...\}$ and $t_1=2$.
$T_2=\{(0,1),(1,0),(1,1)\}$ and $t_2=3$.
This must be a homework problem, so I'll leave $t_3$ to you :)