Mathematical Aside: Golden Mean Shift and Pascal’s Triangle (Part 3)

As was derived in Part 2, |c_{m,n}|= {n-(m-1)}\choose{m} where c_{m,n} denotes the set of binary strings of length n with exactly m non-adjacent ones.

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

  • c_{n,0} denote the the subset of c_{n} ending with 0
  • c_{n,1} denote the the subset of c_{n} ending with 1

After some thought, we realize that c_{n,0} =c_{n-1} and c_{n-2}. We can then derive the recurrence |c_{n}| = |c_{n,0}|+|c_{n,1}|=|c_{n-1}|+|c_{n-2}|. After verifying the base case, we can conclude |c_{n}| = F_{n+2}, the Fibonacci Numbers!

Another way to compute |c_{n}| is |c_{n}| = \sum_{m=0}^{\infty} {n-(m-1)}\choose{m}.

Therefore F_{n+2} = \sum_{m=0}^{\infty} {n-(m-1)}\choose{m}.

With some shifting, we can solve for the n^{th} Fibonnaci number :

F_{n} = \sum_{m=0}^{\infty} {n-m-1}\choose{m}

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


Leave a Reply

Your email address will not be published. Required fields are marked *