demostrar que $(2n)!/(n!)^2$ es incluso si $n$ es un número entero positivo

Question

Demostrar que $\frac{(2n)!}{(n!)^2}$ es incluso si $n$ es un número entero positivo.

Para mayor claridad : el denominador es la única parte que se eleva al cuadrado.

Mi proceso de pensamiento :

El numerador es el producto del primer $n$ incluso números y el producto de los primeros $n$ impar números.

Eso es, $(2n!) = (2n)(2n-2)(2n-4)\cdots(2n-1)(2n-3)(2n-5).$ En efecto, el producto de los números pares se puede anular con $n!$ dando como resultado el siguiente cociente: $$\frac{(2^n)(2n-1)(2n-3)}{(n!)}\;.$$ Para mí esto parece incluso gracias a los poderes de $2$ . Pero por alguna razón no me convence.

¿Este enfoque era ingenuo?

Perdón por la mala notación, no conozco ningún lenguaje de codificación, mis disculpas.

Answer 1

Tenemos $$\displaystyle \frac{(2n)!}{(n!)^2} = \binom{2n}{n}$$ y por supuesto para cada forma de elegir una combinación de $n$ objetos de un total de $2n$ objetos, existe una opción complementaria (el sobrante $n$ objetos). Dado que las formas de elegir $n$ objetos de $2n$ viene en pares, se deduce que el número total es par.

Otra prueba: $$\frac{(2n)!}{(n!)^2} = \frac{ 2n \cdot (2n-1)! }{(n!)^2 } = 2 \cdot \frac{ n \cdot (2n-1)! }{ n\cdot (n-1)! \cdot n!} = 2 \cdot \frac{(2n-1)!}{n! (n-1)!} = 2 \binom{2n-1}{n}$$

Este puede ser escrito de otra manera (usando $\binom{n}{k} = \binom{n-1}{k-1} + \binom{n-1}{k}$ y la propiedad simétrica): $$\frac{(2n)!}{(n!)^2} = \binom{2n}{n} = \binom{2n-1}{n-1} + \binom{2n-1}{n} = 2\binom{2n-1}{n}.$$ Otra más: La suma de los $2n$ -la fila del triángulo de Pascal es $2^{2n}$ que es par, y la suma de todas las entradas excluyendo el coeficiente central también es par, debido a la propiedad simétrica $\displaystyle \binom{n}{k} = \binom{n}{n-k}$ . Por lo tanto, el coeficiente central también debe ser par.

---

Podemos exprimir un poco más este problema y aprender algo interesante con esta cuarta prueba. Ésta no requiere ningún conocimiento de los coeficientes binomiales. Para investigar los factores primos de los factoriales utilizamos la siguiente identidad: $$l = \sum_{k=1}^{\infty} \bigg\lfloor \frac{n}{p^k} \bigg\rfloor$$

donde $p$ es un número primo y $l$ es el único número natural tal que $p^l \mid n!$ pero $p^{l+1} \nmid n!.$ Básicamente esto cuenta la multiplicidad del factor primo $p$ en $n!$ .

La idea de la prueba es la siguiente: Escribir $n! = 1\cdot 2 \cdot 3 \cdots (n-1) \cdot n$ y pregúntese dónde están los factores de $p$ vienen de. Es evidente que se obtiene un factor de $p$ de $p, 2p, 3p, \cdots$ por lo que hay $\lfloor n/p \rfloor$ factores de $p$ de estos. Pero esa no es toda la historia - cuando revisamos los múltiplos $p,2p,3p\cdots$ no contamos el segundo factor de $p$ cada vez que había $p^2, 2p^2, 3p^2 \cdots$ así que viene otro $\lfloor n/p^2 \rfloor$ para añadir. Espera, no contamos otro factor cada vez que nos faltan cubos en $p^3, 2p^3,\cdots$ Así que añadimos otro $\lfloor n/p^3 \rfloor$ y así sucesivamente. Además, hay que tener en cuenta que esto puede parecer una serie infinita, pero eventualmente $p^k > n$ por lo que todos los términos acaban convirtiéndose en $0.$

