Demostrar que $2^n < \binom{2n}{n} < 2^{2n}$

Question

Demostrar que $2^n < \binom{2n}{n} < 2^{2n}$. Esto es demostrado con bastante facilidad, dividiéndolo en dos partes y, a continuación, probar cada parte por inducción.

Primera parte: $2^n < \binom{2n}{n}$. La base de la $n = 1$ es trivial. Asumir de forma inductiva que algunos $k$ satisface nuestra declaración. El paso inductivo puede ser demostrado de la siguiente manera.

$2^k < \binom{2k}{k} \implies 2^{k+1} < 2\binom{2k}{k} = \frac{2(2k)!}{k!k!} = \frac{2(2k)!(k + 1)}{k!k!(k + 1)} = \frac{2(2k)!(k+2)}{(k+1)!k!}<\frac{(2k)!(2k+2)(2k+1)}{(k+1)!k!(k+1)} = \binom{2(k+1)}{k+1}$

Segunda parte: $2^{2n} > \binom{2n}{n}$. De nuevo, la base es trivial. Podemos suponer que para algunos $k$ nuestra declaración es satisfecho y demostrar que paso inductivo de la siguiente manera:

$2^{2k} > \binom{2k}{k} \implies 2^{2k + 2} > 2^2\binom{2k}{k} = \frac{2\cdot2(2k)!}{k!k!} = \frac{2\cdot2(2k)!(k+1)(k+1)}{k!k!(k+1)(k+1)} = \frac{(2k)!(2k+2)(2k+2)}{(k+1)!(k+1)!} > \frac{(2k)!(2k+1)(2k+2)}{(k+1)!(k+1)!} = \binom{2(k+1)}{k+1}$

Hay un no-inductivo de derivación para la desigualdad?

Answer 1

A ver que $\binom{2n}{n} < 2^{2n}$, aplicar el teorema del binomio $$2^{2n} = (1+1)^{2n} = \sum_{k=0}^{2n} \binom{2n}{k} > \binom{2n}{n}.$$

A ver que $2^n < \binom{2n}{n}$, escribe como un producto de $$\binom{2n}{n} = \frac{2n}{n} \cdot \frac{2n-1}{n-1} \cdot ... \cdot \frac{n+1}{1},$$ where each factor is $\ge 2$, and for $n > 1$, some factors are strictly greater than $2$. The claim is not true if $n=1$.

Answer 2

Como he dicho en un comentario, esto sólo es cierto para $n>1$. Para $n=1$, usted tiene $2^1=\binom 21$.

Puramente enfoque combinatorio.

Deje $S$ ser un conjunto con $n$ elementos. Deje $T=S\times\{1,2\}$. Deje $R=\{X\subset T:\left|X\right|=n\}$. Entonces usted necesita mostrar que:

$$\left|\mathcal P(S)\right|< \left|R\right| < \left|\mathcal P(T)\right|$$

Donde $\mathcal P(Y)$ es el juego de poder de $Y$.

Ahora, $R\subsetneq \mathcal P(T)$, por lo que realmente sólo necesitan demostrar el lado izquierdo.

Definir $f:\mathcal P(S)\to R$ $X\subseteq S$ por:

$$f(X)=\{(x,1):x\in X\}\cup \{(x,2):x\in S\setminus X\}$$

A continuación,$f$$1-1$, por lo que todo lo que realmente necesita es que no está en. Pero es fácil llegar con elementos de $R$ no en la imagen de $f$ al $n>1$.

Otra forma de obtener el lado izquierdo de la desigualdad es:

$$\binom{2n}{n}=\sum_{k=0}^n\binom{n}{k}^2 >\sum_{k=0}^n\binom{n}{k}=2^n$$

La ecuación que se utiliza aquí para $\binom {2n}{n}$ es bastante conocido y demostrado fácilmente, y el segundo paso es sólo cierto para $n>1$, de nuevo.

Estos son muy aproximada de los límites para la $\binom{2n}{n}$. En realidad, tenemos que $$\binom{2n}{n}\sim \frac{2^{2n}}{\sqrt{n\pi}}$$

Answer 3

Para la segunda parte de la nota que $$2^{2n}=(1+1)^{2n}=1+\binom {2n}1 +\dots + \binom {2n}n+\dots\gt \binom{2n}n$$

Answer 4

Para la primera parte, no necesitamos la inducción como en la $$\binom {2n}n=\prod_{0\le r\le n-1}\frac{2n-r}{n-r}=2\prod_{1\le r\le n-1}\frac{2n-r}{n-r}>2\cdot 2^{n-1}$$ and $2n-r>2(n-r)$ for $r>0$

Answer 5

Combinatoria argumento:

Tome $n$ pares de la gente, que es $2n$ personas en total, y entonces usted puede elegir:

• una persona de cada par en $2^n$ formas,
• cualquier $n$ de los individuos en $\binom{2n}{n}$ formas,
• cualquier subconjunto de esas personas en $2^{2n}$ maneras.

Espero que esta ayuda ;-)