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

Question

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$.

Answer 1

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.

Answer 2

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.