17 votos

En informática: $ \gcd \left({2n \choose 1}, {2n \choose 3},\cdots, {2n \choose 2n-1}\right)$

Me gustaría calcular

$$ d=\gcd \left({2n \choose 1}, {2n \choose 3},\cdots, {2n \choose 2n-1}\right) $$

Tenemos:

$$ \sum_{k=0}^{n-1}{2n \choose 2k+1}=2^{2n-1} $$

$$ d=2^k, 0\leq k\leq2n-1 $$

...

¿Alguna idea?

10voto

Adjit Puntos 172

Deje $q = 2^i$ donde$2^i | 2n$$2^{i+1} \not|2n$. Reclamo: $d=q$.

En primer lugar vamos a mostrar que cada plazo ${2n \choose 2k+1}$ $0 \leq k \leq n-1$ $q$ como un factor. Considerar,

$$\begin{align*} {2n \choose 2k+1} &= \frac{(2n)(2n-1)(2n-2) \cdots (2n- [2k+1] + 1)}{(2k+1)(2k)(2k-1)\cdots(1)}\\ &= \frac{2n}{2k+1} \cdot {2n-1 \choose 2k}\\ &= \frac{2n{2n-1 \choose 2k}}{2k+1} \end{align*}$$

Desde $k \leq n-1$, $2k < 2n-1$, y el número de ${2n-1 \choose 2k}$ es un número entero distinto de cero. Ahora desde ${2n \choose 2k+1}$ es un número entero, sabemos que $2k+1$ divide el numerador. No hay factores de $2$$2k+1$, por lo tanto, $q$ debe sobrevivir para ser un factor de ${2n \choose 2k+1}$.

Segundo nos muestran que $d \leq q$. Sabemos al menos que $q$ $d$ comparten la misma de mayor potencia de 2, ya que una de las condiciones es ${2n \choose 1} = 2n$. Ahora como Andre señala en los comentarios, esto significa que hemos terminado en este punto. Desde OP demostrado que $d$ es una potencia de 2, tenemos $d=q$.

4voto

DiGi Puntos 1925

He aquí un breve argumento de la segunda parte de Shaun prueba.

Supongamos que $p$ es una extraña primer dividiendo $2n$, decir $2n = mp^k$ donde $p\nmid m$. Entonces yo reclamo que

$$\begin{align*} \binom{2n}{p^k}&=\frac{(2n)!}{p^k!(2n-p^k)!}\\ &=\frac{(mp^k)!}{p^k!((m-1)p^k)!}\\ &=\frac1{p^k!}\prod_{i=0}^{p^k-1}(mp^k-i)\\ &=m\prod_{i=1}^{p^k-1}\frac{(m-1)p^k+i}i \end{align*}$$

no es divisible por $p$. Claramente $p\nmid m$. Si $1\le i\le p^k-1$, vamos a $p^s$ ser el más alto poder de $p$ dividiendo $(m-1)p^k+i$. A continuación,$s<k$$p^s\mid i$, por lo que el factor de $$\frac{(m-1)p^k+i}i$$ contributes no factor of $p$ to $\dbinom{2n}{p^k}$. Thus, $p\nmid d$.

Por otro lado, $d\mid 2n$, por lo que cualquier factor principal de $d$ debe dividir $2n$. De ello se desprende que $d$ no tiene impar de factores primos y, por ende (por la primera parte de Shaun prueba) que $d$ es el más alto poder de $2$ dividiendo $2n$.

i-Ciencias.com

I-Ciencias es una comunidad de estudiantes y amantes de la ciencia en la que puedes resolver tus problemas y dudas.
Puedes consultar las preguntas de otros usuarios, hacer tus propias preguntas o resolver las de los demás.

Powered by:

X