Para $n \ge 4$ ¿se deduce que ${{3n} \choose {n}} > 4^n$

Question

Creo que la respuesta es sí. Esto es lo que pienso:

(1) Para $n \ge 4, { {2n} \choose {n}} \ge \frac{4^n}{n}$

Por inducción: $64 = \frac{4^4}{4} \le {{8}\choose{4}}= 70$ . Supongamos que es cierto hasta $n-1 \ge 4$ . Entonces, ${ {2n} \choose n} = 2\left(\frac{2n-1}{n}\right){{2n-1}\choose{n-1}} > 2\left(\frac{2n-1}{n}\right)\frac{4^{n-1}}{n-1} > 2 \cdot 2\cdot \frac{4^{n-1}}{n} = \frac{4^n}{n}$

Nota: Este argumento fue tomada de Wikipedia.

(2) $(3n-1) > \left(\frac{3}{2}\right)(2n-1), (3n-2) > \left(\frac{3}{2}\right)(2n-2), \dots, (2n-n+1) > \left(\frac{3}{2}\right)(2n-n+1)$

Si $2a = 3b$ entonces $2a - 2 > 3b - 3$ y $2(a-1) > 3(b-1)$ para que $(a-1) > \frac{3}{2}(b-1)$

(3) Para $n\ge 2$ , ${{3n}\choose{n}} > \left(\frac{3}{2}\right)^n{{2n} \choose {n}}$

A partir de (2): ${{3n} \choose{n}} = \frac{(3n)(3n-1)\dots(3n-n+2)(3n-n+1)}{n!} > \left(\frac{3}{2}^n\right)\frac{(2n)(2n-1)\dots(2n-n+2)(2n-n+1)}{n!} = \left(\frac{3}{2}^n\right){{2n} \choose {n}}$

(4) Ya que para $n \ge 4, \left(\frac{3}{2}\right)^n > n$ se deduce que:

${{3n}\choose{n}} > \left(\frac{3}{2}\right)^n{{2n}\choose{n}} > n\left(\frac{4^n}{n}\right) = 4^n $

Nota: El argumento de que para $n \ge 2, \left(\frac{3}{2}\right)^n > n$ se puede encontrar aquí .

Answer 1

Incluso es cierto para $n\ge3$ . En efecto, $\;\dbinom 93=\dfrac{9!}{3!\,6!}=84 >64$ .

\begin {align} & \text {A continuación, tenemos } \qquad\qquad & \binom {3(n+1)}{n+1}&= \binom {3n}n, \frac {(3n+1)(3n+2)(3n+3)}{(n+1)(2n+1)(2n+2)},&& \qquad\qquad\end {align} así que, por inducción, todo lo que tenemos que demostrar es que $$\frac{3(3n+1)(3n+2)}{2(n+1)(2n+1)}\ge4$$ Esta desigualdad equivale a $$ 27n^2+27n+6\ge 16n^2+24n+8\iff 11n^2+3n\ge 2, $$ lo cual es obviamente cierto si $n \ge 1$ .

Answer 2

Tenemos las siguientes aproximaciones de Stirling:

• $\sqrt{2\pi n}n^ne^{-n} \leq n! \leq e \sqrt{n} n^n e^{-n} $ para todos $n \in \mathbb{N}$ $${{3n} \choose {n}} \geq \frac{\sqrt{2\pi 3n}(3n)^{3n}e^{-3n}}{e \sqrt{n} n^n e^{-n} \cdot e \sqrt{2n} (2n)^{2n} e^{-2n}} =\frac{\sqrt{3\pi}}{e^2\sqrt{n}} \frac{27^n}{4^n} > \frac{\sqrt{3\pi}}{e^2} \frac{\left(\frac{3}{2}\right)^n}{\sqrt{n}}4^n$$ Por lo tanto, si $n$ es lo suficientemente grande, la desigualdad se mantiene.

Answer 3

Un argumento combinatorio

Dividir $3n$ elementos distintivos en $n$ grupos, cada uno de los cuales contiene 3 elementos. Para elegir $n$ elmentos fuera de ellos, hay muchas maneras, incluyendo las siguientes categorías:

1) elegir un elemento de cada grupo, lo que da $3^{n}$ diferentes maneras

2) elegir un elemento de cada grupo para $n-k$ grupo, luego elija $k$ de los restantes $k$ grupos, de modo que cada grupo de los restantes $k$ grupos contribuye a $0$ elementos o al menos $2$ elementos. Esto da ${ n \choose {n-k}}3^{n-k} A_k$ formas, donde $A_k$ es la forma de elegir $k$ de los restantes $k$ grupos, de modo que cada grupo de los restantes $k$ grupos contribuye a $0$ elementos o al menos $2$ elementos. Evidentemente, $A_k \ge 1$ , a excepción de $k=1$ tenemos $A_1=0$

Hay que tener en cuenta que las formas anteriores son exlcusivas para diferentes $k$ .

Con ${ n \choose {n-2}}3^{n-2} A_2 = { n \choose {n-2}}3^{n-2} 6 = n(n-1)3^{n-1}\ge 3^{n-1} n + \frac{n(n-1)}{2}3^{n-2}$ (la última desigualdad es equivalente a $5n-11\ge 0$ )

tenemos

${ {3n} \choose {n}} \ge 3^n + \sum_{k=2}^n { n \choose {n-k}}3^{n-k} A_k\ge \sum_{k=0}^n { n \choose {n-k}}3^{n-k} =(3+1)^n =4^n$

Answer 4

Su pensamiento me parece correcto. He aquí un enfoque similar: Los casos $n=4,5$ se puede comprobar a mano. Para $n\geq6$ tenemos $n!\leq\left(\frac{n}{2}\right)^n$ lo que se demuestra fácilmente por inducción, y por lo tanto $$\binom{3n}{n}=\frac{(3n)!}{(2n)!n!}=\prod_{i=k}^n\frac{2n+k}{k}=\prod_{k=1}^n\left(1+\frac{2n}{k}\right)>2^n\frac{n^n}{n!}\geq4^n,$$ donde la primera desigualdad proviene del hecho de que $1+\frac{2n}{k}>\frac{2n}{k}$ para todos $k$ .