Prove recursion for sum One should show, that
$$S(n,x,y):= (y-n)\sum_{k=0}^n \binom{n}{k} (x+k)^{k+1} (y-k)^{n-k-1}$$
satisties the recursion
$$S(n,x,y)=x(x+y)^n +n S(n-1,x+1,y-1),\quad \text{for} ~n\geq1,\quad S(0,x,y)=x.$$
I know that we should use Abels' generalization of the binomial theorem, that is
$$\begin{equation} (x + y)^n = \sum_{k=0}^n \binom{n}{k} x (x-kz)^{k-1} (y + kz)^{n-k}\end{equation}$$
for any $x, y, z \in\mathbb{R}$.
STARTING SOLUTION:
If I start with the right side, I get
$$\begin{align*}x (x+y)^n &+ n S(n-1,x+1,y-1) \\
         &= x (x+y)^n + n (y-n+1) \sum_{k=0}^{n-1} \binom{n-1}{k} (x+1+k)^{k+1} (y-1-k)^{n-k-2}\\
         &= x\sum_{k=0}^n \binom{n}{k} x (x-kz)^{k-1} (y + kz)^{n-k} \\
         &\hspace{2.1cm}+ n (y-n+1) \sum_{k=0}^{n-1} \binom{n-1}{k} (x+1+k)^{k+1} (y-1-k)^{n-k-2}\\
         &=\cdots\\
         &= (y-n) \sum_{k=0}^n \binom{n}{k} (x+k)^{k+1} (y-k)^{n-k-1} = S(n,x,y),\end{align*}$$
I do not really know how to continue from here, those anyone have a clue what could be inserted for z (and how one could shift the indices of the second sum to get the right term)?
 A: We start with the right-hand side and keep at first the focus on $nS(n-1,x+1,y+1)$.

We obtain
\begin{align*}
&\color{blue}{nS(n-1,x+1,y-1)}\\
&\qquad =n(y-n)\sum_{k=0}^{n-1}\binom{n-1}{k}(x+1+k)^{k+1}(y-1-k)^{n-k-2}\tag{1}\\
&\qquad= n(y-n)\sum_{k=1}^{n}\binom{n-1}{k-1}(x+k)^k(y-k)^{n-k-1}\tag{2}\\
&\qquad=(y-n)\sum_{k=0}^n\binom{n}{k}k(x+k)^k(y-k)^{n-k-1}\tag{3}\\
&\qquad\,\,\color{blue}{=S(n,x,y)-(y-n)\sum_{k=0}\binom{n}{k}x(x+k)^k(y-k)^{n-k-1}}\tag{4}
\end{align*}

Comment:

*

*In (1) we use the definition of $S(n,x,y)$.


*In (2) we shift the index $k$ by one.


*In (3) we use the binomial identity $\binom{n}{k}=\binom{n-1}{k-1}\frac{n}{k}$. We also start with index $k=0$ which doesn't change anything.


*In (4) we use $k=(x+k)-x$ and obtain a representation with $S(n,x,y)$.

Looking at (4) we observe the following is left to show:
\begin{align*}
(x+y)^n=\color{blue}{(y-n)}\sum_{k=0}\binom{n}{k}(x+k)^k(y-k)^{n-k-1}\tag{5}
\end{align*}
We use Abel's generalisation with $z=-1$ which gives
\begin{align*}
(x + y)^n = \color{blue}{x}\sum_{k=0}^n \binom{n}{k} (x+k)^{k-1} (y - k)^{n-k}\tag{6}
\end{align*}
and we see (6) is close to the wanted representation (5) indicating we could give the substitution $\color{blue}{x\to y-n}$ a try.

This substitution finally does the job.

We obtain
\begin{align*}
\color{blue}{(x+y)^n}&=((y-n)+(x+n))^n\tag{7}\\
&=\sum_{k=0}^n\binom{n}{k}(y-n)((y-n)+k)^{k-1}((x+n)-k)^{n-k}\tag{8}\\
&=\sum_{k=0}^n\binom{n}{k}(y-n)(y-(n-k))^{k-1}(x+(n-k))^{n-k}\\
&\,\,\color{blue}{=(y-n)\sum_{k=0}^n\binom{n}{k}(y-k)^{n-k-1}(x+k)^{k}}\tag{9}\\
\end{align*}
which is besides a factor $x$ the sum in (4) and the claim follows.

Comment:

*

*In (7) we use the substitution $x\to y-n$ and $y\to x+n$.


*In (8) we use Abel's generalised binomial theorem from (6).


*In (9) we change the order of summation $k\to n-k$.
