# Combinatorial Identities

I am trying to prove the following identities:

a. $$\sum_{k=0}^n(-1)^k{n\choose k}^2 = \bigg\{^{0 \ \text{if k is odd}}_{(-1)^m{2m\choose m} \ \text{if n = 2m}}$$

b. $$\sum^k_{i=0} {n+i \choose i}={n+k+1\choose k}$$

For part $b$ I know I can use induction. It is clearly true when $k=0$ and then assuming for $k-1$ we get $$\sum^k_{i=0}{n+i\choose i}={n+k\choose k-1}+{n+k \choose k}={n+k+1\choose k} \ ...$$

## 1 Answer

We have $\displaystyle (1+x)^n(1-x)^n=\left( \sum_{k=0}^n \binom{n}{k}x^k \right)\left( \sum_{k=0}^n (-1)^k\binom{n}{k}x^k \right)$

The coefficient of $x^n$ is $\displaystyle \sum_{k=0}^n (-1)^k\binom{n}{k}\binom{n}{n-k}$.

But we also have: $\displaystyle (1+x)^n(1-x)^n=(1-x^2)^n=\left(\sum_{k=0}^n \binom{n}{k}(-1)^kx^{2k} \right)$

Thus, the coefficient of $x^n$ is $0$ if $n$ odd and $\displaystyle (-1)^{\frac{n}2}\binom{n}{n/2}$ if $n$ is even.

• Thank you! How did you get the coefficient of $x^n$? – Robben Jan 22 '15 at 4:21
• @Robben multiplying the coefficient of $x^k$ from $\left( \sum_{k=0}^n (-1)^k\binom{n}{k}x^k \right)$ and $x^{n-k}$ from $\left( \sum_{k=0}^n \binom{n}{k}x^k \right)$ for each $k = 0,1, \cdots, n$ – sciona Jan 22 '15 at 4:23
• I see. Thank you! – Robben Jan 22 '15 at 4:24