Concrete Mathematics (page 262 2nd ed.) demonstrates $x^n = \sum_k \left\{ \begin{matrix} n \\ k \\ \end{matrix} \right\} x^{\underline{k}}$ using a proof by induction:
$$ \begin{align} x \sum_k \left\{ \begin{matrix} n-1 \\ k \\ \end{matrix} \right\} x^{\underline{k}} &= \sum_k \left\{ \begin{matrix} n-1 \\ k \\ \end{matrix} \right\} x^{\underline{k+1}} + \sum_k \left\{ \begin{matrix} n-1 \\ k \\ \end{matrix} \right\} kx^{\underline{k}} \tag{1} \\ &= \sum_k \left\{ \begin{matrix} n-1 \\ k-1 \\ \end{matrix} \right\} x^{\underline{k}} + \sum_k \left\{ \begin{matrix} n-1 \\ k \\ \end{matrix} \right\} kx^{\underline{k}} \tag{2} \\ &= \sum_k \left( k \left\{ \begin{matrix} n-1 \\ k \\ \end{matrix} \right\} + \left\{ \begin{matrix} n-1 \\ k-1 \\ \end{matrix} \right\} \right) x^{\underline{k}} = \sum_k \left\{ \begin{matrix} n \\ k \\ \end{matrix} \right\} x^{\underline{k}} \tag{3} \end{align} $$
(1) is due to $ x \cdot x^{\underline{k}} = x^{\underline{k+1}} + kx^{\underline{k}}$.
(3) is an application of the recurrence relation for Stirling numbers of the second kind.
How do we get (2) from (1)?
It is important to make the summation ranges explicit ( to be sure (to be sure)) \begin{eqnarray*} x \sum_{k=1}^{n-1} \left\{ \begin{matrix} n-1 \\ k \\ \end{matrix} \right\} x^{\underline{k}} &=& \sum_{k=1}^{n-1} \left\{ \begin{matrix} n-1 \\ k \\ \end{matrix} \right\} x^{\underline{k+1}} + \sum_{k=1}^{n-1} \left\{ \begin{matrix} n-1 \\ k \\ \end{matrix} \right\} kx^{\underline{k}} \tag{1} \\ &=& \sum_{k'=2}^{n} \left\{ \begin{matrix} n-1 \\ k'-1 \\ \end{matrix} \right\} x^{\underline{k'}} + \sum_{k=1}^{n-1} \left\{ \begin{matrix} n-1 \\ k \\ \end{matrix} \right\} kx^{\underline{k}} \tag{2a} \\ &=& \sum_{k=1}^{n} \left\{ \begin{matrix} n-1 \\ k-1 \\ \end{matrix} \right\} x^{\underline{k}} + \sum_{k=1}^{n} \left\{ \begin{matrix} n-1 \\ k \\ \end{matrix} \right\} kx^{\underline{k}} \tag{2b} \\ &=& \sum_{k=1}^{n} \left( k \left\{ \begin{matrix} n-1 \\ k \\ \end{matrix} \right\} + \left\{ \begin{matrix} n-1 \\ k-1 \\ \end{matrix} \right\} \right) x^{\underline{k}} = \sum_{k=1}^{n} \left\{ \begin{matrix} n \\ k \\ \end{matrix} \right\} x^{\underline{k}} \tag{3} \end{eqnarray*} To go from $(1)$ to $(2a)$ a change of variable occur $k'=k+1$ in the first sum.
To go from $(2a)$ to $(2b)$ note that $\left\{ \begin{matrix} n-1 \\ 0 \\ \end{matrix} \right\}= 0 $ and $\left\{ \begin{matrix} n-1 \\ n \\ \end{matrix} \right\}= 0 $ so the summation ranges can be extended.