Upper bound for - $\sum_{i=1}^n i {2n \choose n+i} $.

Question

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.

Answer 1

Another proof, neater but from a probabilistic point of view. If you are comfortable with discrete probability theory (random variables, expectations etc.) you might find this one more to your liking.

Note that the quantity you are trying to analyze is equal to

$$ \frac{1}{2}\cdot \ \ \ \ \underbrace{\sum_{i=-n}^n |i| \binom{2n}{n+i}}_S $$.

I'll ignore the $1/2$ because the question is about asymptotics and consider only the sum $S$ above.

Consider the following probablistic scenario. Let $X_1,\ldots, X_{2n}$ be $2n$ independent random variables each uniformly distributed over $\{\pm 1\}.$ Let $X$ denote $X_1+X_2+\cdots+X_{2n}.$ The sum $S$ is exactly $4^n \cdot \mathbb{E}[|X|]$ (i.e. the expectation of $|X|$).

By the Cauchy-Schwarz inequality, we have $\mathbb{E}[|X|]\leq \sqrt{\mathbb{E}[X^2]}$. An easy analysis allows us to show that $\mathbb{E}[X^2]=n.$

Answer 2

Here's an outline of something that might work:

1. Show that $\binom{2n}{n+i}\leq \binom{2n}{n}\cdot \exp(-\Omega(i^2/n)).$ (The inequality $1-x\leq \exp(-x)$ might come in handy.)

2. Use Stirling's approximation to note that $\binom{2n}{n} =\Theta(4^n/\sqrt{n})$. (You can also try to prove it directly. Hint here.)

3. The above should reduce your problem to upper bounding a sum of the form $\sum_{i} i\cdot \exp(-\Omega(i^2/n)).$ Upper bound this by a suitable integral to get the result.

Answer 3

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.