# 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!

# Mathematical Aside: Golden Mean Shift and Pascal’s Triangle

I noticed something curious when I was working on my summer project last year. Basically, you consider the set $c_n$ of binary strings (strings of length $n$ where each symbol is either a $1$ or a $0$ and $1$‘s are non-adjacent).  So we construct a table like

 Length 1 2 3 4 5 6 Strings 0;1 00;01;10 000;001;010;100;101 0000;0001;0010;0100;0101;1000;1001;1010 … …

And then count the number of elements of length $n$ with $m$ ones.

 Number of ones [m] (below) Number of strings (below) Length of string [n] (right) 1 2 3 4 5 6 0 1 1 1 1 1 1 1 1 2 3 4 5 6 2 0 0 1 3 6 10 3 0 0 1 4 4 0 0

Do you see Pascal’s Triangle hiding inside? Starting from the top left and diagonally down to the left. First one is 1,2,1, then is 1,3,3,1 etc The explanation is simple enough. We are using the fact that the subset of $c_n$ composed of strings with $m$ ones (lets call this $c_{n,m}$) can be made by taking an element in $c_{n-1,m}$ and appending a zero to it or an element in $c_{n-2,m-1}$ and appending a zero-one to it. We end up with the recurrence $c_{n,m}= c_{n-1,m}+ c_{n-2,m-1}$. If we consider $d_{n,m}$ as the $n^{th}$ element in the $m^{th}$ diagonal, then we realize that $d_{n.m}$ follows the same recurrence. This reccurence is well documented in the literature for calculating $|c_n|$, here we are just using this idea for subsets of $c_n$ with exactly $m$ ones to connect it with Pascal’s Triangle.

The adventure continues in Part 2!