8
$\begingroup$

Prove that $\sigma(n!) < \frac{(n+1)!}{2}$ for all positive integers $n$, where $n \geq 8$.

$\sigma(n)$ is sum of positive divisors of $n$.

My thought :

$n=p_1^{k_1}p_2^{k_2}...p_m^{k_m}$, where $p_1, p_2, ..., p_m$ are primes.

$\sigma(n) = \displaystyle\prod_{i=1}^m\left(\frac{p_i^{k_i+1}-1}{p_i-1}\right)$

I think this problem may be solved by using LTE.

How can we find $\sigma(n!)$ ?

$\endgroup$
4
  • $\begingroup$ my thought is use triangular numbers. $\endgroup$
    – user451844
    Jul 20, 2017 at 13:56
  • $\begingroup$ @Roddy MacPhee, please explain on how to use it. $\endgroup$
    – user403160
    Jul 20, 2017 at 14:58
  • $\begingroup$ my thought was based on the formula for triangular numbers being $${n(n+1)\over 2}$$ because that similar in form to the value you are checking against. But the only thing close, I can think of, is number of pairs of divisors so it may not be as helpful as I thought. $\endgroup$
    – user451844
    Jul 20, 2017 at 16:03
  • 2
    $\begingroup$ $\displaystyle n! = \prod_{p \le n} p^{\sum_{k \ge 1}\lfloor n/p^k \rfloor }$ $\endgroup$
    – reuns
    Jul 20, 2017 at 17:00

2 Answers 2

5
$\begingroup$

The claim is equivalent to $\frac{\sigma(n!)}{n!}<\frac{n+1}{2}$ for $n \geq 8$. By inspection this holds for $n=8,9,10$, so assume $n\geq 11$ and write

\begin{align} \frac{\sigma(n!)}{n!}&=\prod_{p\leq n}\frac{p-\frac{1}{p^{v_p(n!)}}}{p-1}\tag{1}\\ &<\prod_{p\leq n}\frac{p}{p-1}\\ &=\frac{2}{1}\frac{3}{2}\frac{5}{4}\frac{7}{6}\prod_{11\leq p\leq n}\frac{p}{p-1}\\ &\leq \frac{35}{8}\prod_{11\leq k\leq n}\frac{k}{k-1}\tag{2}\\ &=\frac{35}{8}\frac{n}{10}\tag{3}\\ &=\frac{7}{16}n\\ &<\frac{n+1}{2}. \end{align}

Here:

  1. Definition of $\sigma$ and the fact that prime $p\mid n!$ iff $p\leq n$
  2. Switched from a product over primes $p$ to a product over all integers $k$ in a given range (added terms are all $>1$ so this could only increase the product)
  3. Product telescoped

Note: With some care the above argument can be extended to show for any $\varepsilon>0$ we have $\frac{\sigma(n!)}{n!}<\varepsilon n$ for all $n$ sufficiently large.

$\endgroup$
2
$\begingroup$

Robin proved that $\sigma(n) < e^\gamma n \ln \ln n + n \frac{0.6482...}{\ln \ln n}$ for all $n\geq 3$.

So $\sigma(n!) < e^\gamma n! \ln \ln n! + n! \frac{0.6482}{\ln \ln n!} < \frac{(n+1)!}{2} = 0.5 n! (n+1)$

Divide both sides by $n!$ to get $ e^\gamma \ln \ln n! + \frac{0.6482}{\ln \ln n!} < 0.5 (n+1)$

Using the upper bound Stirling approximation $n! < n^n \sqrt{n} e^{-n} e$

We arrive at $e^\gamma \log \left(-n+\left(n+\frac{1}{2}\right) \log (n)+1\right) +\frac{0.6482}{\log \left(-n+\left(n+\frac{1}{2}\right) \log (n)+1\right)} < 0.5(n+1)$

Since $-n+1 <0 $ and $2n>(n+0.5) \ln n$ for all $n\geq 3$ we get to

$ e^{\gamma } \log (2 n)+\frac{0.6482}{\log (2 n)}<0.5 (n+1)$

Solving for $n$ we get that this is true for all $n>10.1574 $

By simple checking from $1$ till $10$ we conclude the proof.

$\endgroup$
4
  • $\begingroup$ Thank you very much, Ahmad. I wonder if there would be more elementary solution. $\endgroup$
    – user403160
    Jul 21, 2017 at 11:21
  • $\begingroup$ this proof is elementary, see Robin proof which is simple, also upper and lower bound for $n!$ is also elementary, my proof is simple, so the whole proof is elementary. $\endgroup$
    – Ahmad
    Jul 21, 2017 at 16:20
  • $\begingroup$ The inequality in the problem is also true for $n$ = 8, 9. Please check. $\endgroup$
    – user403160
    Jul 22, 2017 at 10:39
  • $\begingroup$ that is covered by the last line in the post. $\endgroup$
    – Ahmad
    Jul 27, 2017 at 19:38

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .