Hitting a target with a die: finding a better closed form of the recursive formula 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?
 A: Here's one option: represent the recursive formula as a $k\times k$ matrix:
$$
M_{k,n}=
\begin{bmatrix}
\frac{1}{k} & \frac{1}{k} & \cdots & \frac{1}{k} & \frac{1}{k} \\
1 & 0 & \cdots & 0 & 0 \\
0 & 1 & \cdots & 0 & 0 \\
\vdots & \vdots & \ddots & \vdots & \vdots \\
0 & 0 & \cdots & 1 & 0
\end{bmatrix}^n
$$
The probability is the first element of the matrix.
$$
p_{k,n}=(M_{k,n})_{0,0}
$$
A: 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*}

Denoting with $[z^j]$ the coefficient of $z^j$ in a series we obtain
\begin{align*}
[z^2]&\left(\frac{z+\color{blue}{z^2}+z^3}{3}+\frac{(\color{blue}{z}+z^2+z^3)^2}{9}\right)=\frac{1}{3}+\frac{1}{9}\color{blue}{=\frac{4}{9}}
\end{align*}
We obtain $n=2$ by either throwing two pips $(2)$ the first time with probability $\frac{1}{3}$ or by throwing one pip twice $(1,1)$ with probability $\frac{1}{9}$ resulting in a total of $\color{blue}{\frac{4}{9}}$. There are no other ways to obtain $n=2$ with a three-sided die.

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)!}$.
A: (WARNING : not an answer to the question, but too long for a comment):
Fixed $n$ formula are tough, but their asymptotic in this case remains simple:
As $n$ gets large, for $k$ fixed, $p_{k,n}$ converges toward the inverse of the expected value of the dice, so $2/(k+1)$ for a $k$-dice.
Check Blackwell renewal theorem, arithmetic case for this kind of limit statement : https://encyclopediaofmath.org/wiki/Blackwell_renewal_theorem
