Prove $3^{n−2} n (n − 1) = \sum_{k=2}^{n} \binom{n}{k} (k)(k − 1)2^{k−2}$ for $n\ge3$

Question

The question asks for a combinatorial proof only.

In my attempt, I rewrote $3^{n-2}$ as $(1+2)^{n-2}$. Then using binomial theorem, i was able to get $(1+2)^{n-2} = \sum_{k=2}^{n} \binom{n}{k} 2^k$.

I don't know how to proceed from here.

Answer 1

Hint: Consider the second derivative of $(1+x)^n$ at $x=2$.

Answer 2

This can be done combinatorially. Consider $n$ objects. The left is the number of ways to Color one red, one blue, and label each of the others a number from $1$ to $3$. We could also do this by choosing $n - k$ numbers to label $3$; there are $\binom{n}{k}$ ways to do this. From the numbers not labeled $3$, we must color one red, one blue and label the rest $1$ or $2$.