What is the generalised recurrence for Stirling numbers of the second kind? The Stirling numbers of the second kind obey the well-known recurrence relation:
$$S(n,k) = k \cdot S(n-1,k) + S(n-1,k-1).$$
This recurrence relation reduces the value of the first argument in the Stirling numbers by one.  I would like to apply this recurrence relation iteratively, allowing me to reduce the first argument by some arbitrary value $t \in \mathbb{N}$.  This will give me a generalised recurrence of the form:
$$S(n,k) = \sum_{i=0}^t a_{t,i} \cdot S(n-t,k-i),$$
where the coefficients $a_{t,i}$ also depend implicitly on the fixed value $k$.  So far I have not found an explicit expression for these coefficients, and hence for the generalised recurrence.  I have managed to characterise the coefficients recursively by:
$$a_{t,0} = k^t \quad \quad \quad a_{t,t} = 1
\quad \quad \quad a_{t+1,i} = a_{t,i-1} + (k-i) \cdot a_{t,i}.$$
Can anyone identify the coefficients in this generalise recursion, and give an explicit formula for these coefficients?
 A: I'll denote ${n\brace k}:=S(n,k)$ for more symmetry with $\binom{n}{k}$. So, from
$${n\brace k}=k{n-1\brace k}+{n-1\brace k-1}$$
we get, using induction on $k$, that for $|x|<1/k$
$$\sum_{n=k}^{\infty}{n\brace k}x^n=\prod_{r=1}^{k}\frac{x}{1-rx}$$
(this is also well-known). Now suppose, as you do,
$${n\brace k}=\sum_{s=0}^{t}a_{t,s}(k){n-t\brace k-s};\tag{1}$$
then $\sum_{n=k}^{\infty}[\ldots]x^n$ gives, after changing the order of summation,
$$\prod_{r=1}^{k}\frac{x}{1-rx}=x^t\sum_{s=0}^{t}a_{t,s}(k)\prod_{r=1}^{k-s}\frac{x}{1-rx}.\tag{2}$$
Replacing $x$ with $1/(k-x)$ and using $(x)_s:=\prod_{r=0}^{s-1}(x-r)$, we get
$$(k-x)^t=\sum_{s=0}^{t}(-1)^s a_{t,s}(k)(x)_s.$$
On the other hand,
$$(k-x)^t=\sum_{r=0}^{t}\binom{t}{r}k^{t-r}(-1)^r\underbrace{\sum_{s=0}^{r}{r\brace s}(x)_s}_{=x^r}$$
Thus, by comparison,
$$\bbox[5px, border:1px solid]{a_{t,s}(k)=\sum_{r=s}^{t}{r\brace s}\binom{t}{r}(-1)^{r-s}k^{t-r}.}$$

UPDATE: Details on $(1)\implies(2)$. Formally, $\sum_{n=k}^{\infty}[\ldots]x^n$ gives $$\prod_{r=1}^{k}\frac{x}{1-rx}=\sum_{s=0}^{t}a_{t,s}(k)\sum_{n=\color{red}{k}}^{\infty}{n-t\brace k-s}x^n$$ but, in fact, a few leading terms in the inner sum are zero: $${n-t\brace k-s}\neq 0\implies n-t\geqslant k-s\implies n\geqslant k+t-s.$$ Thus, substituting $n\mapsto n+t$ additionally, $$\sum_{n=k}^{\infty}{n-t\brace k-s}x^n=\sum_{n=\color{red}{k+t-s}}^{\infty}{n-t\brace k-s}x^n=\sum_{n=k-s}^{\infty}{n\brace k-s}x^{n+t}=x^t\prod_{r=1}^{k-s}\frac{x}{1-rx}.$$
