What is the generalised recurrence for Stirling numbers of the second kind?

Question

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?

Answer 1

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