Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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?

share|cite|improve this question
There isn't really anything to do other than write down what T1, T2, and T3 are. What exactly are you stuck on? – 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
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.

share|cite|improve this answer
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 :)

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.