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} \ ...$$


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.

  • $\begingroup$ Thank you! How did you get the coefficient of $x^n$? $\endgroup$ – Robben Jan 22 '15 at 4:21
  • $\begingroup$ @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$ $\endgroup$ – sciona Jan 22 '15 at 4:23
  • 1
    $\begingroup$ I see. Thank you! $\endgroup$ – Robben Jan 22 '15 at 4:24

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.