3
$\begingroup$

I've spent many hours trying to find proof by induction to this problem:

$$(n!)^2<\left(\frac{(n+1)(2n+1)}{6}\right)^n$$

for n > 1.

Does anyone have any idea how to solve it? Any help would be appreciated.

$\endgroup$
  • $\begingroup$ It's worth noting that this is true for $n \geq 2$. $\endgroup$ – Harry Jun 21 '17 at 20:15
  • 1
    $\begingroup$ Ok first thing, I'm not asking because I need this for exam or anything like that. I graduated long long time ago. Friend asked me to help him and when I say I tried lot of things, I tried lot of things. So questions like "What have you tried? We will not solve your school problems etc." are really not appreciated. I will put bounty, hopefully that will change attitude. $\endgroup$ – Aleksandar Makragić Jun 21 '17 at 20:16
  • 3
    $\begingroup$ Erm... since you want help from people who may or may not volunteer to do so, the question of what you appreciate is somewhat moot, wouldn't you say so? If you had included that info in your question, reactions would have been entirely different, I'm certain. $\endgroup$ – Professor Vector Jun 21 '17 at 20:21
  • 1
    $\begingroup$ @DuncanRamage First thing I tried is classical way, but wasn't sure if I even could replace hypotesis into inductive step, then I tried putting everything to one side and proving that that side is positive in one case or negative in other depending to what side you transfered everything, but that didn't get me anywhere... $\endgroup$ – Aleksandar Makragić Jun 21 '17 at 20:28
9
$\begingroup$

Using AM-GM inequality (which can be proved by induction on the number of terms),

$$\sqrt[n]{1^2\cdot 2^2\cdot3^2 \cdots n^2} \le \frac{1^2 + 2^2+3^2+\cdots + n^2}{n}$$

Equality holds iff $1^2 = 2^2 = \ldots = n^2$, which means equality does not hold for $n>1$.

On the left hand side,

$$(n!)^2 = 1^2 \cdot2^2 \cdot 3^2 \cdots n^2$$

which can be proved by induction on $n$.

On the right hand side,

$$1^2 + 2^2+3^2+\cdots + n^2 = \frac{n(n+1)(2n+1)}{6}$$

which can also be proved by induction on $n$.

Joining the three links together,

$$\sqrt[n]{(n!)^2} < \frac{(n+1)(2n+1)}{6}$$

Taking the $n$th power on both sides (which preserves order as both sides are positive) gives the required inequality.

$\endgroup$
  • $\begingroup$ Thanks for answering! :) I don't understand how inequality you wrote connects with problem I have? $\endgroup$ – Aleksandar Makragić Jun 21 '17 at 20:31
  • $\begingroup$ What is $k^2$, exactly? $\endgroup$ – Duncan Ramage Jun 21 '17 at 20:32
  • $\begingroup$ @AleksandarMakragić There is an identity that $1^2 + 2^2+3^2+\cdots + n^2 = \frac{n(n+1)(2n+1)}{6}$ which can be proved by induction. $\endgroup$ – peterwhy Jun 21 '17 at 20:44
  • 1
    $\begingroup$ @DuncanRamage $k^2$ was meant to be the set $\{1^2, 2^2,\ldots,n^2\}$, modified. $\endgroup$ – peterwhy Jun 21 '17 at 20:45
  • 2
    $\begingroup$ @peterwhy Thanks a lot! I will wait two days in order to give you bounty. +1 for now! Thanks a lot one more time! $\endgroup$ – Aleksandar Makragić Jun 21 '17 at 21:05
1
$\begingroup$

I will prove the given inequality with a different approach from @peterwhy just to shopw another way I like to prove this. It is a little bit more euler- handwavy than @peterwhy s proof but it hink it is quite nice.

to start we note two well known results (which I can prove if you want) $an^n>bn!>c d^n$ for all n suitably large in relation to a, b, c and d and only for n suitably large. This can be summarized as $n^n$ grows faster than $n!$ which grows faster than $d^n$. proving this is not hard.

for this problem we are interested if $an^n> c d^n bn!$ for all n suitably large in relation to a, b, c and d and only for n suitably large. say we have $e=\frac{cb}{a}$ we take n so large that lets say $q=(n!)^{1/n}$ then $q^n=n!$ notice that $q<n$ and that $n-q$ can be made arbitrarly large. then we can say that $d^n n!=(dq)^n$ if we then pick $n=(e^{1/n}dq)$ , $an^n= c d^n bn$ while for every $n$ smaller than that $an^n< c d^n bn!$ and for every $n$ larger $an^n> c d^n bn$ because $\frac{ c d^n bn!}{a}=\frac{ cb}{a}(dq)^n=e(dq)^n=(e^{1/n}dq)^n$.

After proving this we notice that $(n!)^2<\left(\frac{(n+1)(2n+1)}{6}\right)^n$ implies $6^n(n!)^2<\left((n+1)(2n+1)\right)^n>(n^2)^n=(n^n)^2$ since we know that $(n^n)^2>6^n(n!)^2$ because $(n^n)>6^n(n!)$ for all n suitably large and only for n suitably large. we only have to show that the original inequality holds for $n=2$ which it does.

$\endgroup$

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.