How to prove combinatorial summations?

Question

I don't know where to start to prove combinatorial sums. For example, how can I prove that, given $n\in \mathbb N, 0 \le k \le n$$$\sum_{k=0}^n 2^k\binom{n}{k} = 3^n$$

I bet it's a very simple identity to prove, but I don't know what to do.

Answer 1

You can show by induction, and more generally, that for all real $a$ and $b$

$$ \left(a+b\right)^n=\sum_{k=0}^{n}\binom{n}{k}a^kb^{n-k} $$

Start with case $n=0$. Then suppose it is true until a certain rank $n$, and show it is again true for the index $n+1$. You should use the Pascal's formula which is $$ \binom{n}{k}+\binom{n}{k+1}=\binom{n+1}{k+1} $$

Answer 2

Another nice proof is by double counting. We count the vectors with $n$ coordinates each taking values 0, 1 or 2. Clearly since we have 3 options for each coordinate, and $n$ coordinates, we have $3^n$ such vectors. Another way of counting them is by counting for each $k$, the number of vectors with $k$ coordinates equal to 0 or 1. The number of choices for the set of coordinates equal to 0 or 1 is $\binom{n}{k}$ and the number of choices for which coordinates are 1 and which are 0 in this set is $2^k$ which gives us $\binom{n}{k}2^k$. Summing over $k$ we get the result we want.

Answer 3

$$\sum_{k=0}^n \binom nk2^k=(1+2)^n=3^n$$

Answer 4

I don't know where to start to prove combinatorial sums. For example ...

The existing answers tackle the example, but the answer to the more general question is that these sums tend to have hypergeometric terms, so Gosper's algorithm for indefinite sums or definite sums with arbitrary endpoints (which is pretty much the same thing), and Zeilberger's algorithm for sums over the whole support.