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 Cancel reply

Spam prevention powered by Akismet