# Recurrence relation and the Fibonacci

Prove that $b_n = f_{n+2}$ where $f_n$ is the Fibonacci number.

$b_n$ is defined as the number of binary sequences of length $n$ that do not contain 11.

Which I observed as $b_n = b_{n-1} + b_{n-2}.$

$b_0 = 1, b_1 = 2, b_2=3.$

Attempt: I thought the best way to prove this was to use induction; the base case was easy to prove. I assumed $n=k$ and am working to prove $b_{k+1} = f_{k+3}$.

However, I noticed that I am often hesitant to use the property $(b_{k+1} = b_{k} + b_{k-1})$ of recurrence relations, mainly because we can't assume $b_{k-1} = f_{k+1}$.

So, is induction the right approach to this question? How should I approach to prove this?

• Fourth row describes those several numbers that do not contain 11 in their binary representation; $b_0 = 1, b_1 = 2, b_2 = 3$ and so on Nov 22 '16 at 19:03
• I am sorry, I misunderstood your question. I got it now.
– RGS
Nov 22 '16 at 19:05
• your question is the exercise 2.15 of the book a first course in discrete mathematics by ian anderson. There is an useful key answer at the end of the book!. Nov 28 '16 at 7:08

You can use a "different" type of induction, strong induction, in which your inductive step is a bit different. Instead of assuming that your preposition holds for $k$ and proving it works for $k+1$ as well, you assume it works for any $i$ up until $k$, and then prove it for $k+1$.

That is, assuming

$$b_i = f_{i+2} \forall_i \leq k$$

Prove that

$$b_{k+1} = f_{k+3}$$

A more crucial step of your proof would be to prove that $b_n = b_{n-1} + b_{n-2}$ because that is where the hard part of the question is. $b_{n} = f_{n+2}$ would follow trivially.

• So using the "strong" induction enables me to use the property of recurrence relations? Nov 22 '16 at 19:00
• @Corp.andLtd. exactly. That will let you assume $b_{k-1} = f_{k+1}$
– RGS
Nov 22 '16 at 19:02
• @Corp.andLtd. i edited my answer to include a little thought of mine that might be relevant. Have a good day
– RGS
Nov 22 '16 at 19:12

$$b_n=b_{n-1}+b_{n-2}$$,

the characteristic equation is

$$x^2-x-1=0$$ has two roots $g_1$ and $g_2$.

thus

$$b_n=Ag_1^n+Bg_2^n$$

$$F_n=Cg_1^n+Dg_2^n$$

with $$b_0=A+B=1=F_2$$

$$b_1=Ag_1+Bg_2=2=F_3$$

and $$b_n=F_{n+2}$$ for $n\geq 0$.