I'm having trouble seeing how this recursion formula holds.
Let $a_x(\lambda) = (x - \lambda)^r \frac{\lambda^x e^{-\lambda}}{x!}$
Firstly, we have
$$\log a_x(\lambda) = r \log(x - \lambda) + x \log \lambda - \lambda - \log x!,$$
which we differentiate to get,
$$\frac{1}{a_x(\lambda)} \frac{da_x}{d\lambda} = \frac{r}{\lambda - x} + \frac{x}{\lambda} - 1$$
so the derivative is $$\frac{da_x}{d\lambda} = a_x(\lambda) \left( \frac{r}{\lambda - x} + \frac{x}{\lambda} - 1 \right) $$
Thus, the equality being proposed in the question, fully written out, is:
$$\sum_{x=0}^{\infty} (x - \lambda)^{r+1} \frac{\lambda^x e^{-\lambda}}{x!} = \lambda \left[ r \sum_{x=0}^{\infty} (x - \lambda)^{r-1} \frac{\lambda^x e^{-\lambda}}{x!} + \sum_{x=0}^{\infty} (x - \lambda)^r \frac{\lambda^x e^{-\lambda}}{x!} \left( \frac{r}{\lambda - x} + \frac{x}{\lambda} - 1 \right) \right] $$
and I do not see how we can simplify the right hand side to get the left hand side. Have I made a mistake somewhere?
Your computations look correct so far. You just have to complete it. The RHS simplifies to
$$\sum_{x=0}^\infty \frac{\lambda^{x+1} e^{-\lambda}}{x!} \left(r (x-\lambda)^{r-1} + (x-\lambda)^r \left( \frac{r}{\lambda - x} + \frac{x}{\lambda} - 1 \right) \right) \\ = \sum_{x=0}^\infty \frac{\lambda^{x+1} e^{-\lambda}}{x!} (x-\lambda)^r \frac{x-\lambda}{\lambda} \\ = \sum_{x=0}^\infty (x-\lambda)^{r+1} \frac{\lambda^x e^{-\lambda}}{x!}.$$
In the first line, we factored out the terms $\lambda^{x+1}$, $e^{-\lambda}$, and $x!$. In the second step, we observe that the first term in parentheses cancels with the product $(x-\lambda)^r \cdot r/(\lambda - x)$. In the last step, we note the product $(x-\lambda)^r (x/\lambda - 1) = (x-\lambda)^{r+1}/\lambda$.