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?

  • $\begingroup$ 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 $\endgroup$ Nov 22 '16 at 19:03
  • $\begingroup$ I am sorry, I misunderstood your question. I got it now. $\endgroup$
    – RGS
    Nov 22 '16 at 19:05
  • $\begingroup$ 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!. $\endgroup$
    – Amin235
    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.

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

Starting by your recursive relation


the characteristic equation is

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




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


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


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.