Challenge: How to prove this identity between bi- and trinomial coefficients?

This question is the continuation of its predecessor.

Using the convention that trinomial coefficients $$\binom{n}{k_1,k_2,k_3}=\frac{n!}{k_1! k_2! k_3!}$$ are zero if $k_i<0$ or $\sum_i k_i\neq n$, we have the following relation between binomial and trinomial coefficients, $$\binom{2n}{\ell} = \sum_{k=0}^{\lfloor \frac{\ell}2 \rfloor} 2^{\ell-2k} \binom{n}{\ell-2k,k,n-\ell+k} = \sum_{k=\max(\ell-n,0)}^{\lfloor \frac{\ell}2 \rfloor} \frac{2^{\ell-2k} n!}{(\ell-2k)!\,k!\,(n-\ell+k)!}, \quad (*)$$ and in particular, $$(2n)!=\sum_{k=0}^{\lfloor \frac{n}2 \rfloor} \frac{2^{n-2k} (n!)^3}{(n-2k)!\,(k!)^2}.$$

I came across this identity as a by-product of a different proof, and my question is, how one might prove this identity directly - e.g. via generating functions or other tools form number theory (which is not my expertise by a long shot) - and thought that this might be an interesting challenge.

Originally I posted just the latter identity, where Semiclassical solved this by a double-counting argument (after first recovering the form of the binomial coefficient).

Since the trinomial coefficient can trivially be split into two binomial coefficients, it might also be possible to adapt the double-counting argument to this, but it's not immediately obvious to me. Using the same method as in Semiclassical's answer, counting the ways of putting $\ell$ (wlog $\le n$) 1s in a $2\times n$-array by taking $k$ columns of 0s, $m$ columns of 1s and $n-k-m$ columns with 0&1 doesn't seem to work, because $m$ would need to be simultaneously $k$ (for the power of 2), $\ell-2k$ (for the binomial coefficient) and $\ell+k-n$ for the condition that there are $\ell$ 1s.

Some remarks:

• I tried to search for this identity without success, and would be interested in a reference if someone has seen similar things show up somewhere else.
• I've successfully tested the (first) identity numerically, which makes me quite certain that I've not made a mistake in the proof (the indirect version mentioned above).
• Visually, the relation also has a potentially interesting interpretation: As the binomial coefficients correspond to Pascal's triangle, so do the trinomial coefficients correspond to Pascal's tetrahedron (or Pascal's pyramid). Therefore, $(*)$ means that certain weighted sums within the $n^{\mathrm{th}}$ level of Pascal's tetrahedron give the $(2n)^{\mathrm{th}}$ row of Pascal's triangle, as illustrated below for $n=5$. • I think the double-counting argument does go through still, but I'll have to make sure. For sake of diversity, though, I'll try to find a generating function argument. (I suspect this version is actually easier to prove that way; see the discussion on page 130 of Wilf to get a sense of why that should be so.) – Semiclassical Sep 10 '14 at 14:24
• @Semiclassical: Thanks for that reference - very illuminating read about the "Snake Oil Method". – Axel Sep 10 '14 at 14:42

We may prove this in a slick way via the Snake Oil method of Wilf (see link in the comments of the OP). To make notation far simpler, we note that the range of $k$ and $l$ is enforced by the binomial coefficients--they vanish for integers not valid for counting--and so sums over $k,l$ are taken over $\mathbb{Z}$.

That convention in mind, we multiply the RHS by $x^l$ and sum over all integer $l$:

\begin{align} \sum_{\ell,k} \binom{n}{\ell-2k,k,n-\ell+k}2^{\ell-2k} x^\ell &= \sum_{\ell, k} \binom{n}{\ell,k,n-\ell-k}2^{\ell} x^{\ell+2k}\\ &= \sum_{\ell, k} \binom{n}{\ell,k,n-\ell-k}(2y)^{\ell} (x^2)^k\\ &= (x^2+2x+1)^n \end{align}

In the first equality, we have shifted $\ell \mapsto \ell+2k$; rearranging slightly, we recognize the form of the trinomial theorem and thereby sum the series. But we can factor this expression to $(1+x)^{2n}$ and so apply the binomial theorem to obtain the $l$-th coefficient as $\binom{2n}{l}$. Comparing this with our first expression gives the desired identity.

• That was surprisingly easy - thanks! ;-) – Axel Sep 11 '14 at 7:59
• I was pleasantly surprised at how simple this was as well. What strikes me as especially cute is that it boils down to "the square of a binomial is a trinomial" to explain the connection between binomial and trinomial coefficients. It also is readily generalized, e.g cubing $1+x$ to get a relation between binomial coefficients and a (triple) series of tetra-nomial coefficients. @axel – Semiclassical Sep 11 '14 at 11:38
• I wanted to thank you for exposing me to generating function techniques - I ended up needing them for a fairly involved estimate that forms the core of a substantial part of my last paper (resp. thesis). Unfortunately, I couldn't write this privately (thanks to meta.stackexchange.com/q/431), otherwise I would have provided a reference, of course. But thanks again! – Axel Jan 21 '16 at 13:51

Suppose we seek to evaluate (do some re-writing as observed by the OP) $$\sum_{k=0}^n {n\choose k} 2^{l-2k} {n-k\choose n-l+k}.$$

Start from $${n-k\choose n-l+k} = \frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{1}{z^{n-l+k+1}} (1+z)^{n-k} \; dz.$$

This gives the following integral for the sum $$\frac{1}{2\pi i} \int_{|z|=\epsilon} \sum_{k=0}^n {n\choose k} 2^{l-2k} \frac{1}{z^{n-l+k+1}} (1+z)^{n-k} \;dz \\ = \frac{2^l}{2\pi i} \int_{|z|=\epsilon} \frac{(1+z)^n}{z^{n-l+1}} \sum_{k=0}^n {n\choose k} 2^{-2k} \frac{1}{z^k(1+z)^k} \;dz \\ = \frac{2^l}{2\pi i} \int_{|z|=\epsilon} \frac{(1+z)^n}{z^{n-l+1}} \left(1 + \frac{1}{4z(z+1)}\right)^n \; dz \\ = \frac{2^l}{2\pi i} \int_{|z|=\epsilon} \frac{(1+z)^n}{z^{n-l+1}} \left(\frac{1+4z+4z^2}{4z(z+1)}\right)^n \; dz \\ = \frac{2^l}{2\pi i} \int_{|z|=\epsilon} \frac{(1+z)^n}{z^{n-l+1}} \frac{(1+2z)^{2n}}{2^{2n} (z(1+z))^n} \; dz \\ = \frac{2^{l-2n}}{2\pi i} \int_{|z|=\epsilon} \frac{(1+2z)^{2n}}{z^{2n-l+1}} \; dz.$$

This last integral can be evaluated by inspection and yields $$2^{l-2n} [z^{2n-l}] (1+2z)^{2n} = 2^{l-2n} \times {2n\choose 2n-l} 2^{2n-l} = {2n\choose l}.$$

A trace as to when this method appeared on MSE and by whom starts at this MSE link.

• That's an interesting approach! Have you thought about where this method might be superior to the generating function approach? In any case, having to decide which answer to accept, I ended up deciding in favour of the simpler one. – Axel Sep 11 '14 at 8:02