Prove $ 2\cdot5\cdot11\cdot19\cdot23\cdot29\cdot31>3^{16} $

Question

I recently came across the following problem:

If $C_n=\frac{1}{n+1}\binom{2n}{n}$ is the $n$-th catalan number, then prove that for all $n\ge 17$: $$ C_n>3^n $$ How the induction step works is quite clear, but the base case troubles me (I want to do it by hand):

If we cancel down the appearing fraction, it comes down to proving: $$ 2\cdot5\cdot11\cdot19\cdot23\cdot29\cdot31>3^{16} $$ I tired to bound the numbers on the right hand side by powers of three, but nothing seemed to work. Then I thought maybe it isn't feasible in a reasonable amount of time and got the following result:

Even if we take the inequality to the power of $1000$ and find the optimal integer bounds $(2\cdot5\cdot11)^{1000}>3^{4278}$, $(19\cdot23)^{1000}>3^{5534}$ and $(29\cdot31)^{1000}>3^{6190}$ we only obtain $2\cdot5\cdot11\cdot19\cdot23\cdot29\cdot31>3^{16.002}$.

So it seems indeed that it isn't feasible. However, can you think of a way to prove it; maybe using starlings approximation?

Answer 1

How about this one? $$ \frac{11.23}{3^5}\frac{2.5}{3^2}\frac{29}{3^3}\frac{31}{3^3}\frac{19}{3^2} > 3 $$ To prove that: $$ A = \frac{11.23}{3^5}\frac{2.5}{3^2}\frac{29}{3^3}\frac{31}{3^3}\frac{19}{3^2} = (1+\frac{10}{3^5})(1+\frac{1}{3^2})(1+\frac{2}{3^3})(1+\frac{4}{3^3})(2+\frac{1}{3^2}) $$ and $$ (1+\frac{10}{3^5})(1+\frac{1}{3^2})= 1+\frac{10}{3^5}+\frac{1}{3^2}+\frac{10}{3^7}>1+\frac{10}{3^5}+\frac{1}{3^2}+\frac{9}{3^7}=1+\frac{38}{3^5} $$ also $$ (1+\frac{2}{3^3})(1+\frac{4}{3^3})=1+\frac{6}{3^3}+\frac{8}{3^6}>1+\frac{2}{3^2}+\frac{6}{3^6}=1+\frac{56}{3^5} $$ so replacing we get $$ A > (1+\frac{38}{3^5})(1+\frac{56}{3^5})(2+\frac{1}{3^2}) = (1+\frac{94}{3^5}+\frac{38.56}{3^{10}})(2+\frac{1}{3^2}) > (1+\frac{94}{3^5}+\frac{38.54}{3^{10}})(2+\frac{1}{3^2}) = (1+\frac{94}{3^5}+\frac{38.2}{3^{7}})(2+\frac{1}{3^2}) > (1+\frac{94}{3^5}+\frac{25}{3^{6}})(2+\frac{1}{3^2}) = (1+\frac{307}{3^6})(2+\frac{1}{3^2})= 2 + \frac{307.2}{3^6}+\frac{1}{3^2}+\frac{307}{3^8} > 2 + \frac{307.2}{3^6}+\frac{1}{3^2}+\frac{306}{3^8} = 3 $$ Done

Answer 2

You can estimate as follows:

$29\times 31=900-1$, $19\times 23 =441-4$, $2\times 5 \times 11=110$

So $$2\times 5\times 11\times 19\times 23\times29\times 31=110\times 900\times 441-110\times 4\times 900-110\times 441+4\times 110$$

The leading term is about 1% too high by comparison with the other terms, and is equal to $3^4\times 110\times 100\times 49=3^4\times 539,000$

Now $3^6=729$ and $729^2=531,441$ (or do $81^3=6561\times 81$ if it is easier).

You can put the pieces together to get a good enough estimate. Possibly easier to do the straightforward complete calculation, though.

Answer 3

Here's a proof using logarithms and exponentials that gets by with calculations up to $3^{10}$:

$$ 2\cdot5\cdot11\cdot19\cdot23\cdot29\cdot31\gt3^{16}\\ \Leftrightarrow \frac{10}{3^2}\cdot\frac{253}{3^5}\cdot\frac{29}{3^3}\cdot\frac{31}{3^3}\gt\frac{3^3}{19}\\ \Leftrightarrow\left(1+\frac1{3^2}\right)\left(1+\frac{10}{3^5}\right)\left(1+\frac2{3^3}\right)\left(1+\frac4{3^3}\right)\gt\frac{3^3}{19} $$

With $\log(1+x)\gt x-\frac12x^2$ for $x\gt0$, we get

\begin{eqnarray} &&\log\left(\left(1+\frac1{3^2}\right)\left(1+\frac{10}{3^5}\right)\left(1+\frac2{3^3}\right)\left(1+\frac4{3^3}\right)\right)\\ &\gt&\frac1{3^2}+\frac{10}{3^5}+\frac2{3^3}+\frac4{3^3}-\frac12\left(\left(\frac1{3^2}\right)^2+\left(\frac{10}{3^5}\right)^2+\left(\frac2{3^3}\right)^2+\left(\frac4{3^3}\right)^2\right)\\ &=&\frac{41777}{2\cdot3^{10}}\\ &=&\frac{19}{2\cdot3^3}+\frac{112}{3^{10}}\;, \end{eqnarray}

and then exponentiating again and using $\mathrm e^x\gt1+x+\frac12x^2+\frac16x^3$ yields

\begin{eqnarray} &&\left(1+\frac1{3^2}\right)\left(1+\frac{10}{3^5}\right)\left(1+\frac2{3^3}\right)\left(1+\frac4{3^3}\right)\\ &\gt&\exp\left(\frac{19}{2\cdot3^3}+\frac{112}{3^{10}}\right)\\ &\gt&1+\frac{19}{2\cdot3^3}+\frac{108}{3^{10}}+\frac12\left(\frac{19}{2\cdot3^3}\right)^2+\frac16\left(\frac{18}{2\cdot3^3}\right)^3\\ &=&\frac{24875}{2^3\cdot3^7}\\ &\gt&\frac{24867}{2^3\cdot3^7}\\ &=&\frac{307}{2^3\cdot3^3}\\ &\gt&\frac{3^3}{19}\;. \end{eqnarray}