# proof of formula and calculation sum

Show that following formula is true:

$$\sum_{i=0}^{[n/2]}(-1)^i (n-2i)^n{n \choose i}=2^{n-1}n!$$

Using formula calculate $$\sum_{i=0}^n(2i-n)^p{p \choose i}$$

• for n = 2 i get 0 = 2 from the first formula so it seems ill-formed. Please check the formula – Comic Book Guy Apr 14 '12 at 23:53
• So, why do you think the formula is true? Why do you think you can use it to calculate the second sum? Did you read this somewhere? If so, you could tell us where, it might help us get some traction. – Gerry Myerson Apr 15 '12 at 9:20
• This is very similar to your last question. What is the source for this? Can you tell us what you've tried? – Antonio Vargas Apr 15 '12 at 23:17
• The fomula is from the Laplace work. Tge formula I need is very similar, so probably, one can deduse it from Laplace' formula – Michael Apr 16 '12 at 2:46
• Maybe this link math.stackexchange.com/q/66901/23993 will be of help. – David Apr 16 '12 at 5:11

We show by inclusion/exclusion that $$\sum_{i=0}^n (-1)^i (c-k i)^n \binom ni = k^n n!$$ for any integer $n$ and complex $c$. (Honestly!) Given this, take $c=n$ and $k=2$, note that in this case the term with $i=n/2$ vanishes (if there is one), and your formula follows.

Here's the inclusion/exclusion argument. First suppose $c>k n$ is an integer, and let $S_1,\ldots, S_n$ be disjoint $k$-tuples in $[c]=\{1,\ldots,c\}$. We count all functions from $[n]$ to $[c]$ such that the range of $f$ intersects each $S_j$. On the one hand, there are clearly $k^n n!$ such functions (for each $j$, there's a unique $i$ such that $f(i)\in S_j$, and there are $k$ possibilities for $f(i)$ within $S_j$). On the other hand, the number of functions $f:[n]\to [c]$ which miss a given collection of $i$ of the $S_j$'s is $(c-k i)^n$, so we're done by inclusion/exclusion.

It's clear that the answer doesn't depend on $c$, as long as $c$ is sufficiently large. But the left-hand side is a finite polynomial in $c$, so it must be a constant polynomial, and therefore you can pick $c$ arbitrarily.

• Thank you for this answer. Please consult my second answer for a verification of your result. I will probably award the bounty but I need to reflect on the inclusion-exclusion argument. – Marko Riedel Jun 20 '15 at 19:39
• I have verified the above answer and found it to be sound. Therefore I am awarding the bounty. – Marko Riedel Jun 24 '15 at 20:22

By way of commentary on the answer by @Tad it appears in retrospect that the key is to realize that

$$\sum_{q=0}^{\lfloor n/2 \rfloor} {n\choose q} (-1)^q (n-2q)^n = \sum_{q=\lfloor n/2 \rfloor+1}^n {n\choose q} (-1)^q (n-2q)^n$$

which is trivial once you see it (reindex $q$ by $n-q$) but escaped my attention as I worked on the problem.

Of course the sum

$$\sum_{q=0}^n (-1)^q (c-kq)^n {n\choose q}$$ is easy to evaluate algebraically (complex variables).

Just introduce $$(c-kq)^n = \frac{n!}{2\pi i} \int_{|z|=\epsilon} \frac{1}{z^{n+1}} \exp((c-kq)z) \; dz.$$

This yields for the sum $$\frac{n!}{2\pi i} \int_{|z|=\epsilon} \frac{1}{z^{n+1}} \sum_{q=0}^n {n\choose q} (-1)^q \exp((c-kq)z) \; dz \\ = \frac{n!}{2\pi i} \int_{|z|=\epsilon} \frac{1}{z^{n+1}} \exp(cz) \sum_{q=0}^n {n\choose q} (-1)^q \exp(-kqz) \; dz \\ = \frac{n!}{2\pi i} \int_{|z|=\epsilon} \frac{1}{z^{n+1}} \exp(cz) \left(1-\exp(-kz)\right)^n \; dz.$$

Since $1-\exp(-kz)$ starts at $kz$ the residue is $k^n$ for a final answer of $k^n \times n!.$

The defect of my first answer was that I did not see the symmetry in the sum.

Suppose we seek to evaluate

$$S_1 = \sum_{q=0}^{\lfloor n/2 \rfloor} {n\choose q} (-1)^q (n-2q)^n.$$

Introduce $$(n-2q)^n = \frac{n!}{2\pi i} \int_{|z|=\epsilon} \frac{1}{z^{n+1}} \exp((n-2q)z) \; dz$$

