Proving the identity $\sum_{k = r}^n {n \choose k}{k \choose r}2^k = {n \choose r}2^r3^{n - 2}$

Question

I want to prove the following identity:
$$\sum_{k = r}^n {n \choose k}{k \choose r}2^k = {n \choose r}2^r3^{n - 2}$$

I tried creating a counting problem: Suppose we have $2$ houses and $n$ people. But we are crazy and since kicking people out gives us joy, by the end of the month we want to kick exactly $r$ people out. Now for a fixed $k$ suppose we want to give houses to exactly $k$ people. First we pick these $k$ people in $n \choose k$ ways, and distribute them among the $2$ houses in $2^k$ ways. Then we pick the $r$ unlucky people in $k \choose r$ ways.
Now to count all the possibilities of giving people houses and kicking $r$ of them out, we need to iterate all the possibilities of $k$ which should be in the range $[r, n]$. So there will be $\sum_{k = r}^n {n \choose k}{k \choose r}2^k$ possibilities.

Now I have 2 problems. The first one is that I'm not sure if I'm counting every possibility only once above. My second problem is showing that the right hand side is counting the same thing. I mean we could first pick the $r$ unlucky people and distribute them among the $2$ houses, and then every other person will have 3 possibilities. Either stay homeless, or go to one of the two houses. But this will give us the number ${n \choose r}2^r3^{n - r}$.

Hints would be appreciated and thanks in advance.

Answer 1

Here's a counting argument (for the corrected formula, i.e., where the exponent on $3$ is $n-r$). Say we want to count the number of strings of length $n$ with $r$ places taking the values $3$ or $4$ and the other $n-r$ taking values $0, 1$ or $2$. Clearly this is ${n \choose r}2^r 3^{n-r}$. Now consider constructing an instance of this sequence in the following way: we choose $k \geq r$ spots in the string and assign to these spots $1$ or $2$ and assign $0$ to the remaining $n-k$ spots. There are $2^k$ such possible sequences of $1$s and $2s$ filling the chosen $k$ spots. We then choose $r$ places from the $k$ we have selected and replace spots with value $1$ by $3$ and those with value $2$ by $4$. This is clearly an instance of the kind of string we want, and there are ${n \choose k} {k \choose r} 2^k$ of these strings for given $k$. Now just sum over $r \le k \le n$ and we get ${n \choose r}2^r 3^{n-r}$ (as we are counting all possible cases of our desired string type in this way-can you see why?).