Show by counting in two ways that $\sum_{k=0}^{n} \binom{n+k}{k} = \sum_{k=0}^{n} 2^{k} \binom{n}{k}$?

Question

How does one approach a question like this?

Show by counting in two ways that $\sum_{k=0}^{n} \binom{n+k}{k} = \sum_{k=0}^{n} 2^{k} \binom{n}{k}$

In general, the fact that $k$ can vary from $0$ to $n$ suggests to me that we can consider a universe of $2n$ objects and $2^k$ suggests that subsets are involved.

I have tried a variety of approaches using those ideas, but can't find a nice, simple, interpretation of $\sum_{k=0}^{n} \binom{n+k}{k}$ specifically

Answer 1

Assume to have a group of $n$ people and to want to assign to each member

1. no medal
2. a silver medal
3. a gold medal.

Clearly you have $3^n$ ways for doing it, i.e. simply choosing type-1, type-2 or type-3 for each member.
On the other hand these configurations can be counted in many other fancy ways. For instance, we may select the people actually getting a medal, then choosing among this subset who gets a silver medal and who gets a gold medal. This leads to: $$ 3^n = \sum_{k=0}^{n}\binom{n}{k}2^k. $$ The other sum is different. By the hockey-stick identity $$ \sum_{k=0}^{n}\binom{n+k}{k}=\sum_{k=0}^{n}\binom{n+k}{n}=\sum_{h=n}^{2n}\binom{h}{n}=\binom{2n+1}{n+1}=\binom{2n+1}{n}=\frac{2n+1}{n+1}\binom{2n}{n} $$ which roughly behaves like $2\cdot\frac{4^n}{\sqrt{\pi n}}$ for large values of $n$.

Answer 2

Take $n = 2$. Now,

$$ {2 \choose 0} + {3 \choose 1} + {4 \choose 2} = 1 + 3 + 6 = 10 $$

and

$$ 2^0{2 \choose 0} + 2^1{2 \choose 1} + 2^2{2 \choose 2} = 1 + 4 + 4 = 9 $$

so the problem is not correct, as stated.

In general, we have

$$ \sum_{k = 0}^n{m+k \choose k} = {n+m+1 \choose n} $$

The intuition is that subsets of size $n$ correspond to subsets of size $m+1$ via their complement. Now, fixing a last element $l+1$ there are $m$ to choose from $\{1, \dots l\}$, or $l-m$ to discard. I'll leave you to justify why $m \leq l \leq n+m$ and so we can express $l$ as $m+k$ with $0 \leq k \leq m$. In your particular case, $n = m$.

Also, $$ \sum_{k = 0}^n2^k{n \choose k} = 3^n $$

via either the binomial theorem, or the following interpretation: let's from words of $n$ characters with three letters $A,B,C$. Pick $k$ out of the $n$ to be either $B$ or $C$, thus determining the rest to be $A$. Now, for each one of the $k$ we have $2$ options to pick, thus rendering a total of $2^k{n \choose k}$ for each $k$, and summing these all gives the desired result.