# Estimating sums

Estimate following sums as the functions of variable $n$:

a) $\displaystyle\sum_{i=1}^{n}e^i\ln i$

b) $\displaystyle\sum_{i=1}^{2n}(-1)^i\ln i$

c) $\displaystyle\sum_{i\ge 0}^{}\frac{\ln(n+i)}{e^i}$

d) $\displaystyle\sum_{i\ge 0}^{}\frac{(-1)^i}{\ln(n+i)}$

I prefer the easiest ways to do such things, so Euler-Maclaurin formula isn't in my style. Are these examples very hard? I want to learn how to do such things but unfortunately when it comes to solving I have no ideas.

Only in b) I thought I knew but the idea is probably useless: $$\sum_{i=1}^{2n}(-1)^i\ln i=\sum_{i=1}^{n}\ln(2i)-\ln(2i-1)$$ so let: $$f(x)=\ln(2x)-\ln(2x-1)$$ and it's easy to check that $f(x)$ non increasing for $x\ge 1$ then: $$\int_i^{i+1}f(x)\le f(i)\le\int_{i-1}^if(x)$$ it follows: $$\int_2^{n+1}f(x)\le\sum_{i=2}^n f(i)\le\int_1^{n}f(x)$$ and integral is easy to count: $$\int f(x)=\frac{1}{2}\left( 2x\ln(2x)-(2x-1)\ln(2x-1)-1 \right)+C$$ But is it worth anything? Can I write from this $\sum_{i=1}^n f(i)$ using asymptotics notations like big $O$ or $\Theta$?

I don't know how to approach the rest.

-
The first sum is dominated by its largest term; try to show that it is in fact $\Theta(e^n \log n)$. –  Qiaochu Yuan Aug 24 '12 at 18:35
Why do you feel like Euler-Maclaurin isn't 'the easiest way' to solve problems like this? –  Steven Stadnicki Aug 24 '12 at 18:39
@QiaochuYuan, I'm not sure how to do that. –  ray Aug 24 '12 at 19:58
Perhaps you might want to actually compute a few values of the sum to get a sense of how the terms grow. –  Qiaochu Yuan Aug 24 '12 at 19:59
@StevenStadnicki, I am ashamed to admit, but this formula seems too hard for me. I have even problems with using it.. –  ray Aug 24 '12 at 20:00

For case (b), introduce $x_k=\log(2k)-\log(2k-1)\sim\frac1{2k}$. Then, $s_n=\sum\limits_{k=1}^{2n}(-1)^k\log(k)=\sum\limits_{k=1}^nx_k$ is such that $$s_n\sim\sum\limits_{k=1}^n\frac1{2k}\sim\frac12\log(n).$$ To be more precise, note that $x_k=\int\limits_{2k-1}^{2k}\frac{\mathrm dt}t$ hence $2x_k\leqslant\int\limits_{2k-2}^{2k}\frac{\mathrm dt}t$ for every $k\geqslant2$ and $2s_n\leqslant2x_1+\int\limits_2^{2n}\frac{\mathrm dt}t=2\log(2)+\log(2n)-\log(2)$, that is, $s_n\leqslant\frac12\log(n)+\log(2)$ for every $n\geqslant1$. Likewise, $2x_k\geqslant\int\limits_{2k-1}^{2k+1}\frac{\mathrm dt}t$ for every $k\geqslant1$ and $2s_n\geqslant\int\limits_1^{2n+1}\frac{\mathrm dt}t=\log(2n+1)$, that is, $s_n\geqslant\frac12\log(n)+\frac12\log(2)+\log(1+\frac1{2n})$ for every $n\geqslant1$. This yields the asymptotics $$s_n=\frac12\log(n)+O(1).$$ Edit: Roughly the same techniques of comparison with integrals yield the three other cases, but it might be more profitable to understand fully case (b) before studying them. Anyway, unless I am mistaken, simple equivalents for cases (a), (c) and (d) are $$\text{(a)}\ \frac{\mathrm e}{\mathrm e-1}\log(n)\,\mathrm e^n,\quad \text{(c)}\ \frac{\mathrm e}{\mathrm e-1}\log(n),\quad \text{(d)}\ \frac1{2\log n}.$$
For b, you can say the sum is $\ln \frac {(2n)!!}{(2n-1)!!}=\ln \frac {2^n(n!)^22^n}{(2n)!}$ and then use Stirling's approximation.