Stirling Numbers of second kind defined in terms of coefficients

Question

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.

Answer 1

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}.$$