Finding $n$ such that $\frac{3^n}{n!} \leq 10^{-6}$

This question actually came out of a question. In some other post, I saw a reference and going through, found this, $n>0$.

Solve for n explicitly without calculator: $$\frac{3^n}{n!}\le10^{-6}$$

And I appreciate hint rather than explicit solution.

Thank You.

-
$n!>10^6*3^n$ so $n!>10^6$. This gives a starting guess. – Maesumi Feb 1 '13 at 14:33
And what was the original question this came out from? – 1015 Feb 1 '13 at 14:38
This did not exactly come out of a question. Some one had posted an online solution list and the post I am talking about referred to some other question in the solution list. It's totally irrelevant. As for this question, it was about finding $N$ such that $\epsilon=10^{-6}$. You can guess the series and point of convergence right? – user45099 Feb 1 '13 at 14:42
A natural question it could come out from would be: how far do you need to go in the Taylor polynomial of $e^{-3}=\sum_{n\geq 0}(-3)^n/n!$ to make sure the approximation of $e^{-3}$ does not lead to an error greater than $10^{-6}$? – 1015 Feb 1 '13 at 14:46
Because this gives an alternating series of general term $(-1)^n3^n/n!$. For alternating series obeying Leibniz criterion, the error made when approximating by the first $n-1$ terms is not greater than the absolute value of the $n$-th term. Of course, this is no longer true when the general term is nonnegative, this is why I did not pick $+3$. – 1015 Feb 1 '13 at 15:18

Note that, for $n=3m$, $$3^{-3m}{(3m)!}=\left[m\left(m-\frac{1}{3}\right)\left(m-\frac{2}{3}\right)\right]\cdots\left[1\cdot\frac{2}{3}\cdot\frac{1}{3}\right] <\frac{2}{9}\left(m!\right)^3.$$ So you have to go at least far enough so that $$\frac{2}{9}\left(m!\right)^3>10^{6},$$ or $m! > \sqrt[3]{4500000} > 150$. So $m=5$ (corresponding to $n=15$) isn't far enough; the smallest $n$ satisfying your inequality will be at least $16$.

Similarly, for $n=3m+1$, $$3^{-3m-1}(3m+1)!=\left[\left(m+\frac{1}{3}\right)m\left(m-\frac{1}{3}\right)\right]\cdots \left[\frac{4}{3}\cdot1\cdot\frac{2}{3}\right]\cdot\frac{1}{3} < \frac{1}{3}(m!)^3,$$ so you need $m!>\sqrt[3]{3000000}> 140$, and $m=5$ (that is, $n=16$) is still too small.

Finally, for $n=3m+2$, $$3^{-3m-2}(3m+2)!=\left[\left(m+\frac{2}{3}\right)\left(m+\frac{1}{3}\right)m\right]\cdots \left[\frac{5}{3}\cdot\frac{4}{3}\cdot1\right]\cdot\frac{2}{3}\cdot\frac{1}{3} > \frac{560}{729}(m!)^3,$$ where the coefficient comes from the last eight terms, so it is sufficient that $m! > 100\cdot\sqrt[3]{729/560}.$ To show that $m=5$ is large enough, we need to verify that $(12/10)^3=216/125 > 729/560$. Carrying out the cross-multiplication, you can check without a calculator that $216\cdot 560 =120960$ is larger than $729\cdot 125=91125$, and conclude that $m=5$ (that is, $n=17$) is large enough. The inequality therefore holds for exactly all $n\ge 17$.

-
I find you method novel. great. thanks. – user45099 Feb 1 '13 at 18:09

how about make a function?$f(n)=\frac{3^n}{n!}-10^{-6}$ or maybe $f(n)=\frac{3^n}{n!10^{-6}}$

-
it's inequality. i am not sure if that will help. – user45099 Feb 1 '13 at 14:36
i think it's some trick to proof it. you can use the derivative of function,then you'll get it's convex or no – A Ricko Maulidar Feb 1 '13 at 16:35
Your function is defined for poistive integers. Can you really consider derivatives then? The only way out would be to extend this to $(0,+\infty)$ by the Gamma function en.wikipedia.org/wiki/Gamma_function since $\Gamma (n+1)=n!$. But the study of the sign of the derivative does not look promising... – 1015 Feb 1 '13 at 16:59

I would use Stirling's approximation $n!\approx \frac {n^n}{e^n}\sqrt{2 \pi n}$ to get $\left( \frac {3e}n\right)^n \sqrt{2 \pi n} \lt 10^{-6}$. Then for a first cut, ignore the square root part an set $3e \approx 8$ so we have $\left( \frac 8n \right)^n \lt 10^{-6}$. Now take the base $10$ log asnd get $n(\log 8 - \log n) \lt -6$ Knowing that $\log 2 \approx 0.3$, it looks like $16$ will not quite work, as this will become $16(-0.3)\lt 6$. Each increment of $n$ lowers it by a factor $5$ around here, or a log of $0.7$. We need a couple of those, so I would look for $18$.

Added: the square root I ignored is worth a factor of $10$, which is what makes $17$ good enough.a

Alpha shows that $17$ is good enough.

-
But it is not because it holds for the approximation that it holds for the original term. Unless you estimate the error of the approximation etc... – 1015 Feb 1 '13 at 18:52
@julien: The first error term is a factor $\frac 1{12n}$, which here is about $0.5\%$. That is small compared to the other approximations I have made. $3e\approx 8.15$ for a $2\%$ error and I was even willing to sacrifice the factor $10$ from the square root. This only makes a difference of 1 in how many terms are required. When working without a calculator, this seems acceptable. – Ross Millikan Feb 1 '13 at 18:59

How about we overestimate $3^n$ as $\sqrt{10}^n$ and underestimate every contribution to the factorial beyond $10$ as only $10$? Then $$\frac{3^n}{n!} \le \frac{10^5 \cdot 10^{\frac{n-10}2}}{10! \cdot 10^{n-10}}$$ Since $10!$ is about $10^{6.5}$ we have $$10^{-1.5} \cdot 10^{-\frac{n-10}2} \le 10^{-6}$$ After taking the $\log_{10}$ we have $$-1.5 -\frac{n-10}2 \le -6$$ $$1.5 + \frac{n-10}2 \ge 6$$ $$\frac{n-10}2 \ge 4.5$$ $$n-10 \ge 9$$ $$n \ge 19$$ Since you asked for a solution and not the minimal solution this should suffice, and is more plausibly done without a calculator. The only real mental calculation was remembering the approximate value of $10!$ (well, and $3^2$, but let's be reasonable).

Note that if you know the factorials for higher numbers (or exact values for some powers of 3, such as $3^7 = 2187$) then you could refine this argument using higher $n$ for the "fixed part".

-
sounds good but only concern is that underestimation and overestimation are of same order and do not lead to great error. – user45099 Feb 2 '13 at 9:56
Perhaps I should have been explicit: by overestimating the numerator and underestimating the denominator, each change individually causes the overall fraction to be overestimated, which is conservative to it being less than some limit. – half-integer fan Feb 2 '13 at 12:49
Which is to say, making the denominator smaller makes the fraction larger. – half-integer fan Feb 2 '13 at 12:50