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

You must log in to answer this question.

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