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.