<s>[INST] Upper bound for - $\sum_{i=1}^n i {2n \choose n+i} $. I am tryin to calculate an upper bound for the following sum:
$\sum_{i=1}^n i {2n \choose n+i} $.
I know that the limit should be $\Theta (4^n\sqrt n)$ but I am not sure how to proceed. I already tried to bound by the biggest element, but the bound was too high.
 [/INST] We have that
$$S_n = \sum_{q=1}^n q {2n\choose n+q}
= \sum_{q=1}^n q [w^{n-q}] \frac{1}{(1-w)^{n+q+1}}
= [w^n] \frac{1}{(1-w)^{n+1}} 
\sum_{q=1}^n q \frac{w^q}{(1-w)^q}.$$
Now here the coefficient extractor enforces the range and we get
$$[w^n] \frac{1}{(1-w)^{n+1}} 
\sum_{q\ge 1} q \frac{w^q}{(1-w)^q}
= [w^n] \frac{1}{(1-w)^{n+1}} 
\frac{w/(1-w)}{(1-w/(1-w))^2}
\\ = [w^{n-1}] \frac{1}{(1-w)^n} \frac{1}{(1-2w)^2}
\\ = \mathrm{Res}_{w=0}
\frac{1}{w^n} \frac{1}{(1-w)^n} \frac{1}{(1-2w)^2}.$$
We now apply the change of variables rule 1.8 (5) from Egorychev's
Integral representation and the Computation of Combinatorial sums
(page 16) with $A(w) = \frac{w}{(1-2w)^2}$ and $f(w) = \frac{1}{1-w}.$ We
get $h(w) = w (1-w)$ and find
$$\mathrm{Res}_{z=0} \frac{1}{z^{n+1}}
\left.\left[ \frac{A(w)}{f(w) h'(w)} \right]\right|_{w=g(z).}$$
with $g$ the inverse of $h.$ This becomes
$$\mathrm{Res}_{z=0} \frac{1}{z^{n+1}}
\left.\left[ \frac{w/(1-2w)^2}{(1-2w)/(1-w)} 
\right]\right|_{w=g(z)}
\\ = \mathrm{Res}_{z=0} \frac{1}{z^{n+1}}
\left.\left[ \frac{w(1-w)}{(1-2w)^3} \right]\right|_{w=g(z)}
= \mathrm{Res}_{z=0} \frac{1}{z^{n}}
\left.\left[ \frac{1}{(1-2w)^3} \right]\right|_{w=g(z).}$$
Observe that $(1-2w)^2 = 1 - 4w + 4w^2 = 1-4w(1-w) = 1-4z$
so this is
$$\mathrm{Res}_{z=0} \frac{1}{z^{n}}
\frac{1}{(1-4z)^{3/2}} = 
4^{n-1} {n-1+1/2\choose n-1}
= 4^{n-1} {n-1/2\choose n-1}.$$
Expanding the binomial coefficient we find
$$4^{n-1} \frac{1}{(n-1)!} \prod_{q=0}^{n-2} (n-1/2-q)
= 2^{n-1} \frac{1}{(n-1)!} \prod_{q=0}^{n-2} (2n-1-2q)
\\ = 2^{n-1} \frac{1}{(n-1)!} \frac{(2n-1)!}{2^{n-1} (n-1)!}
= \frac{1}{2n} n^2 {2n\choose n}
= \frac{1}{2} n {2n\choose n}.$$
Now for the central binomial
coefficient
we have ${2n\choose n} \sim \frac{4^n}{\sqrt{\pi n}}$ so this yields
$$\bbox[5px,border:2px solid #00A000]{
S_n = \frac{1}{2} n {2n\choose n} 
\sim \frac{4^n}{2\sqrt{\pi}} \sqrt{n}.}$$
If we seek $\Theta(4^n\sqrt{n})$ from first principles we use from the
same reference the upper bound  ${2n\choose n} \le 4^n/\sqrt{3n+1}$ so
we get
$$S_n \le \frac{1}{2} n \frac{4^n}{\sqrt{3n+1}}
= \frac{1}{2\sqrt{3}} \sqrt{n} \frac{4^n}{\sqrt{1+1/3/n}}
\lt \frac{4^n}{2\sqrt{3}} \sqrt{n}.$$
The lower bound is done similarly and we have the claim.
</s>