Show that for every natural number $n$ there is equality - Stirling numbers of the second kind

Question

Show that for every natural number $n$ there is equality:
$$\left\{ n\atop 3\right\} = \frac{3^{n-1}-2^n+1}{2}$$
To prove this equality use equality $${{n+1}\brace{m+1}} = \sum_{k=0}^{n}{n\choose k}{{k}\brace{m}}$$ and binomial theorem.
Could someone help me with this exercise? I don't know how to go about it ... Thank you!

Answer 1

Just in case you learn about EGFs soon we have from the EGF

$${n\brace k} = n! [z^n] \frac{(\exp(z)-1)^k}{k!}$$

that

$${n\brace 3} = n! [z^n] \frac{(\exp(z)-1)^3}{6} = \frac{1}{6} n! [z^n] (\exp(3z) - 3 \exp(2z) + 3 \exp(z) - 1) \\ = \frac{1}{6} (3^n - 3 \times 2^n + 3) = \frac{1}{2} (3^{n-1} - 2^n + 1)$$

where $n\ge 1.$