1
$\begingroup$

I am just unsure if I did this question right and would just like to check.

Question: A bit-string is simply a finite sequence of zeroes and ones. For the purposes of this problem, strings will always have length $\ge 1$, i.e. no zero-length strings.

Let $A_n$ be the number of strings of length $n$ that have no two consecutive zeros. Thus $A_1=2$ and $A_2=3$ (strings $01$, $10$ and $11$).

Give recursive definitions for $A_n$.

My Answer(s): $$A(n+1) = A(n)+A(n-1),$$ $$A(n) = A(n-1)+A(n-2).$$

$\endgroup$
1
  • $\begingroup$ Your recurrence is correct, though a complete answer would explain the reasoning behind it. $\endgroup$ Commented Feb 4, 2015 at 19:38

1 Answer 1

Reset to default
1
$\begingroup$

Seems true. I assume $A_n$ to be the actual sets not just their respective size. $A_{n+2}$ equals the disjoint union of the set $X$ of sequences ending in $1$ and the set $Y$ of sequences ending in $10$. $A_{n+1}$ maps bijectively on $X$ via $(x_1,\ldots,x_{n+1})\mapsto(x_1,\ldots,x_{n+1},1)$ and $A_{n}$ on $Y$ via $(x_1,\ldots,x_n)\mapsto(x_1,\ldots,x_n,1,0)$.

$\endgroup$

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.