Sum of squares of binomial coefficient with slight modification

74 Views Asked by At

I know, These type of questions have been asked many times and infact, this question is very much similar to my question.

Let $ C_r$ denote ${}^nC_r$ (alternatively ${ n \choose k}$ )

Then for an even natural $n$ the value of $$ S= 2\frac{\left( \frac{n}{2} \right)! \left( \frac{n}{2} \right)! }{n!}[ (C_0)^2 -2(C_1)^2 + 3(C_2)^2 +\cdots + (-1)^n(n+1)(C_n)^2 ]$$

I did this by the "classic" way.

Consider the expansion $$(1+x)^n=\displaystyle \sum_{r=0}^{n}C_rx^r \tag 1$$

Multiply both sides by $x$ and then differentiate w.r.t. $x$ $$(1+x)^n+nx(1+x)^{n-1}=\displaystyle \sum_{r=0}^{n}(r+1)C_rx^r$$

Now multiply the corresponding sides of this equation and $(1)$ (after substituting $x \rightarrow -x$) to get,

$$(1-x^2)^n+nx(1-x)(1-x^2)^{n-1} = [C_0+2C_1x+3C_2x^2+\cdots+(n+1)C_nx^n]\times[C_0-C_1x+C_2x^2-\cdots+(-1)^nC_nx^n]$$

On RHS, this $[(C_0)^2 -2(C_1)^2 + 3(C_2)^2 +\cdots + (-1)^n(n+1)(C_n)^2]$ thing is the coefficient of $x^n$.

Hence, on comparing the coefficient of $x^n$ on RHS, we get $$(-1)^{\frac{n}{2}} {}^nC_{\frac{n}{2}} -n\cdot (-1)^{\left(\frac{n-2}{2}\right)}{}^{n-1}C_{\frac{n-2}{2}}$$

Which on simplifying comes out to $(-1)^{\frac{n}{2}}(n+2)\frac{n!}{2 \left( \frac{n}{2} \right)! \left( \frac{n}{2} \right)! }$

Thus, $S= (-1)^{\frac{n}{2}}(n+2)$

2

There are 2 best solutions below

0
On BEST ANSWER

I would let $n=2m$ and rewrite the identity as

$$\frac2{\binom{2m}m}\sum_{k=0}^{2m}(-1)^k(k+1)\binom{2m}k^2=(-1)^m(2m+2)\;,$$

which can immediately be rewritten as

$$\sum_{k=0}^{2m}(-1)^k(k+1)\binom{2m}k^2=(-1)^m(m+1)\binom{2m}m\;.\tag{1}$$

Now

$$\begin{align*} \sum_{k=0}^{2m}(-1)^k(k+1)\binom{2m}k^2&=\sum_{k=0}^{m-1}(-1)^k(k+1)\binom{2m}k^2+(-1)^m(m+1)\binom{2m}m^2\\ &\quad+\sum_{k=m+1}^{2m}(-1)^k(k+1)\binom{2m}k^2\\ &=\sum_{k=0}^{m-1}(-1)^k(k+1)\binom{2m}k^2+(-1)^m(m+1)\binom{2m}m^2\\ &\quad+\sum_{k=0}^{m-1}(-1)^{2m-k}(2m+1-k)\binom{2m}k^2\\ &=\sum_{k=0}^{m-1}(-1)^k(k+1)\binom{2m}k^2+(-1)^m(m+1)\binom{2m}m^2\\ &\quad+\sum_{k=0}^{m-1}(-1)^k(2m+1-k)\binom{2m}k^2\\ &=2(m+1)\sum_{k=0}^{m-1}(-1)^k\binom{2m}k^2+(-1)^m(m+1)\binom{2m}m^2\\ &=(m+1)\sum_{k=0}^{2m}(-1)^k\binom{2m}k^2\;, \end{align*}$$

so that $(1)$ reduces to

$$\sum_{k=0}^{2m}(-1)^k\binom{2m}k^2=(-1)^m\binom{2m}m\;.\tag{2}$$

(Up to here this is really just a slightly different version of user675453’s argument that happens to be the way that I saw it.)

$(2)$ is moderately well-known but far from obvious (and not an identity in my ready armamentarium!); it can be proved with a nice combinatorial argument that I think I learned from Marc van Leeuwen. Suppose that you have $2m$ blue balls numbered $1$ through $2m$ and $2m$ red balls, also numbered $1$ through $2m$. A pair is a red and a blue ball with the same number. The lefthand side of $(2)$ counts the ways to choose a set containing equal numbers of red and blue balls, counting the set with a factor of $-1$ if the number of each color is odd.

I claim that the subsets that do not contain exactly one member of each pair cancel out in this counting. Suppose that $B$ is such a subset; then there is a smallest $\ell\in[2m]$ such that $B$ either contains neither ball numbered $\ell$ or contains both balls numbered $\ell$. If it contains neither of those balls, add them to $B$ to get a new subset $\hat B$, and if it contains both of them, remove them to get $\hat B$. In either case $\hat B$ still has the same number of red and blue balls, but that number has changed parity, so $B$ and $\hat B$ are counted with opposite signs. Finally, $\hat{\hat B}=B$, so we have indeed shown shown that the subsets that do not contain exactly one member can be matched up to cancel out in the count.

How many subsets contain exactly one member of each pair? They are subsets of size $2m$ in which the $m$ blue balls have precisely the $m$ numbers that are not on the $m$ red balls. Thus, each of these subsets is completely determined by the set of $m$ numbers on the red balls, and there are therefore $\binom{2m}m$ of them. Each of them is counted positively if $m$ is even and negatively if $m$ is odd, so the total count must be $(-1)^m\binom{2m}m$, as desired.

0
On

However, this problem can more neatly solved by the fact : $$ {n \choose k} = {n \choose n-k}$$

$$S=2\frac{\left( \frac{n}{2} \right)! \left( \frac{n}{2} \right)! }{n!}[ (C_0)^2 -2(C_1)^2 + 3(C_2)^2 +\cdots + (-1)^n(n+1)(C_n)^2 ] \tag 1$$

$$S= 2\frac{\left( \frac{n}{2} \right)! \left( \frac{n}{2} \right)! }{n!}[(C_n)^2-2(C_{n-1})^2+3(C_{n-2})^2-\cdots-n(C_1)^2+(n+1)(C_0)^2] \tag 2$$ Adding $(1)$ and $(2)$ $$2S=2\frac{\left( \frac{n}{2} \right)! \left( \frac{n}{2} \right)! }{n!}(n+2)[(C_0)^2-(C_1)^2+\cdots+(C_n)^2]$$

And Finally, $ S=(-1)^{\frac{n}{2}}(n+2)$

(Since n is even, $\displaystyle \sum_{r=0}^{n}(-1)^r(^nC_r)^2=(-1)^{\frac{n}{2}}{}^nC_{\frac{n}{2}}$)