<s>[INST] Inductive proof of sum of falling factorials with Stirling number coefficients 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)?
 [/INST] 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.
</s>