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?

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