12
$\begingroup$

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

$\endgroup$
12
  • $\begingroup$ Have you tried computing a few values? $\endgroup$ May 5 at 6:04
  • $\begingroup$ @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$!!!! $\endgroup$
    – DatBoi
    May 5 at 6:12
  • $\begingroup$ Yep, that is what I got, computationally. $4^{n}=2^{2n}.$ $\endgroup$ May 5 at 6:18
  • $\begingroup$ I suggest rechecking the geometric series you got, looks a bit off to me. Maybe I am missing something $\endgroup$
    – Buraian
    May 5 at 6:24
  • 2
    $\begingroup$ 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. $\endgroup$
    – JimmyK4542
    May 5 at 6:38
1
$\begingroup$

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

$\endgroup$
3
$\begingroup$

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

$\endgroup$
2
$\begingroup$

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

$\endgroup$
1
  • $\begingroup$ 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 $\endgroup$
    – Buraian
    May 6 at 10:39
2
$\begingroup$

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

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

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 .
$\endgroup$
5
  • $\begingroup$ Can you please elaborate more on line 4 to 5? $\endgroup$
    – DatBoi
    May 8 at 16:00
  • $\begingroup$ $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 $\endgroup$
    – G Cab
    May 8 at 16:59
  • $\begingroup$ High ingenuity proof $\endgroup$
    – Buraian
    May 8 at 17:10
  • $\begingroup$ I also don't get what happend in 4->5 , how did the binomial product turn to that? $\endgroup$
    – Buraian
    May 8 at 17:11
  • $\begingroup$ @Buraian: that's the Vandermonde convolution $\endgroup$
    – G Cab
    May 8 at 17:20
2
$\begingroup$

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

This leads to:

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

For more information about cauchy product rule, you can check out my article about it here

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

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

$\endgroup$
10
  • $\begingroup$ Thank you very much for the answer! My knowledge is limited to calc2, ill look at this when I learn complex analysis :P $\endgroup$
    – DatBoi
    May 5 at 6:44
  • $\begingroup$ 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) $\endgroup$
    – Thomas
    May 5 at 7:04
  • $\begingroup$ 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. $\endgroup$
    – user
    May 5 at 8:13
  • $\begingroup$ @user I'll agree about the r being confusing - and so lets swap it from r to R. $\endgroup$ May 5 at 8:33
  • 1
    $\begingroup$ @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.$$ $\endgroup$ May 6 at 2:21
1
$\begingroup$

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

$\endgroup$
1
  • $\begingroup$ "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$". $\endgroup$
    – user
    May 5 at 8:21

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.