As was derived in Part 2, where denotes the set of binary strings of length with exactly non-adjacent ones.

Today we will analyze the set of binary strings of length with any number of non-adjacent ones. We will need some additional notation.

- denote the the subset of ending with 0
- denote the the subset of ending with 1

After some thought, we realize that and . We can then derive the recurrence . After verifying the base case, we can conclude , the Fibonacci Numbers!

Another way to compute is .

Therefore .

With some shifting, we can solve for the Fibonnaci number :

While this formula can be quite easily verified inductively, its nice to construct it explicitly.