# Simplifying summation of binomials

I am working on a proof and think that the following equality holds but am unable to prove it: $$\sum_{k_1=0}^{m} \sum_{k_2=0}^{m-k_1} \dots \sum_{k_{d^2/2}=m-(k_1+k_2+\dots+k_{d^2/2-1})}^{m-(k_1+k_2+\dots+k_{d^2/2-1})}\frac{m!m!}{(k_1)!(k_1)!(k_2)!(k_2)!\dots(k_{d^2/2})!(k_{d^2/2})!}\stackrel{?}{=} \binom{2m}{m}^{d-1}.$$ where $$k_1+k_2+\dots+k_d^2/2=m$$. I have tried multiplying the inner fraction by $$\frac{(m-k_1)!^2}{(m-k_1)!^2}$$ (and so on) and reducing $$\frac{m!}{k_1!(m-k_1)!}\frac{m!}{k_1!(m-k_1)!}=\binom{m}{k_1}^2$$ but to no avail. I am hoping to use that $$\sum^m_{k=0} \binom{m}{k}^2=\binom{2m}{m}$$ or was also considering proof by induction. Note that this equality $$\stackrel{?}{=}$$ just may not be true.

## 1 Answer

The relation is still not correct for $$d\neq 2$$. Asuming $$d$$ to be a even number, we have, \begin{align} \sum_{k_1=0}^m \sum_{k_1=0}^{m-k_1} \ldots \sum_{k_{d^2/2-1}=0}^{m-\sum_{i=1}^{d^2/2-2}k_i}\left[\frac{m!}{k_1!k_2!\ldots k_{d^2/-1}!(m-\sum_{i=1}^{d^2/2-1}k_i)!}\right]^2\\ &\hspace{-10cm}= \sum_{k_1=0}^m \sum_{k_1=0}^{m-k_1} \ldots \sum_{k_{d^2/2-1}=0}^{m-\sum_{i=1}^{d^2/2-2}k_i}\left[\binom{m}{k_1}\binom{m-k_1}{k_2}\ldots \binom{m-\sum_{i=1}^{d^2/2-2}k_i}{k_{d^2/2-1}}\right]^2\\ &\hspace{-10cm}= \sum_{k_1=0}^m \sum_{k_1=0}^{m-k_1} \ldots \sum_{k_{d^2/2-2}=0}^{m-\sum_{i=1}^{d^2/2-3}k_i}\left[\left(\binom{m}{k_1}\binom{m-k_1}{k_2}\ldots \binom{m-\sum_{i=1}^{d^2/2-3}k_i}{k_{d^2/2-2}}\right)^2\right.\\ &\hspace{-1cm}\left.\times\sum_{k_{d^2/2-1}=0}^{m-\sum_{i=1}^{d^2/2-2}k_i}\binom{m-\sum_{i=1}^{d^2/2-2}k_i}{k_{d^2/2-1}}^2\right]\\ &\hspace{-10cm}= \sum_{k_1=0}^m \sum_{k_1=0}^{m-k_1} \ldots \sum_{k_{d^2/2-2}=0}^{m-\sum_{i=1}^{d^2/2-3}k_i}\left[\left(\binom{m}{k_1}\binom{m-k_1}{k_2}\ldots \binom{m-\sum_{i=1}^{d^2/2-3}k_i}{k_{d^2/2-2}}\right)^2\right.\\ &\hspace{-1cm}\left.\times \binom{2(m-\sum_{i=1}^{d^2/2-2}k_i)}{m-\sum_{i=1}^{d^2/2-2}k_i}\right]\\ &\hspace{-10cm}\leq \sum_{k_1=0}^m \sum_{k_1=0}^{m-k_1} \ldots \sum_{k_{d^2/2-1}=0}^{m-\sum_{i=1}^{d^2/2-2}k_i}\left(\binom{m}{k_1}\binom{m-k_1}{k_2}\ldots \binom{m-\sum_{i=1}^{d^2/2-3}k_i}{k_{d^2/2-2}}\right)^2\binom{2m}{m}\\ &\hspace{-10cm}\leq \binom{2m}{m}^{d^2/2-1}\leq \binom{2m}{m}^{d-1}. \end{align} Here, we use the relation $$\sum_{k=0}^n\binom{n}{k}^2=\binom{2n}{n}$$, and fact that $$\binom{2n}{n}$$ is an increasing function of $$n$$ as shown below: $$\begin{equation} \binom{2(n+1)}{n+1} - \binom{2n}{n} = \binom{2n}{n}\left(\frac{(2n+1)(2n+2)}{(n+1)^2}-1\right) = \binom{2n}{n}\left(\frac{3n+1}{(n+1)}\right)>0. \end{equation}$$

• Edited the question since I had a typo with my summation indices. $\sum_{i=0}^{d^2/2}k_i=m$ therefore only $(0,3)=1, (1,2)=9, (2,1)=9,(3,0=9)$ would count from your example and the sum of those matches $RHS=20$. – cpage Apr 8 at 12:07