# proofs for combinatorial identities?

by using the identity $(1-x^2)^n=(1+x)^n(1-x)^n$, show that for each $m \in \Bbb N$ with $m < n$, summation of

$$\sum_{i=0}^n(-1)^i\binom{n}i^2=\begin{cases} 0,&\text{if }n\text{ is odd}\\ (-1)^{n/2}\binom{n}{n/2},&\text{if }n\text{ is even}\;. \end{cases}$$ that is summation of (−1)^i (n taken i )(n taken 2m−i) i=0 to 2m is (−1)^m (n taken m) if n is even and Summation of (−1)^i (n taken i )(n taken 2m+1−i) i from 0 to 2m+1 is 0 if n is odd.

please explain and how to prove the two cases.

• Have you put any work in? Have you even checked a few cases, for small values of $n$? Math is not a spectator sport! – Gerry Myerson Aug 14 '13 at 13:18
• What identity ? – peterwhy Aug 14 '13 at 13:19
• What you've written in the first line is not an identity: there is no equals sign! – Brian M. Scott Aug 14 '13 at 13:19
• @DonAntonio: It's unreasonable to expect someone who may never have used $\LaTeX$ to write it here on his very first question. He did in fact write the expression unambiguously, which is as much as one can reasonably expect. – Brian M. Scott Aug 14 '13 at 13:22
• Please check that I correctly interpreted the additions in your last edit. – Brian M. Scott Aug 14 '13 at 13:27

## 2 Answers

Consider $(1+x)^n (1-x)^n \equiv (1-x^2)^n$, and compare coefficient of $x^n$ term.

\begin{align} \text{Left hand side} =& \sum_{i=0}^{n} \binom{n}{n-i} \left[\binom{n}{i} \left( -1 \right)^{i} \right] &\text{(From the expanded terms)}\\ =& \sum_{i=0}^{n} \binom{n}{i}^2 \left( -1 \right)^{i}\\ \end{align}

For right hand side, you can easily find the coefficient of $x^n$ from the binomial expansion

$$\left( 1-x^2 \right)^n = \sum_{i=0}^n \binom{n}{i} \left( -x^2 \right)^i$$

• See, all the terms in right hand side are in the form of $x^{2i}$. – peterwhy Aug 14 '13 at 13:50

First, \begin{align} &(1+x)^n(1-x)^n\\ &=\left(\sum_{k=0}^n\binom{n}{k}x^k\right) \left(\sum_{j=0}^n\binom{n}{j}(-1)^jx^j\right)&&\text{binomial theorem}\\ &=\sum_{m=0}^{2n}\left(\sum_{i=0}^n\binom{n}{m-i}\binom{n}{i}(-1)^i\right)x^m&&\text{power series convolution}\\ &=\sum_{m=0}^n\left(\sum_{i=0}^n\binom{n}{2m-i}\binom{n}{i}(-1)^i\right)x^{2m}&&\text{even terms}\tag{1a}\\ &+\sum_{m=0}^{n-1}\left(\sum_{i=0}^n\binom{n}{2m+1-i}\binom{n}{i}(-1)^i\right)x^{2m+1}&&\text{odd terms}\tag{1b} \end{align} Next, use $(1+x)(1-x)=1-x^2$ : \begin{align} \left(1-x^2\right)^n &=\sum_{m=0}^n\binom{n}{m}(-1)^mx^{2m}&&\text{binomial theorem}\tag{2} \end{align} Just compare the coefficients from the even and odd terms $(1)$ to those from the $(2)$ to get $$\sum_{i=0}^n\binom{n}{2m-i}\binom{n}{i}(-1)^i=(-1)^m\binom{n}{m}\tag{3}$$ and $$\sum_{i=0}^n\binom{n}{2m+1-i}\binom{n}{i}(-1)^i=0\tag{4}$$ If $n$ is even, use $(3)$ and set $m=\dfrac n2$. If $n$ is odd, use $(4)$ and set $m=\dfrac{n-1}{2}$.