Roll a k-sided die over and over and sum the results. What's the probability that the result will eventually hit exactly n? The recursive formula is:
$$ p_{k,n}= \begin{cases} \begin{array}{cc} 0 & n<0 \\ 1 & n=0 \\ \sum _{x=1}^k \frac{p_{k,n-x}}{k} & n>0 \\ \end{array} \\ \end{cases} $$
Through extremely tedious trial and error, I found the closed form: $$ p_{k,n}= \frac{(k+1)^{n-1}}{k^n}+\sum_{x=1}^{\lfloor{n/(k+1)}\rfloor}(-1)^x\frac{n\cdot (kx+x)^{n-kx-x-1}\cdot x^{kx+x-n}\cdot(n-kx-1)!}{k^{n-kx}\cdot(x-1)!\cdot(n-kx-x)!} $$
Mathematica:
closed[k_,n_]:=(k+1)^(n-1)/k^n+Sum[(-1)^y*n*(k*y+y)^(n-k*y-y-1)*y^(k*y+y-n)*(n-k*y-1)!/k^(n-k*y)/(y-1)!/(n-k*y-y)!,{y,1,Floor[n/(k+1)]}]
Does a cleaner closed form exist? Is there a general approach that works well on recursive formulas with multiple base cases?
Here is a generating function approach. To better see what's going on, we start with a small example.
Example: $k=3, n=2$:
A really small example. We consider a three-sided die and encode the probability to get one, two or three pips as \begin{align*} \frac{z^1+z^2+z^3}{3} \end{align*}
General case: $k,n$:
We calculate the general case and consider \begin{align*} \color{blue}{[z^n]}&\color{blue}{\sum_{j=1}^\infty\left(\frac{z+z^2+\cdots+z^k}{k}\right)^j}\tag{1}\\ &=[z^n]\sum_{j=1}^\infty\frac{1}{k^j}z^j\left(1+z+\cdots+z^{k-1}\right)^j\tag{2}\\ &=\sum_{j=1}^n\frac{1}{k^j}[z^{n-j}]\left(\frac{1-z^k}{1-z}\right)^j\tag{3}\\ &=\sum_{j=1}^n\frac{1}{k^j}[z^{n-j}]\sum_{r=0}^\infty\binom{-j}{r}(-z)^r\sum_{s=0}^j\binom{j}{s}\left(-z^k\right)^s\tag{4}\\ &=\sum_{j=1}^n\frac{1}{k^j}[z^{n-j}]\sum_{t=0}^\infty \sum_{{{r+ks=t}\atop{r\geq 0}}\atop{0\leq s\leq j}}\binom{j+r-1}{j-1}\binom{j}{s}(-1)^sz^t\tag{5}\\ &=\sum_{j=1}^n\frac{1}{k^j}[z^{n-j}]\sum_{t=0}^\infty \sum_{s=0}^{\min\left\{j,\left\lfloor\frac{t}{k}\right\rfloor\right\}}\binom{j+t-ks-1}{j-1}\binom{j}{s}(-1)^sz^t\tag{6}\\ &\,\,\color{blue}{=\sum_{j=1}^n\frac{1}{k^j} \sum_{s=0}^{\min\left\{j,\left\lfloor\frac{t}{k}\right\rfloor\right\}}\binom{n-ks-1}{j-1}\binom{j}{s}(-1)^s}\tag{7} \end{align*} which is similar to OPs formula, admittedly slightly more complex due to the double sum (see below).
Comment:
In (1) we use the Ansatz from the small example. Here we allow $j\geq 1$ throws without any harm, since the coefficient of operator $[z^n]$ guarantees, that terms with powers of $z$ greater than $n$ will be skipped.
In (2) we factor out $z^j$.
In (3) we apply the rule $[z^{p-q}]A(z)=[z^p]z^qA(z)$ and use the finite geometric sum formula. We also set the upper limit $n$ since other indices do not contribute.
In (4) we use the binomial series expansion and apply the binomial theorem.
In (5) we use the Cauchy product of two pwer series. We also use the binomial identity $\binom{-p}{q}=\binom{p+q-1}{p-1}(-1)^q$.
In (6) we eliminate $r$ by substituting $r=t-ks$.
In (7) we select the coefficient of $z^{n-j}$.
OPs formula:
We can transform OPs formula writing $j$ instead of $x$ for convenience only and obtain \begin{align*} p_{k,n}&= \frac{(k+1)^{n-1}}{k^n}\\ &\ +\sum_{j=1}^{\lfloor{n/(k+1)}\rfloor}(-1)^j\frac{n\cdot (kj+j)^{n-kj-j-1}\cdot j^{kj+j-n}\cdot(n-kj-1)!}{k^{n-kj}\cdot(j-1)!\cdot(n-kj-j)!}\\ &=\frac{(k+1)^{n-1}}{k^n}\\ &\ +\sum_{j=1}^{\lfloor{n/(k+1)}\rfloor}(-1)^j\frac{n(k+1)^{n-kj-j-1}j^{-1}}{k^{n-kj}}\binom{n-kj-1}{j-1}\tag{8}\\ \end{align*} In the last line we factored out $j$ and cancelled powers of $j$. We also use $\binom{p}{q}=\frac{p!}{q!(p-q)!}$.