Thread: Three Part Recurrence Relation Problem

1. Three Part Recurrence Relation Problem

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

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

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

So far, this is what I have.

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

(b)
???

(c)
I know
$\displaystyle f_{1} = 1, f_{2} = 1, f_{3} = 2, f_{4} = 3, f_{5} = 5, ...$
and that matches up with
$\displaystyle b_{1} = 2, b_{2} = 3, b_{3} = 5, ...$
So,
$\displaystyle f_{3} = b_{1}$
$\displaystyle f_{4} = b_{2}$
$\displaystyle 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 $\displaystyle b_{n}$, the number of binary sequences of length n that do not contain 11.

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

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

So far, this is what I have.

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

Create a subset of $\displaystyle \{1, 2, 3, ..., n\}$ corresponding to this string by including in it the integer $\displaystyle i$ if $\displaystyle s_i=1$ and excluding it if $\displaystyle s_i=0$.
Thus the number of subsets that do not contain consecutive integers $\displaystyle i$ and $\displaystyle i+1$ and the number of strings that do not contain the sequence $\displaystyle 11$ are therefore equal.
(c)
I know
$\displaystyle f_{1} = 1, f_{2} = 1, f_{3} = 2, f_{4} = 3, f_{5} = 5, ...$
and that matches up with
$\displaystyle b_{1} = 2, b_{2} = 3, b_{3} = 5, ...$
So,
$\displaystyle f_{3} = b_{1}$
$\displaystyle f_{4} = b_{2}$
$\displaystyle 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 $\displaystyle k,\; k+1$, $\displaystyle b_k = f_{k+2}$ and $\displaystyle b_{k+1} = f_{k+3}$. Then, using the relation that defines a Fibonacci sequence,
$\displaystyle f_{k+4}= f_{k+3}+ f_{k+2}$
$\displaystyle =b_{k+1}+b_k$

$\displaystyle =b_{k+2}$, using the answer to (a)
Clearly $\displaystyle b_0 = f_2$ and $\displaystyle 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 $\displaystyle b_0$ you have 1 set, namely the empty set.
For $\displaystyle b_1$ you have 2 sets, $\displaystyle {0,1}$.
For $\displaystyle b_2$ you have 3 sets, $\displaystyle {00, 01, 10}$.
For $\displaystyle b_3$ you have 5 sets, $\displaystyle {000, 001, 010, 100, 101}$.
And so on. The way it becomes a recurrence was by, for example set $\displaystyle b_3$
You first take $\displaystyle b_2 = {00, 01, 10}$ and put a 0 in front of those sets, thus giving you $\displaystyle {000, 001, 010}$
Then take $\displaystyle b_1 = {0, 1}$ and put a 10 in front of those sets, thus giving you $\displaystyle {100, 101}$
Which gives you the union of $\displaystyle b_1, b_2 = b_3$
Therefore $\displaystyle 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 $\displaystyle b_0$ you have 1 set, namely the empty set.
For $\displaystyle b_1$ you have 2 sets, $\displaystyle {0,1}$.
For $\displaystyle b_2$ you have 3 sets, $\displaystyle {00, 01, 10}$.
For $\displaystyle b_3$ you have 5 sets, $\displaystyle {000, 001, 010, 100, 101}$.
And so on. The way it becomes a recurrence was by, for example set $\displaystyle b_3$
You first take $\displaystyle b_2 = {00, 01, 10}$ and put a 0 in front of those sets, thus giving you $\displaystyle {000, 001, 010}$
Then take $\displaystyle b_1 = {0, 1}$ and put a 10 in front of those sets, thus giving you $\displaystyle {100, 101}$
Which gives you the union of $\displaystyle b_1, b_2 = b_3$
Therefore $\displaystyle 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 $\displaystyle (n-1)$ a zero may be added at the end to form a valid string of length $\displaystyle n$. Moreover, for every string of length $\displaystyle n$ that ends in zero, the last character may be removed to form a valid string of length $\displaystyle (n-1)$.

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

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

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