En fin, volvamos al objetivo principal. Usando nuestra identidad, vemos que hay $$\sum_{k=1}^{\infty} \bigg \lfloor \frac{2n}{2^k} \bigg \rfloor - 2 \bigg \lfloor \frac{n}{2^k} \bigg \rfloor$$ factores de $2$ en $\displaystyle \frac{(2n)!}{ (n!)^2}$ y queremos demostrar que este número es al menos $1.$

Con un poco de trabajo fácil podemos ver que $$\lfloor 2x \rfloor - 2 \lfloor x \rfloor = \left\{ \begin{array}{lr} 1 & : \{ x\} \geq \frac{1}{2} \\ 0 & : \{ x\} < \frac{1}{2} \end{array} \right.$$ donde $\{ x \}$ denota la parte fraccionaria de $x.$ Así, nuestro problema se reduce a demostrar que existe algún $k\in \mathbb{N}$ tal que $\displaystyle \frac{n}{2^k}$ tiene una parte fraccionaria mayor o igual a $1/2.$ Por supuesto, esto es cierto, ya que si $m$ es el mayor número entero positivo tal que $\displaystyle \frac{n}{2^m} \geq 1$ entonces $\displaystyle \frac{1}{2} \leq \frac{n}{2^{m+1} } < 1.$ Por lo tanto, $\displaystyle \frac{(2n)!}{(n!)^2}$ está en paz.

Answer 2

A menudo es divertido intentar resolver estos problemas utilizando Teorema de Lagrange de la teoría de grupos finitos. Es decir, para demostrar que $a$ divide $b$ se intenta encontrar un grupo de cardinalidad $b$ con un subgrupo de cardinalidad $a$ .

En este caso, el grupo simétrico en $2n$ cartas, $S_{2n}$ es una opción obvia para un grupo de cardinalidad $(2n)!$ . Dejemos que $G\subset S_{2n}$ sea el conjunto de todas las permutaciones que mapean el conjunto $\{1,\ldots, n\}$ en $\{1,\ldots, n\}$ o $\{n+1,\ldots, 2n\}$ . Puede comprobar que $G$ es un subgrupo de $S_{2n}$ .

Para calcular la cardinalidad $\lvert G \rvert$ una opción es observar que $G\cong S_n\wr \mathbb{Z}_2$ Así que $\lvert G\rvert = \lvert S_n\rvert^{\lvert \mathbb{Z}_2\rvert} \lvert \mathbb{Z}_2\rvert = 2(n!)^2$ . Como alternativa, la elección de un elemento de $G$ corresponde a la elección de dos permutaciones de un conjunto de tamaño $n$ y la opción de intercambiar $\{1,\ldots,n\}$ con $\{n+1,\ldots, 2n\}$ o no, así que $\lvert G\rvert = 2(n!)^2$ .

Así, por el Teorema de Lagrange $2(n!)^2$ divide $(2n)!$ o en otras palabras, $\frac{(2n)!}{(n!)^2}$ está en paz.

Answer 3

Por el teorema del binomio , $$4^n=(1+1)^{2n}=\sum\limits_{k=0}^{2n}{2n\choose k}={2n\choose n}+\sum\limits_{k=0}^{n-1}{2n\choose k}+\sum\limits_{k=n+1}^{2n}{2n\choose k}.$$ Desde El triángulo de Pascal es simétrica, cada término de la suma de $k=0$ a $n-1$ coincide con un término de la suma de $k=n+1$ a $2n$ por lo que estas dos sumas son iguales y $$\frac{(2n)!}{(n!)^2}={2n\choose n}=4^n-2\cdot\sum\limits_{k=0}^{n-1}{2n\choose k}$$ es uniforme para cada $n\geqslant1$ .

Answer 4

Esta respuesta ha sido trasladada desde esta pregunta que se cerró porque se consideró que era un duplicado de esta pregunta.

El número de factores de un primo $p$ en $n!$ es $$\nu_p(n)=\left\lfloor\frac{n}{p}\right\rfloor+\left\lfloor\frac{n}{p^2}\right\rfloor+\left\lfloor\frac{n}{p^3}\right\rfloor+\dots\tag{1}$$ $\left\lfloor\frac{n}{p}\right\rfloor$ cuenta el número de múltiplos positivos de $p$ no mayor que $n$ pero sólo una vez. $\left\lfloor\frac{n}{p^2}\right\rfloor$ cuenta los múltiplos de $p^2$ una segunda vez, y $\left\lfloor\frac{n}{p^3}\right\rfloor$ los múltiplos positivos de $p^3$ una tercera vez, etc. Aplicando $(1)$ a la base- $p$ representación de $n$ $$n=\sum_{i=0}^kn_ip^i\tag{2}$$ donde $0\le n_i<p$ , produce $$\begin{align} \nu_p(n) &=\sum_{i=0}^kn_i\left(1+p+p^2+\dots+p^{i-1}\right)\\ &=\sum_{i=0}^kn_i\left(\frac{p^i-1}{p-1}\right)\\ &=\frac{1}{p-1}\left(n-\sum_{i=0}^kn_i\right)\\ &=\frac{n-\sigma_p(n)}{p-1}\tag{3} \end{align}$$ donde $\sigma_p(n)$ es la suma de la base- $p$ dígitos de $n$ .

Por lo tanto, el número de factores $p$ en $\displaystyle\binom{n}{k}=\frac{n!}{k!(n-k)!}$ es $$\begin{align} &\nu_p(n)-\nu_p(k)-\nu_p(n-k)\\ &=\frac{1}{p-1}\left(n-\sigma_p(n)-k+\sigma_p(k)-(n-k)+\sigma(n-k)\right)\\ &=\frac{\sigma_p(k)+\sigma_p(n-k)-\sigma_p(n)}{p-1}\tag{4} \end{align}$$ Utilizando $(4)$ con $p=2$ dice que el número de factores de $2$ en $\displaystyle\binom{2n}{n}$ es $\sigma_2(n)+\sigma_2(n)-\sigma_2(2n)$ que es simplemente $\sigma_2(n)$ desde $\sigma_2(n)=\sigma_2(2n)$ . Por lo tanto, el número de factores de $2$ en $\displaystyle\binom{2n}{n}$ es el número de $1$ -bits en la representación binaria de $n$ .

Así, si $n>0$ entonces hay al menos una $1$ -bit in $n$ en binario, y así $2$ divide $\displaystyle\binom{2n}{n}$ .

Answer 5

Observemos un ejemplo:

$(2\cdot 5)!=10\cdot 9 \cdot 8 \cdot 7 \cdot 6 \cdot 5!$ podemos concluir que:

$(2n)!=2n\cdot(2n-1)\cdot(2n-2)....(n+1)n!$ por lo que obtenemos la siguiente expresión :

$$\frac{2n\cdot(2n-1)\cdot(2n-2)....(n+1)}{n!}=\frac{2n\cdot(2n-1)\cdot2\cdot(n-1)\cdot(2n-3)\cdot 2 \cdot (n-2)....(n+1)}{n!}$$

$$=\frac{2\cdot2\cdot2...\cdot2\cdot n\cdot(n-1)\cdot(n-2)\cdot......\cdot 1\cdot(2n-1)\cdot(2n-3)\cdot......(n+1)}{n!}$$

$$=\frac{2\cdot2\cdot2...\cdot2 \cdot n!\cdot(2n-1)\cdot(2n-3)\cdot......\cdot (n+1)}{n!}=$$

$$=2\cdot2\cdot2...\cdot2 \cdot(2n-1)\cdot(2n-3)\cdot......\cdot (n+1)$$ por lo que el número es par.