Evaluate $\sum_{r=0}^n 2^{n-r} \binom{n+r}{r}$

Solution 1:

Let $$ S_n:=\sum_{k=0}^n\frac{\binom{n+k}{k}}{2^{n+k}} $$ Obviously $S_0=1$. Assume that equality $$S_{n-1}=1\tag1$$ is valid for some $n$. Then it is valid for $n+1$ as well: $$ \begin{align} S_n &=\sum_{k=0}^n\frac{\binom{n+k}{k}}{2^{n+k}}\\ &=\sum_{k=0}^n\frac{\binom{n+k-1}{k-1}+\binom{n-1+k}{k}}{2^{n+k}}\\ &=\frac12\sum_{k=0}^{n-1}\frac{\binom{n+k}{k}}{2^{n+k}}+\frac12\sum_{k=0}^n\frac{\binom{n-1+k}{k}}{2^{n-1+k}}\\ &=\frac12S_n-\frac{\binom{2n}{n}}{2^{2n+1}}+\frac12S_{n-1}+\frac{\binom{2n-1}{n}}{2^{2n}}\\ &=\frac12S_n+\frac12S_{n-1}\implies S_n=S_{n-1}\stackrel{I.H.}=1. \end{align} $$

Thus, by induction the equality $(1)$ is valid for all integer $n\ge0$.

Accordingly your sum is $2^{2n}S=4^n$.

Solution 2:

Consider the number of binary strings that are $(2n+1)$ digits long with at least $(n+1)$ digits equal to $1$. Let this number be $S$.

Method 1: Flip the $1$'s into $0$'s and vice versa. This covers all binary strings of length $2n+1$: so $2S=2^{2n+1}\implies S=2^{2n}$

Method 2: Consider the $(n+1)th$ $1$ digit. Suppose this is the $(n+1+r)$th digit of the string. Then this yields the desired sum by hockey stick.

So the answer is $\boxed{2^{2n}}$.

Solution 3:

In another way $$ \eqalign{ & S = \sum\limits_{r = 0}^n {2^{\,n - r} \left( \matrix{ n + r \cr r \cr} \right)} = \cr & = \sum\limits_{k = 0}^n {\left( \matrix{ 2n - k \cr n - k \cr} \right)2^{\,k} = } \quad (1)\cr & = \sum\limits_{0\, \le \,k} {\left( \matrix{ 2n - k \cr n - k \cr} \right)2^{\,k} } = \quad (2) \cr & = \sum\limits_{0\, \le \,k} {\left( \matrix{ 2n - k \cr n - k \cr} \right)\left( {1 + 1} \right)^{\,k} } = \sum\limits_{0\, \le \,k} {\sum\limits_{0\, \le \,j} {\left( \matrix{ 2n - k \cr n - k \cr} \right) \left( \matrix{ k \cr k - j \cr} \right)} } = \quad (3) \cr & = \sum\limits_{0\, \le \,j} {\left( { - 1} \right)^{\,n - j} \sum\limits_{\left( {0\, \le } \right)\,k} {\left( \matrix{ - n - 1 \cr n - k \cr} \right)\left( \matrix{ - j - 1 \cr k - j \cr} \right)} } = \quad (4) \cr & = \sum\limits_{0\, \le \,j} {\left( { - 1} \right)^{\,n - j} \left( \matrix{ - n - j - 2 \cr n - j \cr} \right)} = \quad (5) \cr & = \sum\limits_{0\, \le \,j} {\left( \matrix{ 2n + 1 \cr n - j \cr} \right)} = \sum\limits_{k = 0}^n {\left( \matrix{ 2n + 1 \cr k \cr} \right)} = \quad (6)\cr & = {1 \over 2}\sum\limits_{k = 0}^{2n + 1} {\left( \matrix{ 2n + 1 \cr k \cr} \right)} = 2^{\,2n} \quad (7) \cr} $$ where the steps are:

• 1. change index;
• 2. remove upper bound (it is implicit in the binomial);
• 3. split the $2$;
• 4. upper negation ( $\binom{n}{m}=(-1)^m \binom{m-n-1}{m}$ ) on both binomials;
• 5. convolution in $k$,
• 6. upper negation;
• 7. symmetry of the binomial .

Solution 4:

OP's second method can be made to work and it gives the simplest as in the following solution.

$$S=\text{Coefficient of $x^n$ in}~~ (1+x)^n\left(\frac{(1+x)^{n+1}-2^{n+1}}{(x-1)}\right).$$ $$S=-\text{Coefficient of $x^n$}~ \text{in} \left((1+x)^{2n+1}(1-x)^{-1}-2^{n+1}(1-x)^{-1}\right)$$ $$S=-\text{Coefficient of $x^n$}~ \text{in} \left((1+x)^{2n+1}\sum_{k=0}^{\infty} x^k-2^{n+1}\sum_{k=0}^{\infty}x^k\right)$$ $$S=- \left(\sum_{k=0}^{n} {2n+1\choose k}-2^{n+1}\sum_{k=0}^{\infty}{n \choose k}\right)=-2^{2n}+2^{2n+1}=2^{2n}$$