1
$\begingroup$

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?

  • 1
    There isn't really anything to do other than write down what T1, T2, and T3 are. What exactly are you stuck on?2011-04-11
  • 1
    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.2011-04-11
  • 0
    Can you please explain your answer. I do not understand how t1= 2? Shouldn't it equal 1.2011-04-11
  • 0
    $T_1=\{(0),(1)\}$.2011-04-11

2 Answers 2

2

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.

  • 0
    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$$.2011-04-11
1

$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 :)