Show by counting in two ways that $\sum_{k=0}^{n} \binom{n+k}{k} = \sum_{k=0}^{n} 2^{k} \binom{n}{k}$? 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
 A: 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.
A: Assume to have a group of $n$ people and to want to assign to each member


*

*no medal

*a silver medal

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