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 .
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.