# 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?

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