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

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

This looks like an unusual hockey stick sum. Here are my attempts:

### Method 1:

The sum is equivalent to

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

and I could evaluate neither of these.

### Method 2:

$$S=\text{coefficient of x^n in }:$$

$$2^n(1+x)^n\Bigg( 1+\frac{1+x}{2}+\left(\frac{1+x}{2}\right)^2+\cdots+\left(\frac{1+x}{2}\right)^n \Bigg)$$

$$=(1+x)^n\left(\frac{(1+x)^{n+1}-2^{n+1}}{(x-1)}\right)$$

It looks like a heavy task to collect all the $$x^n$$ coefficients from this expression.

Im out of ideas. Any hint is appreciated.

From Putnam 2020, Q A2

• Have you tried computing a few values? May 5 at 6:04
• @ThomasAndrews I found these: $S(0)=1=4^0,S(1)=4,S(2)=16,S(3)=64$. It looks like a GP with common ratio $4$!!!! May 5 at 6:12
• Yep, that is what I got, computationally. $4^{n}=2^{2n}.$ May 5 at 6:18
• I suggest rechecking the geometric series you got, looks a bit off to me. Maybe I am missing something May 5 at 6:24
• FYI: This is 2020 Putnam Exam Problem A2. The contest ended a few months ago, so it's ok to post this. But it should be cited. May 5 at 6:38

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}$$

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$$.

In seeking to evaluate

$$S_n = \sum_{r=0}^n 2^{n-r} {n+r\choose r}$$

we find that it is

$$[z^n] \frac{1}{1-2z} \frac{1}{(1-z)^{n+1}} = \mathrm{Res}_{z=0} \frac{1}{z^{n+1}} \frac{1}{1-2z} \frac{1}{(1-z)^{n+1}}.$$

We will use the fact that residues sum to zero, which requires the residue at $$z=1/2$$ and the residue at $$z=1$$ as well as the residue at infinity. The latter is zero by inspection, however . We get for the residue at $$z=1/2$$

$$-\frac{1}{2} \mathrm{Res}_{z=1/2} \frac{1}{z^{n+1}} \frac{1}{z-1/2} \frac{1}{(1-z)^{n+1}}$$

We obtain

$$- \frac{1}{2} 2^{n+1} 2^{n+1} = - 2 \times 4^n.$$

We also have for the residue at $$z=1$$

$$\mathrm{Res}_{z=1} \frac{1}{z^{n+1}} \frac{1}{1-2z} \frac{1}{(1-z)^{n+1}} \\ = \mathrm{Res}_{z=1} \frac{1}{(1+(z-1))^{n+1}} \frac{1}{-1-2(z-1)} \frac{1}{(1-z)^{n+1}} \\ = (-1)^n \mathrm{Res}_{z=1} \frac{1}{(1+(z-1))^{n+1}} \frac{1}{1+2(z-1)} \frac{1}{(z-1)^{n+1}}.$$

This is

$$(-1)^n \sum_{r=0}^n (-1)^r {n+r\choose r} (-1)^{n-r} 2^{n-r} = \sum_{r=0}^n 2^{n-r} {n+r\choose r} = S_n.$$

We have shown that $$S_n - 2 \times 4^n + S_n = 0$$ or

$$\bbox[5px,border:2px solid #00A000]{ S_n = 4^n.}$$

For the residue at infinity we get

$$-\mathrm{Res}_{z=0} \frac{1}{z^2} z^{n+1} \frac{1}{1-2/z} \frac{1}{(1-1/z)^{n+1}} = - \mathrm{Res}_{z=0} z^n \frac{1}{z-2} \frac{z^{n+1}}{(z-1)^{n+1}} \\ = - \mathrm{Res}_{z=0} z^{2n+1} \frac{1}{z-2} \frac{1}{(z-1)^{n+1}} = 0.$$

• Oh jeez, this is a great answer :) I wish I knew enough residue calculus, I had got to the same step with the denominators but didn't know how to pull the coefficients May 6 at 10:39

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}}$$.

