Complex Analysis proof of multinomial expression

Question

I've recently come across the following identity $$ \displaystyle \sum_{k = 0}^n {n \choose k}^2= {2n \choose n} $$

A nice complex analysis proof (by Felix Marin, here) follows as: $\newcommand{\angles}[1]{\left\langle\, #1 \,\right\rangle} \newcommand{\braces}[1]{\left\lbrace\, #1 \,\right\rbrace} \newcommand{\bracks}[1]{\left\lbrack\, #1 \,\right\rbrack} \newcommand{\ceil}[1]{\,\left\lceil\, #1 \,\right\rceil\,} \newcommand{\dd}{{\rm d}} \newcommand{\ds}[1]{\displaystyle{#1}} \newcommand{\expo}[1]{\,{\rm e}^{#1}\,} \newcommand{\fermi}{\,{\rm f}} \newcommand{\floor}[1]{\,\left\lfloor #1 \right\rfloor\,} \newcommand{\half}{{1 \over 2}} \newcommand{\ic}{{\rm i}} \newcommand{\iff}{\Longleftrightarrow} \newcommand{\imp}{\Longrightarrow} \newcommand{\pars}[1]{\left(\, #1 \,\right)} \newcommand{\partiald}[3][]{\frac{\partial^{#1} #2}{\partial #3^{#1}}} \newcommand{\pp}{{\cal P}} \newcommand{\root}[2][]{\,\sqrt[#1]{\vphantom{\large A}\,#2\,}\,} \newcommand{\sech}{\,{\rm sech}} \newcommand{\sgn}{\,{\rm sgn}} \newcommand{\totald}[3][]{\frac{{\rm d}^{#1} #2}{{\rm d} #3^{#1}}} \newcommand{\ul}[1]{\underline{#1}} \newcommand{\verts}[1]{\left\vert\, #1 \,\right\vert}$ \begin{align} \color{}{\large\sum_{k\ =\ 0}^{n}{n \choose k}^{2}}&= \sum_{k\ =\ 0}^{n}{n \choose k} \oint_{\verts{z}\ =\ 1}{\pars{1 + z}^{n} \over z^{k + 1}}\,{\dd z \over 2\pi\ic} =\oint_{\verts{z}\ =\ 1}{\pars{1 + z}^{n} \over z} \sum_{k\ =\ 0}^{n}{n \choose k}\pars{1 \over z}^{k}\,{\dd z \over 2\pi\ic} \\[5mm]&=\oint_{\verts{z}\ =\ 1}{\pars{1 + z}^{n} \over z} \pars{1 + {1 \over z}}^{n}\,{\dd z \over 2\pi\ic} =\oint_{\verts{z}\ =\ 1}{\pars{1 + z}^{2n} \over z^{n + 1}}\,{\dd z \over 2\pi\ic} =\color{}{\large{2n \choose n}} \end{align}

Is there a way to generalise this technique to find the value of

$$ \displaystyle \sum_{k_1 + k_2 = 0}^n {n \choose k_1, k_2}^2 $$ where $$ {n \choose k_1, k_2} = \frac{n!}{(n-(k_1+k_2))!k_1!k_2!} $$ (please note that this is not the definition of the multinomial coefficient which would actually be $$ {n \choose k_1, k_2} = \frac{n!}{k_1!k_2!} $$)

tl;dr

Find the value of (if possible) $$ \displaystyle \sum_{k_1 + k_2 = 0}^n {n \choose k_1, k_2}^2 $$ using complex analytical techniques.

EDIT: If it helps, it is easy to show that $$ {n \choose k_1, k_2} = \frac{n!}{(n-(k_1+k_2))!k_1!k_2!} = {n \choose k_1} {n - k_1 \choose k_2} $$ A similar problem dealing with binomials and trinomials has been solved using complex analytic techniques here

Answer 1

Note: Here is a slightly different variation of the same story. These techniques are also known as formal residual calculus for power series. They are based upon Cauchys residue theorem and were introduced by G.P. Egorychev (Integral Representation and the Computation of Combinatorial Sums) to compute binomial identies.

We use the residue notation and write e.g. \begin{align*} \mathop{res}_z\frac{(1+z)^{n}}{z^{k+1}}=\frac{1}{2\pi i}\oint_{|z|=1}\frac{(1+z)^{n}}{z^{k+1}}\mathop{dz} \end{align*}

In fact we will use only two aspects of this theory:

Let $A(z)=\sum_{j=0}^{\infty}a_jz^j$ be a formal power series, then

• Write the binomial coeffients as residuals of corresponding formal power series

\begin{align*} \mathop{res}_{z}\frac{A(z)}{z^{j+1}}=a_j\tag{1} \end{align*}

• Apply the substitution rule for formal power series:

\begin{align*} A(z)=\sum_{j=0}^{\infty}a_jz^{j}=\sum_{j=0}^{\infty}z^j\mathop{res}_{w}\frac{A(w)}{w^{j+1}}\tag{2} \end{align*}

---

Using this notation, we show at first that

\begin{align*} \sum_{k=0}^n\binom{n}{k}^2=\binom{2n}{n}\tag{3} \end{align*}

which is in fact the main part in order to simplify OPs expression \begin{align*} \sum_{{k_1+k_2=0}\atop{k_1,k_2\geq 0}}\binom{n}{n-(k_1+k_2),k_1,k_2}^2 \end{align*} We write the trinomial coefficient in the expression above in standard form using the notation for multinomial coefficients.

We observe that \begin{align*} \sum_{k=0}^n\binom{n}{k}^2&=\sum_{k=0}^{\infty}\binom{n}{k}\binom{n}{k}\tag{4}\\ &=\sum_{k=0}^{\infty}\mathop{res}_{u}\frac{(1+u)^{n}}{u^{k+1}}\mathop{res}_{w}\frac{(1+w)^{n}}{w^{k+1}}\tag{5}\\ &=\mathop{res}_{u}\frac{(1+u)^{n}}{u}\sum_{k=0}^{\infty}\frac{1}{u^{k}}\mathop{res}_{w}\frac{(1+w)^{n}}{w^{k+1}}\tag{6}\\ &=\mathop{res}_{u}\frac{(1+u)^{n}}{u}\left(1+\frac{1}{u}\right)^{n}\tag{7}\\ &=\mathop{res}_{u}\frac{(1+u)^{2n}}{u^{n+1}}\\ &=[z^n](1+u)^{2n}\tag{8}\\ &=\binom{2n}{n} \end{align*}

Comment:

• In (4) we extend the upper limit of the sum without changing the value since we are only adding zeroes.

• In (5) we rewrite the binomial coefficients using residues according to (1)

• In (6) we do some rearrangements to prepare for the substitution rule

• In (7) we apply the substitution rule according to (2)

• In (8) we use the coefficient of operator $[z^n]$ to denote the coefficient $a_n$ in $A(z)=\sum_{j=0}^{\infty}a_jz^j$. Observe that following is valid when using the formal residual operator $\mathop{res}$

$$\mathop{res}_z\frac{A(z)}{z^{n+1}}=[z^{-1}]\frac{1}{z^{n+1}}A(z)=[z^n]A(z)$$

$$$$

We now show that OPs expression is

\begin{align*} \sum_{{k_1+k_2=0}\atop{k_1,k_2\geq 0}}\binom{n}{n-(k_1+k_2),k_1,k_2}^2=\sum_{k=0}^{n}\binom{2n}{k}^2\binom{2k}{k}\tag{9} \end{align*}

Note: The RHS of (9) is stated as integer sequence A002893 in OEIS which indicates, that further simplifications are not feasible.

Since OP already stated, that \begin{align*} \binom{n}{n-(k_1+k_2),k_1,k_2}=\frac{n!}{\left(n-(k_1+k_2)\right)!k_1!k_2!}=\binom{n}{k_1}\binom{n-k_1}{k_2} \end{align*}

we can write \begin{align*} \sum_{{k_1+k_2=0}\atop{k_1,k_2\geq 0}}&\binom{n}{n-(k_1+k_2),k_1,k_2}^2\\ &=\sum_{k_1=0}^{n}\sum_{k_2=0}^{n-k_1}\binom{n}{k_1}^2\binom{n-k_1}{k_2}^2\\ &=\sum_{k_1=0}^{n}\binom{n}{k_1}^2\left(\sum_{k_2=0}^{n-k_1}\binom{n-k_1}{k_2}^2\right)\tag{10}\\ &=\sum_{k_1=0}^{n}\binom{n}{k_1}^2\binom{2n-2k_1}{n-k_1}\tag{11}\\ &=\sum_{k=0}^{n}\binom{n}{k}^2\binom{2k}{k}\\ \end{align*}

We observe the residual calculus was used in (10) and (11) by applying (3). Everything else was done with elementary transformations.

---

Note: Further applications of the formal residual calculus are not promising. We could e.g. use the identity $$\binom{2k}{k}=(-4)^k\binom{-\frac{1}{2}}{k}$$ and then try to apply the substitution rule (2) again:

\begin{align*} \sum_{k=0}^{n}&\binom{n}{k}^2\binom{2k}{k}\\ &=\sum_{k=0}^{n}\binom{n}{k}^2(-4)^k\binom{-\frac{1}{2}}{k}\\ &=\sum_{k=0}^{\infty}\mathop{res}_{u}\frac{(1+u)^{n}}{u^{k+1}}\mathop{res}_{w}\frac{(1+w)^{n}}{w^{k+1}} (-4)^k\mathop{res}_{z}\frac{(1+z)^{-\frac{1}{2}}}{z^{k+1}}\\ &=\mathop{res}_{u,w}\frac{(1+u)^{n}}{u}\frac{(1+w)^{n}}{w}\sum_{k=0}^{\infty}\left(-\frac{4}{uw}\right)^k \mathop{res}_{z}\frac{(1+z)^{-\frac{1}{2}}}{z^{k+1}}\\ &=\mathop{res}_{u,w}\frac{(1+u)^{n}}{u}\frac{(1+w)^{n}}{w} \left(1-\frac{4}{uw}\right)^{-\frac{1}{2}} \end{align*} regrettably further simplifications similar to (7) are not feasible. But of course this technique is often helpful, see e.g. this answer regarding central binomial coefficients.