Provide a formula for number of binary sequences of length n that have no consecutive 0's.
Let f(n) be the number of ndigit sequences with no 2 consecutive 0's. There are 2 1digit sequences with no consecutive 0's. They are 0 and 1. Therefore, f(1)=2. There are 3 2digit sequences with no consecutive 0's. They are 01, 10, and 11. Therefore, f(2)=3. Take any n>3. If an ndigit sequence starts with 1, then any n1digit sequence with no consecutive 0's can be the last n1 digits. If an ndigit sequence starts with 0, then the next digit must be 1 to avoid 2 consecutive 0's. Then, any n2digit sequence with no consecutive 0's can be the last n2 digits. Therefore, f(n)=f(n1)+f(n2). Then, f(n)=Fibonacci(n+2).
Edited on October 6, 2018, 9:09 am

Posted by Math Man
on 20181006 09:03:20 