La prueba de una identidad que involucra factoriales

Question

He tropezado con la siguiente declaración y de haber comprobado que sea computacionalmente para muchos $n$ (hasta n=500, se tomó un tiempo largo para mi equipo para hacer todas las matemáticas), pero no tengo idea de cómo ir sobre la prueba.

$$\sum _{ i=0 }^{ n } \sum _{ j=0 }^{ n } \frac { { ((2n)! })^{ 2 }(-1)^{ i+j }(2i+2j)! }{ (n-i)!(n-j)!(2i)!(2j)!2^{ i+j }(i+j)! } =\frac { (4n)! }{ { 4 }^{ n }(2n)! } $$

Una cosa a tener en cuenta es que si multiplicamos la parte superior y la parte inferior de la fracción por $(i)!$, $(j)!$, y $(n!)^2$, a continuación, algunos de los términos simplificar en el factorial definición del coeficiente binomial, por lo que la suma es también se puede expresar como:

$$\sum _{ i=0 }^{ n } \sum _{ j=0 }^{ n } (-1)^{ i+j } \binom{n}{i}\binom{n}{j} \frac { { ((2n)! })^{ 2 }}{(n!)^2}\frac{(i)!}{(2i)!}\frac{(j)!}{(2j)!}\frac{(2i+2j)! }{2^{ i+j }(i+j)! } =\frac { (4n)! }{ { 4 }^{ n }(2n)! } $$

También, vamos a definir $P(n)$ a ser igual al producto de la primera $n$ positivo números impares (o más específicamente, $P(n)=(2n-1)!!$). Podemos utilizar la fórmula explícita $P(n)=\frac{(2n)!}{2^n n!}$ (véase aquí para una explicación) para reescribir diversas expresiones: $$\frac{(2i+2j)! }{2^{ i+j }(i+j)! }=P(i+j)$$ $$\frac{((2n)!)^2}{(n!)^2}=(P(n))^2 2^{2n}$$ $$\frac{(i)!}{(2i)!}=\frac{1}{2^i P(i)}$$ $$\frac{(4n)!}{4^{n}(2n)!}=P(2n)$$

Y así, la declaración puede ser reescrita como: $$ \sum _{ i=0 }^{ n } \sum _{ j=0 }^{ n } (-1)^{ i+j } \binom{n}{i}\binom{n}{j} \frac{2^{2n}(P(n))^2 P(i+j)}{2^{i+j}P(i)P(j)}=P(2n) $$

Curiosamente, esto demuestra que la izquierda debe ser un número entero (véase aquí para una explicación), que creo que es un paso en la dirección correcta.

Todo esto es sólo cosas al azar que he estado tratando de intentar demostrar la identidad, aunque hasta ahora no he llegado muy lejos. Si alguien tiene alguna idea de cómo podría demostrar esta identidad o incluso empezar a probar la identidad, por favor, ayúdenme! Cualquier ayuda es muy apreciada!

Editar, aquí es más el trabajo realizado sobre el tema:

Vamos a definir: $$R_n = \sum _{ i=0 }^{ n } \sum _{ j=0 }^{ n } \frac { { ((2n)! })^{ 2 }(-1)^{ i+j }(2i+2j)! }{ (n-i)!(n-j)!(2i)!(2j)!2^{ i+j }(i+j)! }$$

Actualmente estoy tratando de demostrar que $R_n=P(2n)$. Desde $P(n)$ es el producto de la primera $n$ enteros impares, y $2n-1$ $n$th entero impar, se deduce que el $P(2(n+1))=P(2n+2)=P(2n) \cdot (4n+1) \cdot (4n+3)$. Por lo tanto (ya que el caso base funciona, y puede confirmar que si usted realmente quiere), una declaración equivalente a lo que estoy tratando de demostrar es: $$R_{n+1}=(4n+1)(4n+3)R_{n}$$

Answer 1

La ecuación

$$ \sum_{i = 0}^{n}\sum_{j = 0}^{n} (-1)^{i + j} \binom{n}{i} \binom{n}{j} \frac{2^{2n}(P(n))^{2}P(i + j)}{2^{i+j}P(i)P(j)} = P(2n) $$

es un primer sospechoso de la combinatoria de prueba (prueba combinatoria). La idea sería encontrar una cantidad que ambos lados están contando.

En particular, la cantidad de $\binom{n}{i}\binom{n}{j}$ es lo que sugiere la naturaleza de la suma. Si nos vamos a $$f(i, j) = (-1)^{i + j}\frac{2^{2n} P(n)^{2} P(i + j)}{2^{i+j} P(i)P(j)}$$ a continuación, se reduce a $$ \sum_{i = 0}^{n}\sum_{j = 0}^{n}\binom{n}{i}\binom{n}{j}f(i,j) $$ Esta es entonces una suma de $f(i,j)$ sobre un conjunto muy particular: el conjunto de dos piezas particiones de subconjuntos de a $\{1,2,\dots 2n\}$. Este conjunto es menos complicado de lo que parece: cualquier elemento es tan sólo un par de subconjuntos, uno de $\{1, 2, \dots n\}$ y el otro de $\{n + 1, n+2, \dots 2n\}$. Por qué esto tiene sentido no es claro.