• Not gonna lie, this sounds good but I don't fully understand it. Could you explain where the binary strings came from? May 7 at 6:07
• Engineers induct to see the powers of two. Looking for a bijection with powers of two: binary is the way to go. May 7 at 16:52

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;
1. remove upper bound (it is implicit in the binomial);
1. split the $$2$$;
1. upper negation ( $$\binom{n}{m}=(-1)^m \binom{m-n-1}{m}$$ ) on both binomials;
1. convolution in $$k$$,
1. upper negation;
1. symmetry of the binomial .
• Can you please elaborate more on line 4 to 5? May 8 at 16:00
• $2 \to 3$ just replacing $2$ with $(1+1)$ and apply binomial expansion; $3 \to 4$ applying the "upper negation" $\binom{n}{m}=(-1)^m \binom{m-n-1}{m}$ to both terms May 8 at 16:59
• High ingenuity proof May 8 at 17:10
• I also don't get what happend in 4->5 , how did the binomial product turn to that? May 8 at 17:11
• @Buraian: that's the Vandermonde convolution May 8 at 17:20

$$(1+x)^n\left(\frac{(1+x)^{n+1}-2^{n+1}}{(x-1)}\right)$$

You were on the right path, but you just didn't take the final step. Finish:

$$\frac{(1+x)^n 2^{n+1} }{(1-x)} - \frac{(1+x)^{2n+1} }{(1-x)}$$

Now, I will introduce a 'nice' result( By the cauchy product rule):

$$\frac{ P(x)}{1-x}= (\sum_i x^i) \sum_{i} a_i x^i = \sum_u c_ux^u$$

Where:

$$c_u = \sum_{i=0}^u a_i \tag{1}$$

Hence, the applying the coefficient operator and use(1) while I'm at it:

$$[x^n] \left[\frac{(1+x)^n 2^{n+1} }{(1-x)} - \frac{(1+x)^{2n+1} }{(1-x)} \right] = 2^{n+1} [x^n] \left[ \frac{(1+x)^n}{1-x} \right]- [x^n] \left[ \frac{(1+x)^{2n+1} }{1-x} \right]\\= 2^{n+1} \sum_{i=0}^n \binom{n}{i}-\sum_{i=0}^n \binom{2n+1}{i}$$

Now, by standard results we can work out the first binomial sum:

$$2^{n+1} \sum_{i=0}^n \binom{n}{i} = 2^{2n+1}$$

And, the tricky sum/one step more complicated sum is:

$$S= \sum_{i=0}^n \binom{2n+1}{i} = \sum_{i=0}^n \binom{2n+1}{(2n+1)-i} = \sum_{i=0}^n \binom{2n+1}{(2n+1) - (n-i) } = \sum_{i=0}^n \binom{2n+1}{n+1+i}$$

$$2S = \sum_{i=0}^n \binom{2n+1}{i} + \sum_{i=0}^n \binom{2n+1}{n+1+i} = \sum_{i=0}^n \binom{2n+1}{i} = 2^{2n+1}$$

Or,

$$S= 2^{2n}$$

Put everything together and you have the answer of $$4^n$$.

• Note: (1+x)^n you can directly take out the bracket May 5 at 6:25
• You are absolutely correct @ThomasAndrews May 5 at 6:27

Consider $$\left( \begin{matrix} n \\ k \\ \end{matrix} \right)=\frac{1}{2\pi i}\int\limits_{\left| z \right|=R}^{{}}{\frac{{{\left( 1+z \right)}^{n}}}{{{z}^{k+1}}}dz}$$ so $$\sum\limits_{r=0}^{n}{{{2}^{n-r}}\left( \begin{matrix} n+r \\ r \\ \end{matrix} \right)}=\frac{1}{2\pi i}\int\limits_{\left| z \right|<1}^{{}}{\sum\limits_{r=0}^{n}{{{2}^{n-r}}}\frac{{{\left( 1+z \right)}^{n+r}}}{{{z}^{r+1}}}dz}=\\\frac{1}{2\pi i}\int\limits_{\left| z \right|<1}^{{}}{\frac{{{2}^{n+1}}{{\left( 1+z \right)}^{n}}}{z-1}-\frac{{{\left( 1+z \right)}^{1+2n}}}{\left( z-1 \right){{z}^{n+1}}}dz}\\=\frac{1}{2\pi i}\int\limits_{\left| z \right|<1}^{{}}{\frac{{{\left( 1+z \right)}^{1+2n}}}{\left( 1-z \right){{z}^{n+1}}}dz}$$

