Take the 2-minute tour ×





share|improve this question

1 Answer 1

Inductively, if $A_p \le p \log_2 p + \alpha p + \beta$, then

$A_{2p} \le ((2p) \log_2 (2p) + \alpha (2p) + \beta) + (\beta -2 + \frac {2}{p+1})$

so we'll want $\beta-2 + \frac{2}{p+1} \le 0.$

The odd case is a little harder. Assume the inequality is true for $A_p,A_{p+1}.$

$A_{2p+1} = A_p + A_{p+1} + 2p - 1 + \frac{2}{p+2}$

$ \le (p+1)\log_2 (p+1) + p ~\log_2 p + \alpha(2p+1) + \beta + \beta + 2p - 1 + \frac{2}{p+2}.$

Using $\log_2 x \le \frac{(x-(p+1/2))}{(p+1/2)\log 2} + \log_2 (p+1/2)$ at $x=p, p+1$:

$$A_{2p+1} \le (p+1)\log_2 (p+1/2) + p~\log_2p + \frac{p+1}{(2p+1)\log 2} - \frac {p}{(2p+1)\log 2} \\\ + \alpha(2p+1) + \beta + \beta + 2p - 1 + \frac{2}{p+2}$$

$$A_{2p+1} \le \bigg((2p+1)\log_2(2p+1) + \alpha(2p+1) + \beta \bigg) + \\\ \beta -2+ \frac{2}{p+2}+\frac{1}{(2p+1)\log 2}.$$

So, we'll also want $\beta - 2 + \frac{2}{p+2} + \frac{1}{(2p+1)\log 2} \le 0.$ Then if we choose $\alpha, \beta$ so that the base of the induction is satisfied, we get $A_n \le n \log_2 n + \alpha n + \beta.$

I think that you can get slightly better bounds by starting the induction higher, but let's start it at $p=1, A_2 = 1, A_3 = \frac 8 3.$ Then we want $4$ inequalities to be satisfied:

$1 \le 2 \log_2 2 + 2\alpha + \beta$

$\frac 8 3 \le 3 \log_2 3 + 3\alpha + \beta$

$\beta -2 + 1 \le 0$

$\beta -2 + \frac 23 + \frac{1}{3 \log 2} \le 0$

and we want to minimize $\alpha$ and then minimize $\beta$ for that $\alpha$ subject to these constraints. If I calculate correctly, then the solution is $\alpha = -\frac76 + \frac{1}{6 \log 2} = -0.9263, \beta = \frac43 - \frac 1{3\log 2} = 0.8524,$ and $A_n \le n \log_2 n + \alpha n + \beta$ should be satisfied for all $n \ge 2$. You can get a slightly lower value of $\alpha$ if you don't need the formula to work for $n=2$.

share|improve this answer
Douglas, Thank you very much for this elegant and didactic derivation. This is what I was hoping for. I just have a few remarks. The inequality on $\beta$ obtained from bounding $A_{2p+1}$ always implies the inequality obtained from $A_{2p}$, so we can get rid of the latter; in particular, we don't need the third inequality when setting $p=1$ at the end. When $p=1$, the two first inequalities show that if we want to minimize $\alpha$, we can maximize $\beta \geq 0$, and we know the upper bound on $\beta$ to be the value you provide. Then, the second inequality (again the odd case) yields the –  user25933 Aug 24 '12 at 20:02
lowest value for $\alpha$, that is, $\alpha = \frac{4}{9} - \lg 3 + \frac{1}{9\ln 2} \simeq -0.9802$. The advanced analytical techniques I alluded to yield $A_n = n\lg n - (1.25 \pm 0.01)n + O(1)$. I will work out the lower bound following your inductive method. Thanks again! –  user25933 Aug 24 '12 at 20:02
[I can't edit my answer.] Douglas is right, of course: when you have two lower bounds, you can only take the largest, so the even case rules for deciding $\alpha$, which is indeed the value given by Douglas. Sorry about that. Perhaps a better upper bound on $\lg p$ and $\lg(p+1)$ in terms of $\lg(2p+1)$ would yield a better result? –  user25936 Aug 24 '12 at 22:25

Your Answer


