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$ Sep 9, 2016 at 13:45
  • 1
    $\begingroup$ Ya, I contemplated the sequence $\sum_{k=1}^nk \log(k)$, but nothing pops-up... $\endgroup$
    – dohmatob
    Sep 9, 2016 at 13:46
  • 3
    $\begingroup$ Yes. Take logarithms, use Euler-MacLaurin, and exponentiate. $\endgroup$ Sep 9, 2016 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, 2016 at 13:52
  • 1
    $\begingroup$ See also $(7)$ here: mathworld.wolfram.com/Hyperfactorial.html $\endgroup$ Sep 9, 2016 at 17:24

3 Answers 3

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, 2016 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, 2016 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, 2016 at 7:39
  • $\begingroup$ Great answer! Upvoted. $\endgroup$
    – dohmatob
    Jan 23, 2017 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.