Where for convenience we've chosen a circular contour enclosing the origin with radius less than $$1$$. We can do this because directly after the summation the only contribution comes from a residue at $$z=0$$ (note there is no residue at $$z=1$$ in the second line). The final line above reflects this. Now to get the residue at $$z=0$$... $$res\frac{{{\left( 1+z \right)}^{1+2n}}}{\left( 1-z \right){{z}^{n+1}}}=res\sum\limits_{m=0}^{\infty }{{}}\sum\limits_{k=0}^{\infty }{\left( \begin{matrix} 1+2n \\ k \\ \end{matrix} \right)\frac{1}{{{z}^{n+1-m-k}}}}\\=\sum\limits_{m=0}^{\infty }{\left( \begin{matrix} 1+2n \\ n-m \\ \end{matrix} \right)=}\sum\limits_{m=0}^{n}{\left( \begin{matrix} 1+2n \\ n-m \\ \end{matrix} \right)}=\sum\limits_{m=0}^{n}{\left( \begin{matrix} 1+2n \\ m \\ \end{matrix} \right)}={{4}^{n}}$$ hence $$\sum\limits_{r=0}^{n}{{{2}^{n-r}}\left( \begin{matrix} n+r \\ r \\ \end{matrix} \right)}={{4}^{n}}$$

• Thank you very much for the answer! My knowledge is limited to calc2, ill look at this when I learn complex analysis :P May 5 at 6:44
• At the end this approach is based on the same ideas of your second approach, even if it is written in a more "complex" language. (1) Start from interpreting the general term of the summation as the coefficient of a certain order of a binomial expansion. The complex integral is a way to "extract" the right coefficient from (1+z)^n (2) , and we see also appearing a geometric dependance on n, which is good (2) commute this representation with the summation and than extract again the coefficient. At least this is how I see it now... (+1 from me I like this approach) May 5 at 7:04
• I would assume that the integration domain $|z|<1$ is not correct. Besides the usage of $|z|=r$ in the first integral is at the least misleading as you use the symbol $r$ later in the other sense.
– user
May 5 at 8:13
• @user I'll agree about the r being confusing - and so lets swap it from r to R. May 5 at 8:33
• @mathstackuser12 Note that $$\frac{1}{2\pi i} \int_{|z|=\varepsilon} \frac{1}{z^{n+1}} \frac{1}{1-z} (1+z)^{2n+1} \; dz = [z^n] \frac{1}{1-z} (1+z)^{2n+1} \\= \sum_{k=0}^n [z^{n-k}] \frac{1}{1-z} [z^k] (1+z)^{2n+1} = \sum_{k=0}^n {2n+1\choose k} = \frac{1}{2} 2^{2n+1} = 4^n.$$ May 6 at 2:21

A combinatorial proof.

Let $$U=\{A\subseteq \{1,2,\dots,2n+1\}, |A|>n\}.$$

We have that $$|U|=2^{2n+1}/2=2^{2n}.$$

Given an $$A\in U,$$ define $$m(A)$$ as the largest number such that $$|A\cap\{1,2,\dots,n+r\}|=n.$$ $$m(A)$$ can be anywhere from $$0$$ to $$n,$$ and we always have $$m(A)+1\in A.$$

Let $$U_r=\{A\in U\mid m(A)=r\}.$$ What is the size of $$U_r?$$ We can choose any $$n$$ elements from $$1,2,\dots,n+r$$, add the element $$n+r+1,$$ and then any subset of elements from the remaining $$n-r$$ elements. So $$|U_r|=\binom{n+r}{n}2^{n-r}.$$

and: $$4^{n}=2^{2n}=|U|=\sum_{r=0}^{n}|U_r|=\sum_{r=0}^{n}2^{n-r}\binom{n+r}n$$

• "define $m(A)$ as the largest number such that $|A\cap\{1,2,\dots,n+r\}|=n.$" This is not understandable. Probably you meant "the largest number $r$".
– user
May 5 at 8:21