<s>[INST] Inductive proof for the Binomial Theorem for rising factorials I want to proove the following equality containing rising factorials
$$(x+y)^\overline{n}\overset{(*)}{=}\sum_{k=0}^n\binom{n}{k}x^\overline{k}y^\overline{n-k}.$$
For $n=1$ this equality is obviously correct. Now I tried to create the transition $n-1\rightarrow n$ this way
$$(x+y)^\overline{n}=(x+y)^\overline{n-1}+\underbrace{\binom{n}{n}x^\overline{n}y^\overline{n-n}}_{x^\overline{n}}$$
$$(x+y)^\overline{n}=\sum_{k=0}^{n-1}\binom{n-1}{k}x^\overline{k}y^\overline{n-k-1}+x^\overline{n}.$$
As I am not that familiar with binomials and such sums, can anyone explain me how transform this equality to achieve a representation like in $(*)$?
 [/INST] The notation is a little neater if we do the induction step from $n$ to $n+1$ instead of from $n-1$ to $n$. My induction hypothesis is that for all $x$ and $y$, $$(x+y)^{\overline n} = \sum\limits_{k=0}^n \binom{n}{k}x^{\overline k}y^{\overline{n-k}}.$$
I want to show that for all $x$ and $y$, $$(x+y)^{\overline {n+1}} = \sum\limits_{k=0}^{n+1}\binom{n+1}{k}x^{\overline k}y^{\overline{n+1-k}}.$$
I’ll be using the fact that $u^{\overline {m+1}} = u(u+1)^{\overline m}$. 
$$\begin{align*}
\sum\limits_{k=0}^{n+1}\binom{n+1}{k}x^{\overline k}y^{\overline{n+1-k}} &= \sum\limits_{k=0}^n\binom{n+1}{k}x^{\overline k}y^{\overline{n+1-k}}+x^{\overline{n+1}}\tag{1}\\
&= \sum\limits_{k=0}^n \left(\binom{n}{k-1}+\binom{n}{k}\right)x^{\overline k}y^{\overline{n+1-k}}+x^{\overline{n+1}}\tag{2}\\
&= \sum\limits_{k=0}^n \binom{n}{k-1}x^{\overline k}y^{\overline{n+1-k}} + \sum\limits_{k=0}^n \binom{n}{k}x^{\overline k}y^{\overline{n+1-k}} + x^{\overline{n+1}}\\
&= \sum\limits_{k=0}^{n-1} \binom{n}{k}x^{\overline {k+1}}y^{\overline{n-k}} + \sum\limits_{k=0}^n \binom{n}{k}x^{\overline k}y^{\overline{n+1-k}} + x^{\overline{n+1}}\tag{3}\\
&= \sum\limits_{k=0}^n \binom{n}{k}x^{\overline {k+1}}y^{\overline{n-k}} + \sum\limits_{k=0}^n \binom{n}{k}x^{\overline k}y^{\overline{n+1-k}}\tag{4}\\
&= x \sum\limits_{k=0}^n \binom{n}{k} (x+1)^{\overline k}y^{\overline{n-k}} + y \sum\limits_{k=0}^n \binom{n}{k} x^{\overline k} (y+1)^{\overline {n-k}}\tag{5}\\
&= x(x+1+y)^{\overline n} + y(x+y+1)^{\overline n}\tag{6}\\
&= (x+y)(x+y+1)^{\overline n}\\
&= (x+y)^{\overline{n+1}}
\end{align*}$$
At step $(1)$ I split off the last term of the sum. At step $(2)$ I used the basic binomial recursion. At step $(3)$ I did an index shift on the first sum: the $k=0$ term is $0$, so $k$ might as well run from $1$ to $n$ and can then be replaced by $k-1$, which runs from $0$ to $n-1$. At step $(4)$ I combined the separated term from step $(1)$ with the first summation. At step $(5)$ I used the fact mentioned just before the computation, and at step $(6)$ I applied the induction hypothesis. The rest is just algebra and again the fact mentioned before the computation.
</s>