16
$\begingroup$

Given an integer $n \ge 1$, I'd like to have a not-very-loose upper bound for the integer $$u(n) := \Pi_{k=1}^n k^k = n^n(n-1)^{(n-1)}\ldots2^21^1.$$

It's easy see that, $u(n) \le n^{n(n+1)/2}$, but this is not very interesting.

Update

We have $u(n) \le e^{\left(\frac{1}{2}n(n+1)\log\left(\frac{2n + 1}{3}\right)\right)}$, and we can't really do much better!

Indeed, using Euler-Maclaurin, we have

$ \log(u(n)) = \int_2^nx\log x dx = \frac{1}{4}n^2(2\log(n) - 1) - 2\log(2) + \frac{1}{4} + \text{error terms}$, which is comparable to the bound $\log(u(n)) \le \frac{1}{2}n(n+1)\log\left(\frac{2n + 1}{3}\right)$ in the accepted answer (see below). In particular, we can conclude that accepted answer's bound is tight!

$\endgroup$
9
  • 3
    $\begingroup$ Taking logarithms may be a good start whenever you're dealing with products. $\endgroup$ – Alberto Debernardi Sep 9 '16 at 13:45
  • 1
    $\begingroup$ Ya, I contemplated the sequence $\sum_{k=1}^nk \log(k)$, but nothing pops-up... $\endgroup$ – dohmatob Sep 9 '16 at 13:46
  • 3
    $\begingroup$ Yes. Take logarithms, use Euler-MacLaurin, and exponentiate. $\endgroup$ – Daniel Fischer♦ Sep 9 '16 at 13:47
  • $\begingroup$ Thanks for pointing to Euler-Maclaurin. At the moment, I was just thinking about the Abel summation formula, but your suggestion looks more appropriate. $\endgroup$ – dohmatob Sep 9 '16 at 13:52
  • 1
    $\begingroup$ See also $(7)$ here: mathworld.wolfram.com/Hyperfactorial.html $\endgroup$ – Jack D'Aurizio Sep 9 '16 at 17:24
11
$\begingroup$

Using Jensen's inequality:

Letting $A= \sum_{k=1}^n k = \frac{n (n+1)}{2}$ and $B= \sum_{k=1}^n k^2 = \frac{n (n+1)(2n+1)}{6}$

We have

$$ \begin{align} \log(u(n)) &=\sum_{k=1}^n k \log(k) \\ &= A \sum_{k=1}^n \frac{k}{A} \log(k) \tag{1}\\ &\le A \log \left( \sum_{k=1}^n \frac{k}{A} k \right) = A \log \left( \frac{B}{A} \right) \tag{2} \end{align} $$

Hence

$$\log(u(n)) \le \frac{n(n+1)}{2} \log\left(\frac{2 n+1}{3}\right) \tag{3}$$

The bound seems to be quite tight:

enter image description here

Update: as noted by comments and OP, the bound $(3)$ agrees with the true order of growth; this can be checked by applying the trapezoidal rule to the integral:

$$ -\frac{1}{4}=\int_{0}^{1} x \log(x) dx \approx \frac{1}{n+1} \sum_{k=1}^n \frac{k}{n} \log\left(\frac{k}{n}\right) $$ which gives

$$ \log(u(n)) \approx\frac{ n(n+1)}{2}\left( \log n -\frac{1}{2} \right) \tag{4}$$

If one is interested in an approximation (instead of a bound), $(4)$ might be preferable.

Better asymptotics here (from comments).

$\endgroup$
2
  • $\begingroup$ Perfect! Thanks. I see you've used the concave function $\phi(x) := log(x)$ and positive scalars $a_k = k$ in Jensen's inequality: en.wikipedia.org/wiki/Jensen%27s_inequality $\endgroup$ – dohmatob Sep 9 '16 at 14:05
  • $\begingroup$ Now that's a freaky tight bound! I Indeed, it's no surprise that the bound is tight. Using Euler-Maclaurin suggested by Daniel above, I can get $\log(u(n)) \approx \frac{1}{4} (n^2(2\log(n) - 1) - 1)$ :). Thus I don't need to beg the error terms in my EM, and can just use your bound instead. Thanks again. $\endgroup$ – dohmatob Sep 9 '16 at 14:10
3
$\begingroup$

Another simple way for finding an upper bound is using the Abel's summation $$S=\sum_{k=1}^{n}k\log\left(k\right)=\frac{n\left(n+1\right)}{2}\log\left(n\right)-\frac{1}{2}\int_{1}^{n}\frac{\left\lfloor t\right\rfloor \left(\left\lfloor t\right\rfloor +1\right)}{t}dt $$ where $\left\lfloor t\right\rfloor $ is the floor function and since $\left\lfloor t\right\rfloor >t-1 $ we get $$S<\frac{n\left(n+1\right)}{2}\log\left(n\right)-\frac{1}{2}\int_{1}^{n}\left(t-1\right)dt $$ $$=\color{red}{\frac{n\left(n+1\right)}{2}\log\left(n\right)-\frac{\left(n-1\right)^{2}}{4}}.$$

$\endgroup$
2
$\begingroup$

Don't have the reputation, or else this would be a comment. As mentioned in a link posted by leonbloy, the hyperfactorial, which shows up in the theory of the Barne's G function, is related to $\int_0^n \log\Gamma(x) dx.$ Good bounds on this should give a better bound than that found by Jensen's inequality. I found the expression

$$\log(u(n)) \le A(n):=\dfrac{(n+1/2)^2}{2}(\log(n+1/2)-3/2)+\dfrac{n(n+1)}{2}+ \dfrac{9}{8}\log(2/3)+\dfrac{11}{16}.$$

For a comparison, let's define 'Jensen' and 'A' ratios

$$R_J(n)=\dfrac{\log(u(n))}{n(n+1)/2\log((2n+1)/3))},\quad R_A(n)=\dfrac{\log(u(n))}{A(n)} .$$

Then (approximately) $R_J(100)=0.892$ , $R_A(100)=0.999992;$ and $R_J(10^5)=0.9915$ , $R_A(10^5)=0.99999999915$ (nine nines).

$\endgroup$
2
  • $\begingroup$ Interesting. Do include some detail on your derivation of $A(n)$ (not just an expression for it...). $\endgroup$ – dohmatob Sep 13 '16 at 7:39
  • $\begingroup$ Great answer! Upvoted. $\endgroup$ – dohmatob Jan 23 '17 at 7:22

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.