Prove recursion for sum

Question

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)?

Answer 1

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$.