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?

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.

Grandad