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?