From DojoWiki

February 28th Meeting

For the February meeting, we'll be working on Dave Thomas' Kata Fifteen.

http://codekata.pragprog.com/2007/01/code_kata_fifte.html

This will be a nice break from the "Theory" we've been focusing on.

Detail

---

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, for three-digit numbers, five of the possible eight combinations meet the criteria: 000, 001, 010, 011, 100, 101, 110, 111. 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 that relationship exists?

Answer..

A fibonacci sequence.

For example.. 2^3 = 3 values with non-adjacent 1 bits; 2^4 = 5; 2^5 = 8; etc...