Monthly Archives: November 2017

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.

 

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

As we discussed in Part 1, we noticed a common pattern in the the m^{th} element in the n^{th} diagonal, d_{m,n},  of Pascal’s Triangle and the function c_{m,n}, denoting the set of binary strings of length n with exactly m non-adjacent ones. Today we derive an explicit formula for c_{m,n} in two ways.

Firstly, some more notation. The element in r^{th} row and k^{th} column in Pascal’s Triangle is denoted by {r}\choose{k}. Then we can see d_{m,n} = {n+m-1,m}. Unfortunately, c_{m,n} is at a slight shift. To see this, we think about how long the string needs to be just so can fit in m ones. The answer is 2(m-1). While the d_{m,n} is non-zero straight away, it takes c_{m,n} 2(m-1) increments to the length before it is non-zero. Therefore, |c_{m,n}|=d_{m,n-2(m-1)}= {n-(m-1)}\choose{m}.

Another way to see this requires knowledge of combinations.  If we consider the unconstrained system, the clearly we have u_{m,n} {n}\choose{m} options. We can construct a bijection from u_{m,n-(m-1)} to c_{m,n} as follows:

  • For every element in u_{m,n-(m-1)}, we can add append a 0 to all but the rightmost 1 and construct a unique element in c_{m,n}
  • For every element in c_{m,n}, we can add delete a 0 from the right side of all but the rightmost 1 and construct a unique element in u_{m,n-(m-1)}

Thus |c_{m,n}| = |u_{m,n-(m-1)}|= {n-(m-1)}\choose{m} as required.

We will use this to find an intriguing connection to the Fibonacci numbers in Part 3!