and furthermore introduce $$[[0\le q \le \lfloor n/2 \rfloor]] = \frac{1}{2\pi i} \int_{|w|=\epsilon} \frac{1+w+w^2+\cdots+w^{\lfloor n/2 \rfloor}}{w^{q+1}} \; dw \\ = \frac{1}{2\pi i} \int_{|w|=\epsilon} \frac{w^{\lfloor n/2 \rfloor+1}-1}{(w-1)w^{q+1}} \; dw.$$

This is an Iverson bracket that ensures that we may extend the range of the sum from $\lfloor n/2 \rfloor$ to $n.$

We get for the sum $$\frac{n!}{2\pi i} \int_{|z|=\epsilon} \frac{1}{z^{n+1}} \frac{1}{2\pi i} \int_{|w|=\epsilon} \frac{w^{\lfloor n/2 \rfloor+1}-1}{(w-1)w} \\ \times \sum_{q=0}^{n} {n\choose q} (-1)^q \exp((n-2q)z) \frac{1}{w^q} \; dw \; dz \\ = \frac{n!}{2\pi i} \int_{|z|=\epsilon} \frac{\exp(nz)}{z^{n+1}} \frac{1}{2\pi i} \int_{|w|=\epsilon} \frac{w^{\lfloor n/2 \rfloor+1}-1}{(w-1)w} \\ \times \sum_{q=0}^{n} {n\choose q} (-1)^q \exp(-2qz) \frac{1}{w^q} \; dw \; dz.$$

This is $$\frac{n!}{2\pi i} \int_{|z|=\epsilon} \frac{\exp(nz)}{z^{n+1}} \frac{1}{2\pi i} \int_{|w|=\epsilon} \frac{w^{\lfloor n/2 \rfloor+1}-1}{(w-1)w} \left(1-\frac{\exp(-2z)}{w}\right)^n \; dw \; dz \\ = \frac{n!}{2\pi i} \int_{|z|=\epsilon} \frac{\exp(nz)}{z^{n+1}} \frac{1}{2\pi i} \int_{|w|=\epsilon} \frac{w^{\lfloor n/2 \rfloor+1}-1}{(w-1)w^{n+1}} \left(w-\exp(-2z)\right)^n \; dw \; dz .$$

Call this integral $J_1.$

An alternate representation of the sum is $$S_2 = (-1)^n \sum_{q=\lfloor n/2 \rfloor+1}^n {n\choose q} (-1)^q (2q-n)^n.$$

The Iverson bracket now becomes $$[[\lfloor n/2 \rfloor+1\le q\le n]] = \frac{1}{2\pi i} \int_{|w|=\epsilon} \frac{w^{\lfloor n/2 \rfloor+1}+\cdots+w^n}{w^{q+1}} \; dw \\ = \frac{1}{2\pi i} \int_{|w|=\epsilon} w^{\lfloor n/2 \rfloor+1} \frac{w^{n-\lfloor n/2 \rfloor}-1}{(w-1)w^{q+1}} \; dw.$$

We get for the sum $$(-1)^n \frac{n!}{2\pi i} \int_{|z|=\epsilon} \frac{1}{z^{n+1}} \frac{1}{2\pi i} \int_{|w|=\epsilon} w^{\lfloor n/2 \rfloor+1} \frac{w^{n-\lfloor n/2 \rfloor}-1}{(w-1)w} \\ \times \sum_{q=0}^{n} {n\choose q} (-1)^q \exp((2q-n)z) \frac{1}{w^q} \; dw \; dz \\ = (-1)^n \frac{n!}{2\pi i} \int_{|z|=\epsilon} \frac{\exp(-nz)}{z^{n+1}} \frac{1}{2\pi i} \int_{|w|=\epsilon} w^{\lfloor n/2 \rfloor+1} \frac{w^{n-\lfloor n/2 \rfloor}-1}{(w-1)w} \\ \times \sum_{q=0}^{n} {n\choose q} (-1)^q \exp(2qz) \frac{1}{w^q} \; dw \; dz.$$

