Para todos

Question

Cómo probar que $(n+1)(n+2)\cdots(2n)$ es divisible por $2^n$, para cada una de las $n\in\Bbb N$?

Estoy bastante confundido de cómo comenzar y terminar la prueba usando inducción matemática. Traté de responder a ella, pero no estoy seguro de si es lo correcto. Alguien me puede ayudar por favor?

Esta es mi prueba:

Caso Base Cuando $n=1$, $(1+1)=2\implies1=1$. Desde $2\in\Bbb N$ es divisible por $2^1$, la declaración sostiene al $n=1$.

Inducción Supongamos que el enunciado es cierto para algunos $n=k$. $$2^k\mid(k+1)(k+2)\cdots(2k)$$ Vamos a demostrar que también se aplica a las $n=k+1$. Tenemos $$2^{k+1} \mid [(k+1) + 1] [(k+1) + 2]\cdots[2(k+1)]\tag{target!}$$ $$2^{k+1}\mid (k+2)(k+3)\cdots(2k+2)$$

Ahora $$(k+1) (k+2) \cdots (2k+2) = 2^k(2k+2) = 2^k(2k) + 2^k(2) = 2^k(2k) + 2^k+1$$ y no sé cómo continuar a partir de aquí.

Answer 1

Que $P_n=(n+1)\times(n+2)\times \dots \times(2n)$

base caja: es divisible por $2$ $2^1$

Paso inductivo: $P_{n+1}=P_n\frac{(2n+1)\times(2n+2)}{n+1}$. Ya que siempre es par $2^n\mid P_n$ solo tenemos que mostrar $\frac{(2n+1)\times(2n+2)}{n+1}$, que es claramente cierto, desde $\frac{(2n+1)\times(2n+2)}{n+1}=(2n+1)\times 2$

Answer 2

Tenemos un teorema: % Let $x$ser una privilegiada. El poder de $x$ que divide $n!$

$$\left[\frac{n}{x}\right]+\left[\frac{n}{x^2}\right]+\cdots+\left[\frac{n}{x^k}\right]+\cdots$ $ por lo que es el poder de $2$ que divide $(n+1)\cdots(2n)$

$$\left(\left[\frac{2n}{2}\right]+\left[\frac{2n}{4}\right]+\cdots\right) - \left(\left[\frac{n}{2}\right]+\left[\frac{n}{4}\right]+\cdots\right) = n$$

Answer 3

Sólo por diversión, quiero dar un argumento combinatorio mediante acciones del grupo y de la órbita estabilizador.

El grupo $L=(\mathbb{Z}/2\mathbb{Z})^n$ actúa en $Y=\{1,\ldots,n\}\cup\{1',\ldots,n'\}$ cuando la $k$th vector coordenado actúa como la transposición $(kk')$. Denotar $X=\{1,\ldots,n\}$ y deje $F$ ser el conjunto de todas las funciones inyectiva $X\to Y$. A continuación, $L$'s de acción en $Y$ induce una acción de $L$ $F$ que es gratis, por lo tanto cada órbita tiene el mismo tamaño, por lo $|L|$ divide $|F|$.

---

Aquí está mi intento de frase los argumentos sin grupo de acciones.

Deje $F$ ser el conjunto de todas las secuencias de $(a_1,\ldots,a_n)$ $n$ elementos distintos de a $\{1,\ldots,n,1',\ldots,n'\}$ (que tiene dos copias de cada número $1$ a través de $n$, sólo el extra de copias de los números primos en ellos). Podemos establecer una relación de equivalencia en $F$, $x\sim y$ siempre $x$ $y$ son de la misma tupla después de quitar todos los números primos. Uno puede comprobar que cada clase de equivalencia ha $2^n$ elementos, y no se $(2n)(2n-1)\cdots(n+1)$-muchos elementos en $F$, a partir de la cual el resultado de la siguiente manera.

Answer 4

Solo por ser diferente. (En serio inducción como por Llevar Sonriendo solución es la manera más fácil.)

$(n+1)......(2n)$ tendrá aproximadamente el $n/2$ incluso números. Así que si nos factor de $2$ de cada uno de los términos, a continuación, $2^{n/2}$ factores. La expresión tendrá aproximadamente el $n/4$ números divisibles por $4$. Si nos factor de $2$ fuera de los términos que con conseguir ese $2^{n/2}*2^{n/4}$ factores.

Volvemos a repetir para obtener $2^{n/2}*2^{n/4}*2^{n/8}*.... = 2^{n(1/2 + 1/4 + 1/8 + ....)} = 2^{n*1}$.

Aproximadamente.

Bueno... por lo que el diablo está en los detalles, a la derecha.

Deje $n = \sum_{i = 0}^k b_i 2^i;b_i = \{0|1\}$ ser la representación binaria de $n$.

A continuación,$2n = \sum_{i = 0}^k b_i 2^{i+1}$.

Entre el $1$ $2n$ hay $ \sum_{i = 0}^k b_i 2^{i}$ incluso números. Entre el $1$ $n$ hay $\sum_{i=1}^k b_i 2^{i-1}$ incluso números. Así que entre el $n + 1$ $n$ hay $b_0 + \sum_{i=1}^k bi*(2^{i} - 2{i-1}) = b_0 + \sum_{i=1}^k bi*2^{i-1}$ número par.

Asimismo, entre el $n+1$ $2n$ no se $b_1 + \sum_{i=2}^k bi*2^{i-2}$ números divisibles por $4$.

Y entre el $n+1$ $2n$ no se $b_{m-1} + \sum_{i=m}^k bi*2^{i-m}$ números divisibles por $2^m$.

Por lo $2^{\sum_{m=1}^k (b_{m-1} + \sum_{i=m}^k bi*2^{i-m})}$ divide $(n+1)....2n$.

Sigue siendo para mostrar $\sum_{m=1}^k (b_{m-1} + \sum_{i=m}^k bi*2^{i-m})= n$.

Bien..... $\sum_{m=1}^k (b_{m-1} + \sum_{i=m}^k bi*2^{i-m})=$

$\sum_{m=1}^k (b_{m-1} + \lfloor n/2^m \rfloor)=$

$b_0 + (b_1 + \lfloor n/2 \rfloor) + (b_2 + \lfloor n/4 \rfloor) + ....=$

$b_0 + (b_1 + b_1 + 2\lfloor n/4 \rfloor)+ (b_2 + b_2 + 2\lfloor n/8 \rfloor) + ....=$

$b_0 + b_1*2+ 2\lfloor n/4 \rfloor)+ (b_2*2 + 2\lfloor n/8 \rfloor) + ....=$

