Stirling Numbers of second kind defined in terms of coefficients Prove that $t^n = \sum_{k=1}^n S(n,k)t^{\underline k}$ where $t^{\underline k}$ denotes the $k$-th falling power $t(t-1)(t-2)\ldots(t-k+1)$ of$~t$.
I know that we'll have to use the recurrence relation for $S(n,k)$ here but since the summation itself involves $k$, I'm confused as how will we convert $(t-k)$ into $t^{\underline{k+1}}$. Thanks. 
 A: For the induction proof as per the comment we use
$${n+1\brace k} = k{n\brace k} + {n\brace k-1}$$
which says that we  put $n+1$ into one of $k$ sets  of a set partition
of $n$ into  $k$ sets or we join  it as a singleton to  a partition of
$n$ into $k-1$ sets. The base case is
$$t^1 = \sum_{k=1}^1 {1\brace k} t^\underline{k} = t$$
and we see that it holds. Now suppose that
$$t^n = \sum_{k=1}^n {n\brace k} t^\underline{k}$$
which implies
$$t^{n+1} = \sum_{k=1}^n {n\brace k} t\times t^\underline{k}
\\ = \sum_{k=1}^n {n\brace k} (t-k)\times t^\underline{k}
+ \sum_{k=1}^n {n\brace k} k \times t^\underline{k}
\\ = \sum_{k=1}^n {n\brace k} t^\underline{k+1}
+ \sum_{k=1}^n {n\brace k} k \times t^\underline{k}
\\ = \sum_{k=2}^{n+1} {n\brace k-1} t^\underline{k}
+ \sum_{k=1}^n {n\brace k} k \times t^\underline{k}.$$
Now ${n\brace 0} = {n\brace n+1} = 0$ so this is
$$\sum_{k=1}^{n+1} {n\brace k-1} t^\underline{k}
+ \sum_{k=1}^{n+1} {n\brace k} k \times t^\underline{k}.$$
Apply the recurrence to get
$$t^{n+1} = \sum_{k=1}^{n+1} {n+1\brace k} t^\underline{k}.$$
