# Can you Prove it… combinatorially?

We wish to show that $\sum_{k} \binom{n}{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 $\binom{n}{2k+1}$ as $\binom{n-1}{2k}+\binom{n-1}{2k+1}$ by the Pascal recurrence. The sum then becomes $$\sum_{k} \binom{n-1}{2k}\cdot 5^k+\binom{n-1}{2k+1} \cdot 5^k=\sum_{m} \binom{n-1}{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 $\binom{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 $\binom{n-1}{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:

1. Keep $p$ white
2. Color $p$ black and change the adjacent digits on the left and right of $p$ to $0$ and $0$
3. Color $p$ black and change the adjacent digits on the left and right of $p$ to $0$ and $1$
4. Color $p$ black and change the adjacent digits on the left and right of $p$ to $1$ and $0$
5. 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 $\binom{n-1}{m}$ white sequences having exactly $m$ $1$’s, the result follows.

## 4 thoughts on “Can you Prove it… combinatorially?”

• Thanks Steven, glad you enjoyed it! 🙂 I wonder if it has been published anywhere in a paper or book – I haven’t found it but maybe I just haven’t looked hard enough. Let me know if you (or anyone else reading this) find it elsewhere.

1. Hi Maria, pretty cool proof! I have never seen it before.
Is it OK if we turn this proof into a math problem in our state competition in Brazil?
Of course, we will credit the proof as yours (or as your camp’s, you choose).

• Hey Carlos, I think it would be great to turn this into a Brazillian Olympiad problem! (Bearing in mind that the proof is online now, so it should be sufficiently disguised to make it a fair question.) And it can certainly be used as a practice problem. I’ll discuss with the other Prove it! staff to confirm that this is ok and see what they think about the accreditation, and I’ll get back to you privately later.

Best wishes,
Maria