CombinatorialIdentity GeneratingFunction Challenging

Problem - 4319

Let $N$ be the value of the following expression. $$\sum_{k=0}^{n-1}\left(\binom{n}{0}+\binom{n}{1}+\cdots+\binom{n}{k}\right)\left(\binom{n}{k+1}+\binom{n}{k+2}+\cdots+\binom{n}{n}\right)$$

Show $$N=\frac{n}{2}\binom{2n}{n}$$


Let the left side be $a_{n-1}$ and $$d_k=\binom{n}{0}+\binom{n}{1}+\cdots+\binom{n}{k}$$

Then we have $$\binom{n}{k+1}+\binom{n}{k+2}+\cdots+\binom{n}{n}=\binom{n}{n-k-1}+\binom{n}{n-k-2}+\cdots+\binom{n}{0}=d_{n-k-1}$$

It follows that $$a_{n-1}=\sum_{k=0}^{n-1}d_kd_{n-k-1}$$

Let $f(x)$ be the generating function of $\{d_k\}$, Thus, $$f(x)=\sum_{k=0}^{\infty}d_kx^k\implies f^2(x)=\sum_{n=0}^{\infty}\left(\sum_{k=0}^{n}d_kd_{n-k}\right)x^n$$

This means that $a_{n-1}$ is the coefficient of $x^{n-1}$ in $f^2(x)$.

Because the generating function of $$\binom{n}{0}, \binom{n}{1}, \cdots, \binom{n}{n}$$

is $(1+x)^n$, by the conclusion of # 4313, the generating function of $$\binom{n}{0}, \binom{n}{0} + \binom{n}{1}, \binom{n}{0} + \binom{n}{1}+\binom{n}{2}, \cdots $$

is $$(1+x)^n\sum_{k=0}^{\infty}x^k=\frac{(1+x)^n}{1-x}$$

And $a_{n-1}$ is the coefficient of the term $x^{n-1}$ in $$f^2(x)=\frac{(1+x)^{2n}}{(1-x)^2}$$

From the conclusion of # 4284, we know $$\frac{1}{(1-x)^2}=\sum_{k=0}^{\infty}\binom{2-1+k}{2-1}x^k=\sum_{k=0}^{\infty}(k+1)x^k$$

and by binomial expansion $$(1+x)^{2n}=\sum_{k=0}^{2n}\binom{2n}{k}x^k$$

Therefore, $$\frac{(1+x)^{2n}}{(1-x)^2}=\sum_{k=0}^{\infty}\left(\sum_{l=0}^{k}\binom{2n}{l}(k-l+1)\right)x^k$$

It follows that $$a_{n-1}=\sum_{l=0}^{n-1}\binom{2n}{l}(n-l)$$

From # 4295, we know $$\sum_{k=0}^{n}\binom{2n}{k}=2^{2n-1}+\frac{1}{2}\binom{2n}{n}\quad\text{and}\quad\sum_{k=0}^{n}k\binom{2n}{k}=n\cdot 2^{2n-1}$$

Hence, $$\begin{align*} a_{n-1}=\ & n\sum_{l=0}^{n-1}\binom{2n}{l} - \sum_{l=0}^{n-1}l\binom{2n}{l} \\ \\=\ & n\left(\sum_{l=0}^{n}\binom{2n}{l} - \binom{2n}{n}\right) -\left(\sum_{l=0}^{n}\binom{2n}{l} - n\binom{2n}{n}\right) \\ \\=\ &n\left(2^{2n-1} +\frac{1}{2}\binom{2n}{n} -\binom{2n}{n}\right) - \left(n\cdot 2^{2n-1} - n\binom{2n}{n} \right) \\ \\=\ &\frac{n}{2}\binom{2n}{n} \end{align*}$$

report an error