# Evaluate a sum using generating function and use Inclusion-Exclusion to prove identity

I need to evaluate the following sum using generating functions, and then find some counting argument to prove the resulting identity using inclusion-exclusion principle. \begin{align} \sum_{k=0}^n(-1)^k{n \choose k}(n-k) \end{align} It looks like a binomial convolution so I tried using that to obtain an identity but I can't seem to get the right one.

I have found that this sum evaluates to 0 for any $n$

## 1 Answer

Let $$a_n=\sum_{k=0}^n(-1)^k\binom{n}k(n-k)\;,$$

and let $$A(x)=\sum_{n\ge 0}a_n\frac{x^n}{n!}\;;$$

as you say, it appears that $A(x)$ is the binomial convolution of a couple of exponential generating functions. One of these is apparently

$$f(x)=\sum_{n\ge 0}(-1)^n\frac{x^n}{n!}=\sum_{n\ge 0}\frac{(-x)^n}{n!}=e^{-x}\;,$$

and the other is

$$g(x)=\sum_{n\ge 0}n\frac{x^n}{n!}=\sum_{n\ge 1}\frac{x^n}{(n-1)!}=x\sum_{n\ge 0}\frac{x^n}{n!}=xe^x\;.$$

Thus,

$$A(x)=f(x)g(x)=(e^{-x})(xe^x)=x\;,$$

and it follows that $a_1=1$, and $a_n=0$ if $n\ne 1$. Using an Iverson bracket we can say that

$$\sum_{k=0}^n(-1)^k\binom{n}k(n-k)=[n=1]\;.$$

To see this as an instance of the inclusion-exclusion principle it may be helpful to write out the first few terms of the sum:

$$\binom{n}0n-\binom{n}1(n-1)+\binom{n}2(n-2)-+\ldots$$

It appears that we’re starting with a crude count of $n$; as a first improvement we’re subtracting $n-1$ for each of $n$ things, and the second correction is adding $n-2$ for each pair of things from a set of $n$. One way to get these terms is to let $H_n$ be the set of maps $h:[n]\to[n]$ such that

• $h$ is the identity map, and
• $h$ is a constant function.

It’s not hard to see that $H_n=\varnothing$ if $n\ne 1$, and $H_n$ contains the unique map from $\{1\}$ to $\{1\}$ if $n=1$, so $|H_n|=a_n$ for all $n\ge 0$. The term $\binom{n}0n=n$ counts the constant functions from $[n]$ to $[n]$. The first condition requires that $h(k)=k$ for each $k\in[n]$; thus, for each $k\in[n]$ there are $n-1$ constant functions that have to be thrown away, and there are $\binom{n}1$ choices for $k$, so the first correction term is $-\binom{n}1(n-1)$. Now if $k,\ell\in[n]$ and $k\ne\ell$, any constant function that maps $[n]$ to one of the $n-2$ elements of $[n]\setminus\{k,\ell\}$ violates the first condition for both $k$ and $\ell$, so it’s been thrown away twice and needs to be added back in; there are $\binom{n}2$ pairs of distinct elements of $[n]$, so the second correction term is $\binom{n}2(n-2)$. And so on. I’ll leave it to you to clean this up and express it properly as an inclusion-exclusion argument in whatever form you’re most familiar with.