- #1

issacnewton

- 1,024

- 35

- Homework Statement
- Prove that the number of ##n## digit binary numbers that have no consecutive 1's is the Fibonacci number ##F_{n+2}##. For example, for ##n=2## there are three such numbers ##(00, 01, 10)##, and ##3 = F_{2+2} = F_4##. Also, for ##n=3## there are five such numbers ##(000, 001, 010, 100, 101)##, and ##5 = F_{3+2} = F_5##.

- Relevant Equations
- Mathematical Induction and Fibonacci sequence.

I have already shown base case above for ##n=2##. Let ##k \geq 2## be some arbitrary in ##\mathbb{N}##. Suppose the statement is true for ##k##. So, this means that, number of k-digit binary numbers that have no consecutive 1's is the Fibonacci number ##F_{k+2}##. And I have to prove that number of (k+1)-digit binary numbers that have no consecutive 1's is the Fibonacci number ##F_{k+3}##. Actually, I have no clue where to start on this after the base case. I need help. This problem could have easier solution using combinatorics but I need to use induction here.

Thanks

Thanks