Complex Analysis proof of multinomial expression

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

• If my calculation is correct, when $n = 2$, LHS = $15$ while RHS = $90$. – Zilin J. Apr 2 '15 at 15:04
• @roy_24601 you're 100% correct. It doesn't even hold for n=1. I've changed the question. However, any techniques used to find the value of the expression will be of most interest. – Black Apr 2 '15 at 15:12
• Why not use the usual notation for multinomial coefficients? – Christoph Apr 2 '15 at 15:27
• Since the answer appears to be $\binom{2n}{n} {}_3 F_2 \left( \begin{matrix} -n,-n,-n \\ 1,1/2-n \end{matrix}; \frac{1}{4} \right)$, (which is at least a finite sum!) it seems unlikely that such a proof will work in the same way. – Chappers Apr 2 '15 at 15:30
• How did you arrive at that result with the hypergeometric function? @Christoph, I felt that it may show some relationship between the binomial and multinomial result. – Black Apr 2 '15 at 18:32

1 Answer

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.

• Wow, this is very illuminating. Thank you for the techniques you've presented here and clearly explained. This will surely help a lot of people apply complex analytic techniques to combinatorial problems. – Black Apr 18 '15 at 6:27
• @Black: You're welcome! Thanks for your nice comment. :-) The two aspects from Egorychevs book I've used are only the tip of the iceberg. His book is a deep source of knowledge and inspiration for solving binomial sums. I also deeply appreciate the little paper about the bracket notation of the coefficient of operator by the great Don Knuth. Reading it provides a glimpse to us what he might have thought about notational conventions when he was inventing/creating $\TeX$ for us! Best regards, – Markus Scheuer Apr 18 '15 at 11:55