4
$\begingroup$

How does one solve the following inequality for n, without trial and error, and assuming n can only be an integer?

The inequality is $(n+1)!-1>10^9$.

I want to find the minimum value of n such that $(n+1)!-1>10^9$. How does one do this without graphing the inequality, or using a calculator? I figured it out throwing trial and error on a calculator, but I desire a more elegant solution, one that gets to the answer algebraically, and without a calculator or graph. Any suggestions?

$\endgroup$
  • 2
    $\begingroup$ This inequality does not have an algebraic solution. Trial and error is necessary. The number of trials can be pretty small if you're clever about using the information you learn from each failure. You could edit the question to show us your method and ask if there's a more efficient one. (Question: why is $n$ raised to the first power? Is that a typo?) $\endgroup$ – Ethan Bolker Sep 5 '18 at 13:27
  • $\begingroup$ @EthanBolker I see. Thank you. $\endgroup$ – user590211 Sep 5 '18 at 13:28
  • $\begingroup$ @EthanBolker I had no method though, I literally just brute forced my way to an answer. What is one more efficient way you suggest? $\endgroup$ – user590211 Sep 5 '18 at 13:31
  • $\begingroup$ Do we want the least positive integer or the least value that satisfies this? Because they need two very different methods $\endgroup$ – Rhys Hughes Sep 5 '18 at 13:56
  • $\begingroup$ The Gamma function (coincides with the factorial on positive integers) has no known elementary inverse. See here: math.stackexchange.com/questions/931846/…. $\endgroup$ – Adrian Keister Sep 7 '18 at 0:07
3
$\begingroup$

A possible way would be to use upper and lower bound to the factorial function. There are of course very precise ones, but you said you don't want to use a calculator, so we take simple ones:

$$\left(\frac{n}{2}\right)^{\frac{n}{2}}\leq n!\leq n^n$$

(I leave the simple proofs to you, as they are quite insightful).

Then we first want to solve the easier inequation $m!>10^9$. We immediately see that we must have $m>9$. This already gives you some starting point. An upper bound on the other hand is 20. It is still somewhat bruteforce.

A better approximation is $n!\approx\sqrt{2\pi n}\left(\frac{n}{e}\right)^n$ which will help you more to get a good starting guess.

$\endgroup$
  • $\begingroup$ If we ignore the square root in Stirling, one can notice that $27 \approx 10e$ so $27! \approx 10^{27}$. That can be handy in estimating factorials. The square root gives another factor $10$ but that is not much in this range. $\endgroup$ – Ross Millikan Sep 6 '18 at 0:00
3
$\begingroup$

If you know that $10!$ is between $3$ and $4$ million, then it seems that you would need to go three terms further in the factorial sequence (multiplying by $11$, $12$, $13$) to first exceed $1$ billion.

$\endgroup$
  • $\begingroup$ @Deepesh Meena, Fair enough. I would still start with the highest factorial I knew as a starting point and then try to figure out (or estimate) how many more factors I might need. $\endgroup$ – paw88789 Sep 5 '18 at 13:46
0
$\begingroup$

Observe that between $1$ and $10$, multiplying $1$ and $10$, $2$ and $9$, etc., every pairwise product contributes at least a factor of $10$. Thus $10!$ is at least $10^5$ (but of course you can deduce quite easily that it must actually be at least $10^6$). Then multiplying by $11$ and $12$ contributes about $10^2$. Now we know that $12!>10^8$. So the largest possible value of $n+1$ is now $13$, and you only have to try $12!$ to show that it is indeed smaller than $10^9$. Minimal brute force involved!

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy