Can you Prove it... combinatorially?

This year’s Prove it! Math Academy was a big success, and it was an enormous pleasure to teach the seventeen talented high school students that attended this year. Some of the students mentioned that they felt even more inspired to study math further after our two-week program, but the inspiration went both ways - they inspired me with new ideas as well!

One of the many, many things we investigated at the camp was the Fibonacci sequence, formed by starting with the two numbers $0$ and $1$ and then at each step, adding the previous two numbers to form the next: \[0,1,1,2,3,5,8,13,21,\ldots\] If $F_n$ denotes the $(n+1)$st term of this sequence (where $F_0=0$ and $F_1=1$), then there is a remarkable formula for the $n$th term, known as Binet’s Formula:

\[F_n=\frac{1}{\sqrt{5}}\left( \left(\frac{1+\sqrt{5}}{2}\right)^n - \left(\frac{1-\sqrt{5}}{2}\right)^n \right)\]

Looks crazy, right? Why would there be $\sqrt 5$’s showing up in a sequence of integers?

At Prove it!, we first derived the formula using generating functions. I mentioned during class that it can also be proven by induction, and later, one of our students was trying to work out the induction proof on a white board outside the classroom. She was amazed how many different proofs there could be of the same fact, and it got me thinking: what if we expand each of the terms using the binomial theorem? Is there a combinatorial proof of the resulting identity?

In particular, suppose we use the binomial theorem to expand $(1+\sqrt{5})^n$ and $(1-\sqrt{5})^n$ in Binet’s formula. The resulting expression is:

\[F_n=\frac{1}{\sqrt{5}\cdot 2^n}\left( \left(\sum_{i=0}^n {n \choose i}(\sqrt{5})^i \right) - \left(\sum_{i=0}^n (-1)^i{n \choose i}(\sqrt{5})^i \right) \right)\]

Note that the even terms in the two summations cancel, and combining the odd terms gives us:

\[F_n=\frac{1}{\sqrt{5}\cdot 2^n}\left( \sum_{k=0}^{\lfloor n/2\rfloor} 2 {n\choose {2k+1}}(\sqrt{5})^{2k+1} \right)\] Since $(\sqrt{5})^{2k+1}=\sqrt{5}\cdot 5^k$, we can cancel the factors of $\sqrt{5}$ and multiply both sides by $2^{n-1}$ to obtain:

\[2^{n-1}\cdot F_n=\sum_{k=0}^{\lfloor n/2\rfloor} \binom{n}{2k+1}\cdot 5^k.\]

Now, the left hand and right hand side are clearly nonnegative integers, and one handy fact about nonnegative integers is that they count the number of elements in some collection. The proof method of counting in two ways is the simple principle that if by some method one can show that a collection $A$ has $n$ elements, and by another method one can show that $A$ has $m$ elements, then it follows that $m=n$. Such a ``combinatorial proof’’ may be able to be used to prove the identity above, with $m$ being the left hand side of the equation and $n$ being the right.

I started thinking about this after Prove it! ended, and remembered that the $(n+1)$st Fibonacci number $F_n$ counts the number of ways to color a row of $n-2$ fenceposts either black or white such that no two adjacent ones are black. (Can you see why this combinatorial construction would satisfy the Fibonacci recurrence?) For instance, we have $F_5=5$, because there are five such colorings of a row of $3$ fenceposts: \[\begin{array}{ccc} \square & \square & \square \\ \\ \square & \square & \blacksquare \\ \\ \square & \blacksquare & \square \\ \\ \blacksquare & \square & \square \\ \\ \blacksquare & \square & \blacksquare \end{array}\]

Note also that $2^{n-1}$ counts the number of length-$(n-1)$ sequences of $0$’s and $1$’s. Thus, the left hand side of our identity, $2^{n-1}\cdot F_n$, counts the number of ways of choosing a binary sequence of length $n-1$ and also a fence post coloring of length $n-2$. Because of their lengths, given such a pair we can interlace their entries, forming an alternating sequence of digits and fence posts such as: \[1\, \square\, 0\, \square\, 1\, \blacksquare\, 1\] We will call such sequences interlaced sequences.

We now need only to show that the right hand side also counts these interlaced sequences. See the next page for my solution, or post your own solution in the comments below!

We wish to show that $\sum_{k} {n\choose {2k+1}}\cdot 5^k$ counts the number of interlaced sequences, consisting of a length $n-1$ binary sequence and a length $n-2$ coloring of fence posts such that no two black posts are adjacent. To do so, we first can make the expression a bit nicer, and more relevant to length-$(n-1)$ sequences, by expanding ${n}{2k+1}$ as ${ {n-1}\choose {2k}} +{ {n-1}\choose {2k+1}}$ by the Pascal recurrence. The sum then becomes \[\sum_{k} { {n-1}\choose {2k}}\cdot 5^k+{ {n-1}\choose {2k+1}} \cdot 5^k=\sum_{m} { {n-1}\choose {m}} \cdot 5^{\lfloor m/2 \rfloor}.\]

Notice that this can be thought of as a sum of exactly $2^{n-1}$ powers of $5$, where the power $5^{\lfloor m/2 \rfloor}$ occurs exactly ${n-1}{m}$ times in the sum for all $m\ge 0$. It therefore suffices to sort the interlaced sequences into $2^{n-1}$ disjoint collections such that exactly ${ {n-1}\choose m}$ of them have size $5^{\lfloor m/2\rfloor}$ for each $m$.

Let a white sequence be an interlaced sequence such that all the fence posts are colored white, such as: \[1 \square \, 0 \, \square \, 1\, \square \, 1\, \square \, 1\] Given a white sequence $S$, let $m$ be the number of $1$’s in its binary sequence. We say another interlaced sequence $T$ is a buddy of $S$ if it can be formed by pairing off the $1$’s in $S$ starting from the left to form $\lfloor m/2 \rfloor$ pairs, and then for each pair, consider the fence post $p$ just before the right hand $1$ of the pair and perform one of the following operations:

Keep $p$ white
Color $p$ black and change the adjacent digits on the left and right of $p$ to $0$ and $0$
Color $p$ black and change the adjacent digits on the left and right of $p$ to $0$ and $1$
Color $p$ black and change the adjacent digits on the left and right of $p$ to $1$ and $0$
Color $p$ black and change the adjacent digits on the left and right of $p$ to $1$ and $1$

For instance, the following is a buddy of the white sequence above, by using option 4 on the first pair of $1$’s and option 2 on the second:

\[1 \, \square \, 1 \, \blacksquare \, 0 \, \square \, 0\, \blacksquare\, 0 \]

Notice that the black fence posts formed in this way must be separated by at least one white fence post, since each is between some consecutive (though not necessarily adjacent) pair of $1$’s. Thus all buddies of a white sequence are valid interlaced sequences.

Since there are $5$ possibilities above for each pair of $1$’s in $S$, there are $5^{\lfloor m/2 \rfloor}$ buddies of $S$. Additionally, given any interlaced sequence $T$, there is a unique white sequence $S$ that it is buddies with, constructed as follows: Consider the black fence posts $p$ of $T$ and, from left to right, change $p$ to white and make the digit to the the right of $p$ be $1$ and change the digit on the left so as to make the parity of the $1$’s up to that point odd. Finally, note that no two white sequences are buddies with each other.

It follows that the buddies relation sorts the interlaced sequences into subcollections of $5^{\lfloor m/2 \rfloor}$ collections each, where $m$ is the number of $1$’s in the unique white sequence in the subcollection. Since there are exactly ${n-1}{m}$ white sequences having exactly $m$ $1$’s, the result follows.