Let $l\ge 0$, $p\ge 0$ and $q\ge 1$ be integers. Then the following formula holds: \begin{equation} \sum\limits_{j=l}^p q^{(j)} \left\{ \begin{array}{r} p \\ j\end{array}\right\} \binom{j}{l} (-1)^j = (-1)^p \binom{q+l-1}{l} \sum\limits_{j=0}^l \binom{l}{j} (-1)^j \cdot (q+l-j)^p \end{equation} where $\left\{ \begin{array}{r} p \\ j\end{array}\right\}$ are Stirling numbers of the second kind.
Indeed if $l=0$ the identity follows from the definition of Stirling numbers.Now, we took $l=1$ and discovered the right hand side by fixing $p$ and interpolating a polynomial as a function of $q$ to the left hand side. Having achieved a match between the interpolating polynomial and the left hand side we moved on to the case $l=2$ and then to $l=3$ until finally we discovered the pattern and verified the formula. Clearly the success of this kind of procedure depends on whether the result is a polynomial and therefore in more generic cases such a procedure will simply fail.
My question is therefore how do we prove that identity in a rigorous way.
Is there a probabilistic interpretation of this identity?
We seek to show that with $p\ge l\ge 0$ and $q\ge 1$ a parameter
$$\sum_{j=l}^p {q+j-1\choose j} j! {p\brace j} {j\choose l} (-1)^j = (-1)^p {q+l-1\choose l} \sum_{j=0}^l {l\choose j} (-1)^j (q+l-j)^p.$$
We have
$$j! {p\brace j} = j! \times p! [z^p] \frac{(\exp(z)-1)^j}{j!} = p! [z^p] (\exp(z)-1)^j.$$
Observe that this will produce zero for $j\gt p$ so it enforces the upper limit of the sum. We get for the LHS
$$p! [z^p] \sum_{j\ge l} {q+j-1\choose j} (\exp(z)-1)^j {j\choose l} (-1)^j.$$
Note that
$${q+j-1\choose j} {j\choose l} = \frac{(q+j-1)!}{(q-1)! \times l! \times (j-l)!} = {q+l-1\choose l} {q+j-1\choose q+l-1}$$
so that the LHS becomes
$$p! [z^p] {q+l-1\choose l} \sum_{j\ge l} {q+j-1\choose q+l-1} (\exp(z)-1)^j (-1)^j \\ = p! [z^p] {q+l-1\choose l} \sum_{j\ge l} {q+j-1\choose j-l} (\exp(z)-1)^j (-1)^j \\ = p! [z^p] {q+l-1\choose l} (\exp(z)-1)^l (-1)^l \sum_{j\ge 0} {q+j+l-1\choose j} (\exp(z)-1)^j (-1)^j \\ = p! [z^p] {q+l-1\choose l} (\exp(z)-1)^l (-1)^l \frac{1}{(1-(-1)(\exp(z)-1))^{q+l}} \\ = p! [z^p] {q+l-1\choose l} (\exp(z)-1)^l (-1)^l \exp(-(q+l)z).$$
Extracting coefficients from this we write
$$p! [z^p] {q+l-1\choose l} (-1)^l \exp(-(q+l)z) \sum_{j=0}^l {l\choose j} (-1)^{l-j} \exp(jz) \\ = p! [z^p] {q+l-1\choose l} (-1)^l \sum_{j=0}^l {l\choose j} (-1)^{l-j} \exp((j-l-q)z) \\ = {q+l-1\choose l} (-1)^l \sum_{j=0}^l {l\choose j} (-1)^{l-j} (j-l-q)^p \\ = (-1)^p {q+l-1\choose l} \sum_{j=0}^l {l\choose j} (-1)^{j} (q+l-j)^p.$$
This is the RHS as claimed.