Demostrando $\binom{2n}{n}\le 4^n$ todos los $n$ por menor contraejemplo

Question

Probar $$\binom{2n}{n}\le 4^n$$ for all natural numbers $$ n, por más pequeño (mínimo) contraejemplo.

Mi intento:
Primero, $$\binom{2n}n = \frac{(2n)!}{(n!)^2} \le 4^n\;.$$ We know that $x\ne 0$ because $\frac{(2\cdot 0)!}{(0!)^2} = 1$ which is true. So $x\ge 2$. Now consider $x-1\en \Bbb, N$. Also note that $x-1 <x$ and is the smallest counterexample. So, $n=x-1$. $$\frac{(2(x-1))!}{((x-1)!)^2} \le 4^{x-1}$$ $$\frac{(2x-2)!}{((x-1)!)^2} \le 4^{x-1}$$

Así que esto es donde estoy atascado. ¿Debo seguir en la expansión? Si es así, ¿cómo?

Answer 1

No responde a la pregunta, ya que no utiliza un argumento inductivo, pero es más fácil la prueba de que el resultado real

Si usted tiene $2n$ objetos, a continuación, el número de todos los subets es $2^{2n}=4^n$. Ahora $2n \choose n$ son todos los subconjuntos de a $2n$ contiene $n $ elementos.

Answer 2

SUGERENCIA: para completar la prueba, usted necesita mostrar que la desigualdad $$\frac{(2x-2)!}{((x-1)!)^2} \le 4^{x-1}\tag{1}$$ implies that $$\frac{(2x)!}{x!^2}\le 4^x\;.$$

Ahora $$\frac{(2x)!}{x!^2}=\frac{2x(2x-1)(2x-2)!}{x^2(x-1)!^2}=\frac{2x(2x-1)}{x^2}\cdot\frac{(2x-2)!}{(x-1)!^2}\le\frac{2x(2x-1)}{x^2}\cdot4^{x-1}$$ by virtue of the hypothesis $(1)$. Que voy a hacer, si usted puede demostrar que

$$\frac{2x(2x-1)}{x^2}\le 4\;.$$

Se puede terminar ahora.

Answer 3

Recordar la Identidad de Pascal $\binom{m}{k}=\binom{m-1}{k}+\binom{m-1}{k-1}$. Esto puede ser demostrado por un breve cálculo con factoriales, o por una combinatoria argumento. O si por el contrario, podemos definir los coeficientes binomiales mediante el llamado Triángulo de Pascal, la identidad es verdad por definición. Por cierto, el "Pascal" triángulo era conocido en China siglos antes de Pascal. Incluso fue conocido en Europa. Pero estoy divagando.

Aplicar la Identidad de a $\binom{2n}{n}$, consiguiendo $\binom{2n}{n}=\binom{2n-1}{n}+\binom{2n-1}{n-1}$. A continuación, aplicar de nuevo a las dos partes. Tenemos $$\binom{2n}{n}= \binom{2n-2}{n}+\binom{2n-2}{n-1}+\binom{2n-2}{n-1}+\binom{2n-2}{n-2}.\tag{$1$}$$

Si $n$ es un mínimo contraejemplo, a continuación,$\binom{2n-2}{n-1} \le 4^{n-1}$. Hay dos términos en el lado derecho de la $(1)$, además de dos pequeños, desde la central de los coeficientes binomiales son máximas. De ello se desprende que el lado derecho, y por lo tanto el de la izquierda, es $\lt 4\cdot 4^{n-1}=4^n$, contradiciendo la suposición de que $n$ es un contraejemplo.