I have the following expression,
$$
\frac{1}{n 4^n} \sum_{i = 1}^{n} i \binom{2n}{n + i},
$$
and I'm wondering if one can get either an exact formula for the sum involving binomial coefficient or get a tight asymptotic bound for the whole expression.
Any help would be appreciated.
Best Answer
I have worked on a similar expression:
$$ \begin{align} \sum_{j=1}^{n}{2j\cdot\binom{2n}{n+j}}&=\sum_{j=1}^{n}{(n+j)\cdot\binom{2n}{n+j}}-\sum_{j=1}^{n}{(n-j)\cdot\binom{2n}{n+j}}\\ \\ &=\sum_{j=1}^{n}{(n+j)\cdot\binom{2n}{n+j}}-\sum_{j=1}^{n}{(n-j)\cdot\binom{2n}{n-j}} \end{align} $$
Imagine choosing several of $2n$ people to be in a committee and then electing one of the committee as a leader. The first term on right hand side is the number of possibilities where the committees consist of at least $n+1$ members while the other term is where the committees consist of at most $n-1$ members.
We can select the leader first and then complete the committees. If there are at least $n+1$ members of committee, then there are at most $n-1$ non committee. If there are at most $n-1$ members, then there are at most $n-2$ members aside from the leader.
$$ \begin{align} \sum_{j=1}^{n}{2j\cdot\binom{2n}{n+j}}&=2n\sum_{k=0}^{n-1}{\binom{2n-1}{k}}-2n\sum_{k=0}^{n-2}{\binom{2n-1}{k}}\\ \\ &=2n\cdot\binom{2n-1}{n-1} \end{align} $$
From this result we can get solution to your problem:
$$ \begin{align} \frac{1}{n\cdot 4^{n}}\sum_{j=1}^{n}{j\cdot\binom{2n}{n+j}}&=\frac{1}{2n\cdot 4^{n}}\sum_{j=1}^{n}{2j\cdot\binom{2n}{n+j}}\\ \\ &=\frac{1}{2n\cdot 4^{n}}\cdot 2n\cdot\binom{2n-1}{n-1}\\ \\ &=\frac{1}{4^{n}}\cdot\binom{2n-1}{n-1} \end{align} $$