Thread: Three Part Recurrence Relation Problem

1. Three Part Recurrence Relation Problem

(a) Find a recurrence relation and initial conditions for $b_{n}$, the number of binary sequences of length n that do not contain 11.

(b) Explain why the number of subsets of ${1, 2, ..., n}$ that do not contain both $i$ and $i + 1$ for $i = 1, 2, ..., n-1$ equals $b_{n}$. (Hint: appeal to a known 1-1 correspondence.)

(c) Prove that $b_{n} = f_{n+2}$, where $f_{n}$ is the n-th Fibonacci number, defined by $f_{1} = f_{2} = 1$, and $f_{n} = f_{n-1} + f_{n-2}$ for $n > 2$. (One method that works is strong induction.)

So far, this is what I have.

(a)
$b_{n} = b_{n-1} + b_{n-2}$ for $n \ge 2$
with $b_{0} = 1$ and $b_{1} = 2$

(b)
???

(c)
I know
$f_{1} = 1, f_{2} = 1, f_{3} = 2, f_{4} = 3, f_{5} = 5, ...$
and that matches up with
$b_{1} = 2, b_{2} = 3, b_{3} = 5, ...$
So,
$f_{3} = b_{1}$
$f_{4} = b_{2}$
$f_{5} = b_{3}$
and so on, not sure what to do next.

2. Hello Celcius

Welcome to Math Help Forum!
Originally Posted by Celcius
(a) Find a recurrence relation and initial conditions for $b_{n}$, the number of binary sequences of length n that do not contain 11.

(b) Explain why the number of subsets of ${1, 2, ..., n}$ that do not contain both $i$ and $i + 1$ for $i = 1, 2, ..., n-1$ equals $b_{n}$. (Hint: appeal to a known 1-1 correspondence.)

(c) Prove that $b_{n} = f_{n+2}$, where $f_{n}$ is the n-th Fibonacci number, defined by $f_{1} = f_{2} = 1$, and $f_{n} = f_{n-1} + f_{n-2}$ for $n > 2$. (One method that works is strong induction.)

So far, this is what I have.

(a)
$b_{n} = b_{n-1} + b_{n-2}$ for $n \ge 2$
with $b_{0} = 1$ and $b_{1} = 2$
Would you like to explain why?
(b)
???
The number of subsets is $2^n$ = the number of binary strings of length $n$. And we may set up a 1-1 correspondence between subsets and strings as follows:
Choose any binary string of length $n$, say $s_1s_2s_3...s_n$.

Create a subset of $\{1, 2, 3, ..., n\}$ corresponding to this string by including in it the integer $i$ if $s_i=1$ and excluding it if $s_i=0$.
Thus the number of subsets that do not contain consecutive integers $i$ and $i+1$ and the number of strings that do not contain the sequence $11$ are therefore equal.
(c)
I know
$f_{1} = 1, f_{2} = 1, f_{3} = 2, f_{4} = 3, f_{5} = 5, ...$
and that matches up with
$b_{1} = 2, b_{2} = 3, b_{3} = 5, ...$
So,
$f_{3} = b_{1}$
$f_{4} = b_{2}$
$f_{5} = b_{3}$
and so on, not sure what to do next.
If your answer to part (a) is correct, then this result follows immediately by induction.

Assume that, for two consecutive integers $k,\; k+1$, $b_k = f_{k+2}$ and $b_{k+1} = f_{k+3}$. Then, using the relation that defines a Fibonacci sequence,
$f_{k+4}= f_{k+3}+ f_{k+2}$
$=b_{k+1}+b_k$

$=b_{k+2}$, using the answer to (a)
Clearly $b_0 = f_2$ and $b_1 = f_3$ and that completes the proof.

3. Yes, for (a)
I came up with those numbers first by counting a couple then creating the relation

For $b_0$ you have 1 set, namely the empty set.
For $b_1$ you have 2 sets, ${0,1}$.
For $b_2$ you have 3 sets, ${00, 01, 10}$.
For $b_3$ you have 5 sets, ${000, 001, 010, 100, 101}$.
And so on. The way it becomes a recurrence was by, for example set $b_3$
You first take $b_2 = {00, 01, 10}$ and put a 0 in front of those sets, thus giving you ${000, 001, 010}$
Then take $b_1 = {0, 1}$ and put a 10 in front of those sets, thus giving you ${100, 101}$
Which gives you the union of $b_1, b_2 = b_3$
Therefore $b_3 = {000, 001, 010, 100, 101}$.
And thus the recurrence is formed.

4. Hello Celcius
Originally Posted by Celcius
Yes, for (a)
I came up with those numbers first by counting a couple then creating the relation

For $b_0$ you have 1 set, namely the empty set.
For $b_1$ you have 2 sets, ${0,1}$.
For $b_2$ you have 3 sets, ${00, 01, 10}$.
For $b_3$ you have 5 sets, ${000, 001, 010, 100, 101}$.
And so on. The way it becomes a recurrence was by, for example set $b_3$
You first take $b_2 = {00, 01, 10}$ and put a 0 in front of those sets, thus giving you ${000, 001, 010}$
Then take $b_1 = {0, 1}$ and put a 10 in front of those sets, thus giving you ${100, 101}$
Which gives you the union of $b_1, b_2 = b_3$
Therefore $b_3 = {000, 001, 010, 100, 101}$.
And thus the recurrence is formed.
A more formal proof of this is as follows:

Suppose we call a string that doesn't contain the string '11' a valid string. Then to every valid string of length $(n-1)$ a zero may be added at the end to form a valid string of length $n$. Moreover, for every string of length $n$ that ends in zero, the last character may be removed to form a valid string of length $(n-1)$.

Therefore the number of valid strings of length $n$ that end in zero is exactly $b_{n-1}$.

Similarly, the number of valid strings of length $(n-1)$ that end in zero is $b_{n-2}$. Further for each of these strings, a '1' may be added to the end to form a valid string of length $n$.

Therefore the number of valid strings of length $n$ is $b_{n-1}+b_{n-2}$.