$b_0 + b_1*2+ 2*b_2 + 4\lfloor n/8 \rfloor)+ (b_2*2 + 2*b_3 + 4\lfloor n/16 \rfloor) + ....=$

$b_0 + b_1*2+ b_2*2^2 + 2*b_3 + 4\lfloor n/8 \rfloor)+ ( 2*b_3 + 4\lfloor n/16 \rfloor) + ....=$

.....

$b_0 + b_1*2 + b_2*2^2 + b_3*2^3 + .... = n$.

Bueno... yo dije que la inducción fue más fácil.

Pero lo que espero haber demostrado que es una idea de por qué esto funciona. es decir, que dividiendo $2$ $n/2$ incluso los números y, a continuación, otro $2$ $n/4$ números divisibles por $4$, por lo que en dividimos $2$ aproximadamente $n/2 + n/4 + .... = n$ veces lo $2^n$ es un factor.

Answer 5

$\newcommand{\ángulos}[1]{\left\langle\,{#1}\,\right\rangle} \newcommand{\llaves}[1]{\left\lbrace\,{#1}\,\right\rbrace} \newcommand{\bracks}[1]{\left\lbrack\,{#1}\,\right\rbrack} \newcommand{\dd}{\mathrm{d}} \newcommand{\ds}[1]{\displaystyle{#1}} \newcommand{\expo}[1]{\,\mathrm{e}^{#1}\,} \newcommand{\mitad}{{1 \over 2}} \newcommand{\ic}{\mathrm{i}} \newcommand{\iff}{\Longleftrightarrow} \newcommand{\imp}{\Longrightarrow} \newcommand{\Li}[1]{\,\mathrm{Li}_{#1}} \newcommand{\mc}[1]{\mathcal{#1}} \newcommand{\mrm}[1]{\mathrm{#1}} \newcommand{\ol}[1]{\overline{#1}} \newcommand{\pars}[1]{\left(\,{#1}\,\right)} \newcommand{\partiald}[3][]{\frac{\partial^{#1} #2}{\parcial #3^{#1}}} \newcommand{\raíz}[2][]{\,\sqrt[#1]{\,{#2}\,}\,} \newcommand{\totald}[3][]{\frac{\mathrm{d}^{#1} #2}{\mathrm{d} #3^{#1}}} \newcommand{\ul}[1]{\underline{#1}} \newcommand{\verts}[1]{\left\vert\,{#1}\,\right\vert}$ \begin{align} &\color{#f00}{\pars{n + 1}\pars{n + 2}\ldots\pars{2n}} = {\pars{2n}! \over n!} = {\Gamma\pars{2n + 1} \over \Gamma\pars{n + 1}} = 2\,{\Gamma\pars{2n} \over \Gamma\pars{n}}\qquad\qquad\pars{~Recurrence~} \\[5mm] = &\ 2\,{1 \over \root{\pi}}\,2^{2n - 1}\,\,\Gamma\pars{n + \half} \qquad\qquad\pars{~Duplication\ Formula~} \end{align}

---

\begin{align} &\color{#f00}{\pars{n + 1}\pars{n + 2}\ldots\pars{2n} \over 2^{n}} = {1 \over \root{\pi}}\,2^{n}\,\Gamma\pars{n + \half} \\[5mm] = &\ {2^{n} \over \root{\pi}}\,\pars{n - \half}\Gamma\pars{n - \half} = {2^{n} \over \root{\pi}}\,\pars{n - \half}\pars{n - {3 \over 2}} \Gamma\pars{n - {3 \over 2}} \\[5mm] = &\ \cdots = {2^{n} \over \Gamma\pars{1/2}}\,\pars{n - \half}\pars{n - {3 \over 2}}\ldots \half\,\Gamma\pars{\half}\qquad\quad \pars{~\mbox{Note that}\ \Gamma\pars{\half} = \root{\pi}~} \\[5mm] = &\ {2^{n} \over \Gamma\pars{1/2}}\,\pars{n - \half}\pars{n - {3 \over 2}}\ldots \half\,\Gamma\pars{\half}\\[5mm] = &\ 2^{n}\ \overbrace{{2n - 1 \over 2}\,{2n - 3 \over 2}\ldots{2n - \pars{2n - 1} \over 2}} ^{\ds{n\ \mbox{terms}}} \end{align}

---

$$ \color{#f00}{\pars{n + 1}\pars{n + 2}\ldots\pars{2n} \over 2^{n}} = \color{#f00}{\pars{2n - 1}!!}\ \en\ \mathbb{N} $$