Question

establish below inequality

Answer 1

\[\large \dfrac{\sigma(n!)}{n!}\ge H_n\]

where
\(\sigma\) is sum of divisors function
\(H_n\) isthe nth harmonic number
https://en.wikipedia.org/wiki/Harmonic_number

Answer 2

hey
\(\sigma((2k)!) = k(2k+1)\)
doesn't look correct

Answer 3

http://www.wolframalpha.com/input/?i=Table%5Bsigma%28%282*k%29%21%29+-+k%282k%2B1%29%2C%7Bk%2C1%2C10%7D+%5D

Answer 4

I guess I didn't consider all the divisors...
for example for 6! I only considered 6,5,4,3,2,1
I guess I should have also considered 30,20,12,15,24,10, etc...

Answer 5

oh nice, i see.. then we can definitely say
\[\sigma((2k)!)\ge 1+2+3+\cdots +(2k-1)+(2k) = k(2k+1)\]

Answer 6

I wonder if that divided by (2k)! will still be bigger than the harmonic number of 2k

Answer 7

i have a feeling that ratio would be always less than 1

Answer 8

it seems the lowerbound k(2k+1) is too small compared to (2k)!

Answer 9

http://www.wolframalpha.com/input/?i=Table%5Bk%282k%2B1.0%29%2F%282k%29%21%2C%7Bk%2C1%2C10%7D%5D

Answer 10

yep I just plugged in k equals 2 into my above inequality and it failed

Answer 11

http://www.wolframalpha.com/input/?i=Table%5Bsigma%28n%21%29%2Fn%21-H_n%2C%7Bn%2C1%2C10%7D%5D

Answer 12

\[H_n=\frac{ 1 }{ 1 }+\frac{ 1 }{ 2 }+\frac{ 1 }{ 3 }......\frac{ 1 }{ n }\]\[H_n=\frac{ \sum_{a=1}^{n} \frac{ n! }{ a}}{ n! }\]

clearly the numerator of \(H_n\) will have terms of this form-> [\(2*3*4*5..n\)], [\(1*3*4*5..n\)], ....
these are divisors of n!

but the numerator will not contain all the divisors of n! for example -> 1, 2, 2*3, ...

so clearly the Numerator on the LHS will be greater
the denominator in both cases is same
so LHS>RHS

now we have to prove that LHS=RHS for some case

hmmm

for this the short way is to take n=1 (;
when n will be 1
its clear that LHS=RHS
+
we also proved that LHS will be greater than RHS

So \(LHS \ge RHS\)

Answer 13

Excellent ! that is really a very nice proof !!

Answer 14

thanks :)

Answer 15

I love it when a proof makes something just feel obvious like this. Niiiiiice

Answer 16

This got me thinking of just fun stuff with factorials and primorials, and I realized this would be true for n>1:

