# Sum of multinomals = sum of binomials: why?

I stumbled on the following identity, which has been checked numerically.

Question. Is this true? If so, any proof? $$\sum_{j=0}^{\lfloor\frac{k}2\rfloor}\binom{n-2k+j}{j,k-2j,n-3k+2j} =\sum_{j=0}^{\lfloor\frac{k}2\rfloor}\binom{n-k-2j-1}{k-2j}.$$

Here, $\binom{m}{a,b,c}$ is understood as $\frac{m!}{a!\,b!\,c!}$.

• Set $m=n-2k$. Then $$\binom{n-2k+j}{j,k-2j,n-3k+2j} = \binom{k-j}{j}\binom{m+j}{k-j}$$ and we sum over all values of $j$ (i.e., $0 \leq j \leq \lfloor k/2 \rfloor$ is the same as $0 \leq j \leq k-j$). – Zach Teitler Jun 2 '17 at 21:33
• Good idea. Perhaps the summand on the RHS becomes $\binom{m+k-2j-1}{k-2j}$. Then what? – T. Amdeberhan Jun 2 '17 at 21:42
• $\binom{m+k-2j-1}{k-2j} = \dim S^{k-2j} \mathbb{C}^m$ so RHS = dimension of forms in $m$ variables, of degree $\leq k$, of degree same parity as $k$... no idea if that helps. – Zach Teitler Jun 2 '17 at 21:49
• I like the approach, Let's hope someone can pick up where you left off. – T. Amdeberhan Jun 2 '17 at 21:50

For convenience set $m=n-2k$. Then $$\begin{split} \binom{n-2k+j}{j,k-2j,n-3k+2j} &= \binom{m+j}{j,k-2j,m-k+2j} \\ &= \binom{m+j}{m} \binom{m}{k-2j} \\ &= [t^j](1-t)^{-(m+1)} \cdot [t^{k-2j}](1+t)^m \\ &= [t^{2j}](1-t^2)^{-(m+1)} \cdot [t^{k-2j}](1+t)^m \end{split}$$ where $[t^a]p$ is the coefficient of $t^a$ in the formal power series $p=p(t)$. Note that $[t^{2j+1}](1-t^2)^{-(m+1)} = 0$. So the left hand side is $$\begin{split} [t^k](1-t^2)^{-(m+1)}(1+t)^m &= [t^k](1-t)^{-(m+1)}(1+t)^{-1} \\ &= \sum_{j=0}^k [t^{k-j}](1-t)^{-(m+1)} \cdot [t^j](1+t)^{-1} \\ &= \sum_{j=0}^k \binom{m+k-j}{m} (-1)^j \\ &= \sum_{j=0}^{\lfloor k/2 \rfloor} \binom{m+k-2j}{m} (-1)^{2j} + \binom{m+k-2j-1}{m} (-1)^{2j+1} \\ &= \sum_{j=0}^{\lfloor k/2 \rfloor} \binom{m+k-2j}{m}-\binom{m+k-2j-1}{m} \\ &= \sum_{j=0}^{\lfloor k/2 \rfloor} \binom{m+k-2j-1}{m-1} \end{split}$$ as desired.
As functions of $k$, it appears that both sides satisfy the recurrence \begin{align} & 4(-n+2\,k+1) (-n+2k) A(n,k) \\[6pt] & {} + (8k^2-8\,kn+n^2+10k-9n) A(n,k+1)\\[6pt] & {} + (k+2)(-n+k) A(n,k+2)=0 \end{align} with $A(n,0) = 1$, $A(n,1) = n-2$.