Showing an identity between polynomials whose coefficients involve combinatorial identities

Question

I want to show that $$ \sum_{k=0}^{\lfloor n/2 \rfloor} \sum_{l=0}^{\lfloor \frac{n-2k}{2}\rfloor} (-1)^l \binom{n}{k} \binom{n-2k-l}{l} \frac{n-2k}{n-2k-l} x^{n-2k-2l} = x^n. $$ If we "compare coefficients", then we get $x^n$ on the left if $k = l = 0$, hence $$ \binom{n}{0} \binom{n}{0} \frac{n}{n} x^{n} = x^n $$ is valid. But the other sums look quite messy...

Answer 1

Putting $n=2N$ we want to show for integral $N\geq 0$: \begin{align*} \sum_{k=0}^N\sum_{l=0}^{N-k}(-1)^l\binom{2N}{k}\binom{2N-2k-l}{l} \frac{2N-2k}{2N-2k-l}x^{2N-2k-2l}=x^{2N} \end{align*}

At first we derive a somewhat more convenient representation. We obtain \begin{align*} \color{blue}{\sum_{k=0}^N}&\color{blue}{\sum_{l=0}^{N-k}(-1)^l\binom{2N}{k}\binom{2N-2k-l}{l} \frac{2N-2k}{2N-2k-l}x^{2N-2k-2l}}\\ &=\sum_{k=0}^N\sum_{l=0}^{N-k}(-1)^{N-k-l}\binom{2N}{k}\binom{N-k+l}{N-k-l} \frac{2N-2k}{N-k+l}x^{2l}\tag{1}\\ &=\sum_{k=0}^N\sum_{l=0}^{k}(-1)^{k-l}\binom{2N}{N-k}\binom{k+l}{k-l} \frac{2k}{k+l}x^{2l}\tag{2}\\ &=\sum_{l=0}^N\sum_{k=l}^{N}(-1)^{k-l}\binom{2N}{N-k}\binom{k+l}{k-l} \frac{2k}{k+l}x^{2l}\tag{3}\\ &\,\,\color{blue}{=\sum_{l=0}^N\sum_{k=0}^{N-l}(-1)^{k}\binom{2N}{N-k-l}\binom{k+2l}{k} \frac{2k+2l}{k+2l}x^{2l}}\tag{4}\\ \end{align*}

Comment:

• In (1) we exchange the summation order of the inner sum $l\to N-k-l$.

• In (2) we exchange the summation order of the outer sum $k\to N-k$.

• In (3) we exchange the series.

• In (4) we shift the index of the inner sum to start with $k=0$.

Let's call the polynomial $P(x)$. We can easily derive from (4) the coefficient $[x^{2N}]$ of the highest power and see \begin{align*} \color{blue}{[x^{2N}]P(x)=1} \end{align*}

Next we consider for integral $N>0$ and $0\leq t<N$ according to (4): \begin{align*} &\color{blue}{[x^{2t}]P(x)=\sum_{k=0}^{N-t}(-1)^{k}\binom{2N}{N-k-t}\binom{k+2t}{k} \frac{2k+2t}{k+2t}}\\ &\quad=\sum_{k=0}^{N-t}(-1)^{k}\binom{2N}{N-k-t}\binom{k+2t}{k} \left(1+\frac{k}{k+2t}\right)\\ &\quad=\sum_{k=0}^{N-t}(-1)^{k}\binom{2N}{N-k-t}\binom{k+2t}{k}+\sum_{k=1}^{N-t}(-1)^{k}\binom{2N}{N-k-t}\binom{k+2t-1}{k-1}\tag{5}\\ &\quad=\sum_{k=0}^{N-t}(-1)^{k}\binom{2N}{N-k-t}\binom{k+2t}{k} +\sum_{k=0}^{N-t-1}(-1)^{k}\binom{2N}{N-k-t-1}\binom{k+2t}{k}\tag{6}\\ &\quad=\sum_{k=0}^{N-t}\binom{2N}{N-k-t}\binom{-2t-1}{k} +\sum_{k=0}^{N-t-1}\binom{2N}{N-k-t-1}\binom{-2t-1}{k}\tag{7}\\ &\quad=\binom{2N-2t-1}{N-t}-\binom{2N-2t-1}{N-t-1}\tag{8}\\ &\quad\,\,\color{blue}{=0} \end{align*} and the claim follows.

Comment:

• In (5) we multiply out and apply to the right-hand series the binomial identity $\binom{p}{q}=\frac{p}{q}\binom{p-1}{q-1}$.

• In (6) we shift the index of the right-hand series to start with $k=0$.

• In (7) we apply the binomial identity $\binom{-p}{q}=\binom{p+q-1}{q}(-1)^q$ twice.

• In (8) we apply the Chu-Vandermonde Identity twice.