Como para la simplificación $f(i,j)$, se puede romper en pedazos. La primera cosa a notar es que el $2^{i + j}$. El número de subconjuntos de un conjunto con $k$ elementos es $2^{k}$ (más información). Por lo tanto, podríamos considerar que $$\frac{2^{2n}}{2^{i+j}} = 2^{2n - i - j} = (2^{n - i})(2^{n - j})$$ puede ser una buena manera de descomponer. A continuación, la cantidad representa el número de subconjuntos de los elementos restantes después de la extracción $i$ desde el primer $n$ $j$ a partir del segundo.

También, esto sugiere que el origen de $(-1)^{i + j}$. Cuando se suma a más de ciertos conjuntos de subconjuntos, nos topamos con signo cambia por el principio de inclusión-exclusión (también conocido como el PASTEL).

La importancia de $\left(P(n)^2 \frac{P(i + j)}{P(i)P(j)}\right)$, entonces es un poco más claro. Considerar la relación entre el$P(2n)$$P(n)^{2}$. Desde $P$ es no lineal, la diferencia es análogo a un crossterm (e.g $(x+y)^{2} - (x^{2} + y^{2})$). Por lo tanto, la suma se puede cuantificar el tamaño de este crossterm. De hecho, si nos movemos $P(n)^{2}$ hacia el otro lado, obtenemos:

$$ \sum_{i = 0}^{n}\sum_{j = 0}^{n} \binom{n}{i} \binom{n}{j} \left((-1)^{i + j} \cdot 2^{2n - i - j}\right) \frac{P(i + j)}{P(i)P(j)} = \frac{P(n + n)}{P(n)P(n)} $$

O, dejando $g(i,j) = \frac{P(i + j)}{P(i)P(j)}$,

$$ \sum_{i = 0}^{n}\sum_{j = 0}^{n} \binom{n}{i} \binom{n}{j} \left((-1)^{i + j} \cdot 2^{2n - i - j}\right) g(i,j) = g(n,n) $$

Este todavía no tiene una interpretación clara, pero se está haciendo allí. El siguiente paso sería encontrar una concreta interpretación a uno de $P$ o $g$ (una interpretación de la otra, es probable que siga).

Actualización:

Resulta que para números enteros $g$ tiene una especialmente bonita interpretación. Tenga en cuenta que $$ (2k)!! = (2k)(2k-2) \dots (4)(2) = 2^{k}[(k)(k-1) \dots (2)(1)] = 2^{k} k! $$ Por lo tanto, $$ g(2i,2j) = \frac{2^{i+j}(i+j)!}{2^{i}2^{j} \ i! \ j!} = \frac{(i+j)!}{i! \ j!} = \binom{i+j}{i} $$ que es el número de $i$ elemento de subconjuntos de a $\{1, 2, \dots i+j\}$. Por desgracia, no funciona tan bien para los enteros impares ($g(i,j)$ no suele ser un número entero cuando al menos uno de $i, j$ es impar).

El doble factorial tiene un número de interpretaciones, especialmente para valores impares (ver wikipedia). También de uso potencial es un papel relevante acerca de las identidades (de Una combinatoria de la encuesta de identidades para el doble factorial).

Answer 2

Considere el polinomio $$ f_n(x)=\left(x^2+1-\frac{\left(x+1\right)^2}{2}\right)^{2n}. $$ El lado izquierdo y derecho de la OP la identidad de cada uno de calcular el coeficiente de $x^{2n}$$f_n(x)$.

Por un lado, podemos expandir $f_n$ utilizando el trinomio binomial y teoremas: \begin{align*} f_n(x)&=\sum_{a+b\leq 2n}\frac{(2n)!}{a!b!(2n-a-b)!}x^{2a}\left(x+1\right)^{2(2n-a-b)}\frac{(-1)^{2n-a-b}}{2^{2n-a-b}}\\ &=\sum_{\substack{a+b\leq 2n\\r\leq 4n-2a-2b}}\frac{(2n)!}{a!b!(2n-a-b)!}{4n-2a-2b\choose r}\frac{(-1)^{2n-a-b}}{2^{2n-a-b}}x^{2a+r}. \end{align*} Para obtener $x^{2n}$, tenemos $r=2n-2a$, por lo que el $a\leq n$. Además, $r=2n-2a$ $r\leq 4n-2b-2b$ implican $b\leq n$, por lo que estamos sumando más de $0\leq a,b\leq n$. Hacer la sustitución $i=n-a$, $j=n-b$ (de modo que $r=2i$). En términos de$i$$j$, la suma es $0\leq i,j\leq n$. Esto muestra que el coeficiente de $x^{2n}$ es el lado izquierdo de la OP de la identidad.

