One of my favorite facts from combinatorics is that $\sum\limits_{0\leq k\leq n}\binom{n}{k} = 2^{n}$. To prove it is simple: Note that $2 = 1 + 1$, and that $\binom{n}{k} = \binom{n}{k}\cdot 1^{k}\cdot 1^{n-k}$, and appeal to binomial theorem:
$$\sum_{0\leq k\leq n}\binom{n}{k} = \sum_{0\leq k\leq n}\binom{n}{k}\cdot 1^{n-k}\cdot 1^{k} = \left(1+1\right)^{n} = 2^{n}.$$
But what can we say about $\sum\limits_{1\leq k\leq n}k\binom{n}{k}$, or maybe even more general binomial coefficient sums?
It turns out that there’s a really nice combinatorial proof for the closed form of this sum.
Proposition.
$$\sum_{1\leq k\leq n}k\binom{n}{k} = n2^{n-1}.$$
Proof. Suppose we want to make a committee out of a subset of $n$ people, where one member of the committee will be selected as the leader of the committee.
On one hand, there are $n$ choices for the leader, and then $2^{n-1}$ choices for the rest of the committee. Therefore, there are $n2^{n-1}$ total choices for a committee with one leader.
On the other hand, we can consider each potential committee size separately. If we fix $k$ as the size of the committee, then we have $\binom{n}{k}$ choices for the $k$ members of the committee, and then $k$ choices from those for the leader of the committee, giving $k\binom{n}{k}$ choices for a committee of size $k$ with one leader. Summing over all committee sizes, and noting that this sum will equal the expression we got before, we get
$$\sum_{1\leq k\leq n}k\binom{n}{k} = n2^{n-1}. \textbf{ QED}$$
Of course, now that we’ve made this argument, we can pretty much immediately generalize to committees with multiple leaders.
Proposition.
$$\sum_{d\leq k\leq n}\binom{n}{k}\binom{k}{d} = \binom{n}{d}2^{n-d}.$$
The proof is almost exactly the same as before, so I’ll leave it as an exercise for the reader.
Now suppose we vary the number of leaders, say $0\leq d\leq n$?
It turns out that we get to use the trick from the introduction!
Corollary.
$$\sum_{0\leq d\leq n}\sum_{d\leq k\leq n}\binom{n}{k}\binom{k}{d} = 3^{n}.$$
Proof. Since the inner sum is $\sum\limits_{d\leq k\leq n}\binom{n}{k}\binom{k}{d} = \binom{n}{d}2^{n-d} = \binom{n}{d}2^{n-d}\cdot 1^{d}$, the full sum can be evaluated by appealing to the binomial theorem. That is,
$$\sum_{0\leq d\leq n}\sum_{d\leq k\leq n}\binom{n}{k}\binom{k}{d} = \sum_{0\leq d\leq n}\binom{n}{d}2^{n-d}\cdot 1^{d} = \left(2+1\right)^{n} = 3^{n}. \textbf{ QED}$$