\[\tau(\sigma(p_n \#)) > 2n \]

Really cute to use this trick with a multiplicative function, so I'm just playing with it at the moment.

\[f(p_n \#) = \prod_{k=1}^n f(p_k)\]

Answer 17

\(\tau(\sigma(p_n \#)) > 2n \)

may i see why is this true ?

Answer 18

here is an identical but one liner version of @imqwerty 's earlier proof

\[\sigma(n!) = \sum\limits_{d\mid n!}\dfrac{n!}{d}\implies \dfrac{\sigma(n!)}{n!}=\sum\limits_{d\mid n!}\dfrac{1}{d}\ge H_n\]

Answer 19

First off, here's a quick fact:
\[p_n\# = \prod_{k=1}^n p_k\]
So we have:
\[\tau(p_n \#) = 2^n\]

Now since \[\sigma(p_n\#) = \prod_{k=1}^n (p_k+1)\] for each term with k>1 you necessarily have more divisors than the corresponding \(p_n\#\) term because \(p_k+1\) is a composite number which means it has more divisors so:

\[\tau(\sigma(p_n\#)) > \tau(p_n\#) = 2^n\]

Answer 20

nice, gotcha !

Answer 21

Quick question, I can put a tighter lower bound on this if I can prove that:

For primes p greater than 3, we have \(p+1\) is never a perfect square.

I think there might be some modular arithmetic thing that might show this but I don't know.

Answer 22

If we can prove that, then since n>2 we have:

\[\tau(\sigma(p_n \#)) = \tau(2)\tau(3) \prod_{k=3}^n \tau(p_k+1) \ge 6 *4^{n-2} \]

Where I've replaced all the \(p_k+1\) with numbers that have at least 4 divisors, if any of them were perfect squares (other than 3+1) we can already make this statement:


\[\tau(\sigma(p_n \#)) = \tau(2) \prod_{k=2}^n \tau(p_k+1) \ge 2 *3^{n-1} \]

Answer 23

I didn't realize how interested I could be in the behavior of primes near perfect squares and cubes... It seems strange that \(3+1=2^2\) and \(2^3+1=3^2\)... Anyways just playing around don't mind me lol

Answer 24

I goofed when I wrote the tau's out front above, they should be:

\[\tau(\sigma(p_n \#)) = \tau(2+1)\tau(3+1) \prod_{k=3}^n \tau(p_k+1) \ge 6 *4^{n-2} \]
\[\tau(\sigma(p_n \#)) = \tau(2+1) \prod_{k=2}^n \tau(p_k+1) \ge 2 *3^{n-1} \]

Answer 25

very interesting !
\(p+1 = n^2 \implies p = n^2-1 = (n+1)(n-1)\)

Answer 26

Beautiful!

Answer 27

its irrelevent here, but by same argument \(p_n\#+1\) is never perfect square

Answer 28

Well I guess I am not gonna stop there, what about bumping it to having each term \(\tau(p_k+1) > 5\) is that possible? Since there's only one way to make this true, that's with \(p_k+1=q^4\) I just have to show that this isn't satisfied which looks like a quick reuse of the same trick!

\[p_k = (q^2+1)(q+1)(q-1)\]

Even if q is 2, it's still composite, so we can make it even larger of a lower bound!

For n>2:

\[\tau(\sigma(p_n \#)) \ge 6 * 5^{n-2}\]

Dare we try for 6?

Answer 29

wait, how do we know \(p_k+1=q^4\) ?

Answer 30

@ganeshie8 Since we ruled out each of the terms earlier satisifes \(\tau(p_k+1) > 4\) (for k>2) then in order to increase the lower bound, we have to show \(\tau(p_k+1) > 5\). To do this, I looked at all the possible ways for \(\tau(n)=5\) which only has this as a solution \(\tau(q^4) = 5\)

So as long as I can show \(p_k+1 \ne q^4\) then I've increased the bound... I believe!

Answer 31

Maybe I've left out some cases now that I think of it hmmm...

Answer 32

I completely skipped over trying to pull out cases where \(\tau(p_k+1)=4\)... heh... Ok I guess I'd have to show that

\[p_k+1 \ne q^3\] AND \[p_k+1 \ne qr\]

which is a considerably harder condition to fulfill... Especially since 5+1=2*3 and 7+1=2^3... Unless by some miracle these are the only two cases that are exceptions... xD

Answer 33

they seem to appear more frequent..

Answer 34

solve over prime numbers

\(a+1 = bc\)

Answer 35

yeah for \(p+1=q^3\), the only solution is \(p=7, q=2\)...
but the second case, it feels like it should have infinitely many solutions

Answer 36

Interesting, I want to say that you're right but at the same time, I am not sure. It could very well be that all primes after a certain point with large numbers are only ever near numbers with more than 2 factors?

Answer 37

\(a+1= bc\)

letting \(c=2\)
\(a+1 = 2b\)

\(\dfrac{a+1}{2}=b\)


so the whole thing boils down to finding \(a\) such that \(\dfrac{a+1}{2}\) is also a prime

Answer 38

Interesting, this makes it look really nice and possibly solvable for finite cases

Answer 39

\(c\) has to be \(2\) for \(p_k\gt 2\) because the left hand side is always even

Answer 40

well we can show that for \(p_k=2\) it has no solutions, so we're safe on that case to

Answer 41

http://jsfiddle.net/ganeshie8/uf88dy2e/