5
$\begingroup$

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

  • 0
    for n = 2 i get 0 = 2 from the first formula so it seems ill-formed. Please check the formula2012-04-14
  • 0
    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.2012-04-15
  • 1
    This is very similar to your last question. What is the source for this? Can you tell us what you've tried?2012-04-15
  • 0
    The fomula is from the Laplace work. Tge formula I need is very similar, so probably, one can deduse it from Laplace' formula2012-04-16
  • 0
    What "Laplace work"? Try to meet us halfway, won't you?2012-04-16
  • 0
    Laplace, theorie analytique des probabilitied, paris, 1812, p. 1712012-04-16
  • 1
    Maybe this link http://math.stackexchange.com/q/66901/23993 will be of help.2012-04-16

3 Answers 3

3

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.

  • 0
    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.2015-06-20
  • 0
    I have verified the above answer and found it to be sound. Therefore I am awarding the bounty.2015-06-24
1

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.

1

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.