prueba de fórmula y suma de cálculo

Question

Demuestre que la siguiente fórmula es verdadera:

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

Utilizando la fórmula calcular $$ \sum_{i=0}^n(2i-n)^p{p \choose i} $$

Answer 1

Demostramos por inclusión/exclusión que $$\sum_{i=0}^n (-1)^i (c-k i)^n \binom ni = k^n n!$$ para cualquier número entero $n$ y complejo $c$ . (¡Honestamente!) Dado esto, toma $c=n$ y $k=2$ , nótese que en este caso el término con $i=n/2$ desaparece (si existe), y su fórmula sigue.

Este es el argumento de inclusión/exclusión. En primer lugar, supongamos que $c>k n$ es un número entero, y que $S_1,\ldots, S_n$ ser disjuntos $k$ -tuplas en $[c]=\{1,\ldots,c\}$ . Contamos todas las funciones de $[n]$ a $[c]$ de manera que el rango de $f$ se cruza con cada $S_j$ . Por un lado, es evidente que hay $k^n n!$ tales funciones (para cada $j$ Hay un único $i$ tal que $f(i)\in S_j$ y hay $k$ posibilidades de $f(i)$ en $S_j$ ). Por otro lado, el número de funciones $f:[n]\to [c]$ que echan de menos una determinada colección de $i$ de la $S_j$ es $(c-k i)^n$ , así que hemos terminado por inclusión/exclusión.

Está claro que la respuesta no depende de $c$ Siempre y cuando $c$ es suficientemente grande. Pero el lado izquierdo es un polinomio finito en $c$ por lo que debe ser un polinomio constante, y por lo tanto se puede elegir $c$ de forma arbitraria.

Answer 2

Supongamos que queremos evaluar

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

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

y además introducir $$[[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.$$

Este es un soporte Iverson que asegura que podemos ampliar el alcance de la suma desde $\lfloor n/2 \rfloor$ a $n.$

Obtenemos para la suma $$\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.$$

Esto es $$\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 .$$

Llama a esta integral $J_1.$

Una representación alternativa de la suma es $$S_2 = (-1)^n \sum_{q=\lfloor n/2 \rfloor+1}^n {n\choose q} (-1)^q (2q-n)^n.$$

El soporte de Iverson se convierte ahora en $$[[\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.$$

Obtenemos para la suma $$(-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.$$

Esto es $$(-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 .$$

Llama a esta integral $J_2.$

Mediante la anulación del $w^{n+1}$ factor esto es $$- (-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 .$$

Ahora pon $z=-v$ para conseguir $$(-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 .$$

De ello se desprende que $$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 .$$

Esto es $$-\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.$$

Ahora tenemos dos casos, a saber $q=n$ y $q\lt n$ . Cuando $q=n$ obtenemos la 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.$$

La serie para $1-\exp(-2z)$ comienza con $2z$ para que al extraer el residuo en $z$ obtenemos $$-\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.$$

Queda por demostrar que la siguiente integral es cero: $$-\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.$$

Esto es $$-\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$$

que se ve que es cero por inspección ya que la potencia máxima del $w-1$ El término es $n-1$ y estamos extrayendo el $w^n$ coeficiente.

Hemos demostrado que $2S = 2^n \times n!$ y por lo tanto $$S = 2^{n-1} \times n!$$ como se ha reclamado.

Se utilizó una técnica similar en este Enlace MSE I y esto Enlace MSE II .

Answer 3

A modo de comentario sobre la respuesta de @Tad parece que en retrospectiva que la clave está en darse cuenta de que

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

que es trivial una vez que se ve (reindexar $q$ por $n-q$ ) pero se me escapó atención mientras trabajaba en el problema.

Por supuesto, la suma

$$\sum_{q=0}^n (-1)^q (c-kq)^n {n\choose q}$$ es fácil de evaluar algebraicamente (variables complejas).

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

Esto da como resultado para la suma $$\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.$$

Desde $1-\exp(-kz)$ comienza en $kz$ el residuo es $k^n$ para una respuesta final de $k^n \times n!.$

El defecto de mi primera respuesta fue que no vi la simetría en la suma.