Por otro lado, podemos simplificar $f_n$: \begin{align*} f_n(x)&=\left(\frac{(x-1)^2}{2}\right)^{2n}\\ &=\frac{(x-1)^{4n}}{4^n}. \end{align*} El teorema del binomio, a continuación, se muestra el coeficiente de $x^{2n}$ es el lado derecho de la OP de la identidad.

Answer 3

Vamos, $$S_1(n)=\sum _{ i=0 }^{ n } \sum _{ j=0 }^{ n } \frac { { ((2n)! })^{ 2 }(-1)^{ i+j }(2i+2j)! }{ (n-i)!(n-j)!(2i)!(2j)!2^{ i+j }(i+j)! } \\ S_2(n) =\frac { (4n)! }{ { 4 }^{ n }(2n)! } $$
Observe que $S_1(0)=S_2(0) = 1$. En segundo lugar observar primaria manipulaciones que, $$ S_2(n+1) = (1+4n)(3+4n)S_2(n)$$ Sustituto $S_1(n)$ en el mismo recurrencia y observar también satisface, $$S_1(n+1) = (1+4n)(3+4n)S_1(n)$$ Las dos secuencias, $S_1$$S_2$, de acuerdo al $n=0$ y uno puede calcular su $(n+1)^\textrm{th}$ valores de la misma recurrencia debe ser que las dos secuencias de acuerdo para todas las $n$ por inducción. Uno llega a la conclusión de que, $S_1(n) = S_2(n)$.

Comentarios adicionales: para ayudar A la comprensión voy a seguir boceto de cómo comprobar la recurrencia de $S_1$. Quiero evitar tener que escribir interminablemente, así que no va a dar a todos el álgebra. También el ejercicio es mucho más difícil que de costumbre!

Inicio de $S_1(n+1)$ y empezar a manipular, $$ S_1(n+1) = \sum _{ i=0 }^{ n+1 } \sum _{ j=0 }^{ n+1 } \frac { { ((2n+2)! })^{ 2 }f(i,j)}{ (n+1-i)!(n+1-j)!} $$ Aquí $f(i,j)$ " sólo se usa para acortar expresiones. Comparar para arriba para una definición. Continuando, $$ S_1(n+1) = \sum _{ i=0 }^{ n+1 } \sum _{ j=0 }^{ n+1 } \frac { { ((2n+2)! })^{ 2 }f(i,j)}{ (n+1-i)!(n+1-j)!}\\ = \sum _{ i=0 }^{ n+1 }\left[ \frac { { ((2n+2)! })^{ 2 }f(i,n+1)}{ (n+1-i)!}+ \la suma de _{ j=0 }^{ n } \frac { { ((2n+2)! })^{ 2 }f(i,j)}{ (n+1-i)!(n+1-j)!}\right]\\ = \sum _{ i=0 }^{ n+1 }\left[ \sum _{ j=0 }^{ n } \frac { { ((2n+2)! })^{ 2 }f(i,n+1)}{ (n+1) (n+1-i)!}+ \frac { { ((2n+2)! })^{ 2 }f(i,j)}{ (n+1-i)!(n+1-j)!}\right]\\ =\left[ \sum _{ j=0 }^{ n } \frac { { ((2n+2)! })^{ 2 }f(n+1,n+1)}{ (n+1)}+ \frac { { ((2n+2)! })^{ 2 }f(n+1,j)}{ (n+1-j)!}\right]+ \sum _{ i=0 }^{ n}\left[ \sum _{ j=0 }^{ n } \frac { { ((2n+2)! })^{ 2 }f(i,n+1)}{ (n+1) (n+1-i)!}+ \frac { { ((2n+2)! })^{ 2 }f(i,j)}{ (n+1-i)!(n+1-j)!}\right]\\ = \sum _{ i=0 }^{ n} \sum _{ j=0 }^{ n }\frac { { ((2n+2)! })^{ 2 }f(n+1,n+1)}{ (n+1)^2}+ \frac { { ((2n+2)! })^{ 2 }f(n+1,j)}{ (n+1)(n+1-j)!}+ \frac { { ((2n+2)! })^{ 2 }f(i,n+1)}{ (n+1) (n+1-i)!}+ \frac { { ((2n+2)! })^{ 2 }f(i,j)}{ (n+1-i)!(n+1-j)!} $$ La colocación de esta en la recurrencia, poniendo el polinomio en la parte frontal de $S_1(n)$ debe dar una suma doble. El doble de la suma de hecho, se desvanece y mi equipo está haciendo actualmente el álgebra para demostrar que...