Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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|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? 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

2 Answers 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.

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

Your Answer


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