Because experience
is the only teacher

Kata15: A Diversion

Think of binary numbers: sequences of 0’s and 1’s. How many n-digit binary numbers are there that don’t have two adjacent 1 bits? For example, here are the three-digit numbers:

000 001 010 011 100 101 110 111

Five of the possible eight combinations meet the criteria

What is the number for sequences of length 4, 5, 10, n?

Having worked out the pattern, there’s a second part to the question: can you prove why the relationship exists?