Recurrence relation and the Fibonacci

Question

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?

Answer 1

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.

Answer 2

Starting by your recursive relation

$$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$.