This is $$(-1)^n \frac{n!}{2\pi i} \int_{|z|=\epsilon} \frac{\exp(-nz)}{z^{n+1}} \frac{1}{2\pi i} \int_{|w|=\epsilon} w^{\lfloor n/2 \rfloor+1} \frac{w^{n-\lfloor n/2 \rfloor}-1}{(w-1)w} \\ \times \left(1-\frac{\exp(2z)}{w}\right)^n \; dw \; dz \\ = (-1)^n \frac{n!}{2\pi i} \int_{|z|=\epsilon} \frac{\exp(-nz)}{z^{n+1}} \frac{1}{2\pi i} \int_{|w|=\epsilon} w^{\lfloor n/2 \rfloor+1} \frac{w^{n-\lfloor n/2 \rfloor}-1}{(w-1)w^{n+1}} \\ \times \left(w-\exp(2z)\right)^n \; dw \; dz .$$

Call this integral $J_2.$

By cancellation of the $w^{n+1}$ factor this is $$- (-1)^n \frac{n!}{2\pi i} \int_{|z|=\epsilon} \frac{\exp(-nz)}{z^{n+1}} \frac{1}{2\pi i} \int_{|w|=\epsilon} \frac{1}{(w-1)w^{n-\lfloor n/2 \rfloor}} \left(w-\exp(2z)\right)^n \; dw \; dz .$$

Now put $z=-v$ to get $$(-1)^n \frac{n!}{2\pi i} \int_{|v|=\epsilon} \frac{\exp(nv)}{(-1)^{n+1} v^{n+1}} \frac{1}{2\pi i} \int_{|w|=\epsilon} \frac{1}{(w-1)w^{n-\lfloor n/2 \rfloor}} \\ \times\left(w-\exp(-2v)\right)^n \; dw \; dv \\ = - \frac{n!}{2\pi i} \int_{|v|=\epsilon} \frac{\exp(nv)}{v^{n+1}} \frac{1}{2\pi i} \int_{|w|=\epsilon} \frac{1}{(w-1)w^{n-\lfloor n/2 \rfloor}} \\ \times\left(w-\exp(-2v)\right)^n \; dw \; dv .$$

It follows that $$J_1+J_2 = 2S \\ = -\frac{n!}{2\pi i} \int_{|z|=\epsilon} \frac{\exp(nz)}{z^{n+1}} \frac{1}{2\pi i} \int_{|w|=\epsilon} \frac{1}{(w-1)w^{n+1}} \left(w-\exp(-2z)\right)^n \; dw \; dz .$$

This is $$-\frac{n!}{2\pi i} \int_{|z|=\epsilon} \frac{\exp(nz)}{z^{n+1}} \frac{1}{2\pi i} \int_{|w|=\epsilon} \frac{1}{(w-1)w^{n+1}} \\ \times \sum_{q=0}^n {n\choose q} (w-1)^{n-q} (1-\exp(-2z))^q \; dw \; dz.$$

Now we have two cases namely $q=n$ and $q\lt n$. When $q=n$ we get the integral $$-\frac{n!}{2\pi i} \int_{|z|=\epsilon} \frac{\exp(nz)}{z^{n+1}} \frac{1}{2\pi i} \int_{|w|=\epsilon} \frac{1}{(w-1)w^{n+1}} (1-\exp(-2z))^n \; dw \; dz.$$

The series for $1-\exp(-2z)$ starts with $2z$ so that on extracting the residue in $z$ we obtain $$-\frac{n!\times 2^n}{2\pi i} \int_{|w|=\epsilon} \frac{1}{(w-1)w^{n+1}} \; dw \\ = \frac{n!\times 2^n}{2\pi i} \int_{|w|=\epsilon} \frac{1}{(1-w)w^{n+1}} \; dw = n! \times 2^n.$$

It remains to show that the following integral is zero: $$-\frac{n!}{2\pi i} \int_{|z|=\epsilon} \frac{\exp(nz)}{z^{n+1}} \frac{1}{2\pi i} \int_{|w|=\epsilon} \frac{1}{(w-1)w^{n+1}} \\ \times \sum_{q=0}^{n-1} {n\choose q} (w-1)^{n-q} (1-\exp(-2z))^q \; dw \; dz.$$

This is $$-\frac{n!}{2\pi i} \int_{|z|=\epsilon} \frac{\exp(nz)}{z^{n+1}} \frac{1}{2\pi i} \int_{|w|=\epsilon} \frac{1}{w^{n+1}} \\ \times \sum_{q=0}^{n-1} {n\choose q} (w-1)^{n-q-1} (1-\exp(-2z))^q \; dw \; dz$$

which is seen to be zero by inspection since the maximum power of the $w-1$ term is $n-1$ and we are extracting the $w^n$ coefficient.

We have shown that $2S = 2^n \times n!$ and hence $$S = 2^{n-1} \times n!$$ as claimed.

A similar technique was used at this MSE link I and this MSE link II.