Leibniz' Rule for Finite Differences I am attempting to prove a higher-order product rule in discrete calculus:
I'd like to show $$\Delta^n [f(x)g(x)] = \sum_{k=0}^n \binom{n}{k} (\Delta^kf(x))(\Delta^{n-k}T^kg(x))$$ where $\Delta f(x):= f(x+h) - f(x), Tf(x) := f(x+h)$ are the forward difference operator and forward shift, respectively. I have here defined $\Delta^k$ as the $k^{th}$ iterate of $\Delta$, with $\Delta^0$ acting as the identity. $T^k$ is defined similarly.
I have the ordinary product rule $\Delta[f(x)g(x)] = f(x)\Delta g(x) + g(x)\Delta f(x) + \Delta f(x)\Delta g(x).$ Is there a nice way to get this formula?
Assume all operators are acting on sufficiently well-behaved classes of functions (in case you need to use other tools like Taylor expansions or the identification $T = e^{hD}$).
 A: 
We obtain for $n\geq 0$:
\begin{align*}
\color{blue}{\Delta^n\left(fg\right)}
&=(T-I)^n\left(fg\right)\tag{1}\\
&=\sum_{k=0}^n\binom{n}{k}(-1)^kI^kT^{n-k}\left(fg\right)\\
&=\sum_{k=0}^n\binom{n}{k}(-1)^k\left(T^{n-k}f\right)\left(T^{n-k}g\right)\tag{2}\\
&=\sum_{k=0}^n\binom{n}{k}(-1)^k\left(\left(\Delta+I\right)^{n-k}f\right)\left(T^{n-k}g\right)\\
&=\sum_{k=0}^n\binom{n}{k}(-1)^k\sum_{j=0}^{n-k}\binom{n-k}{j}\left(\Delta^jf\right)\left(T^{n-k}g\right)\\
&=\sum_{j=0}^n\left(\Delta^jf\right)\sum_{k=0}^{n-j}\binom{n}{k}\binom{n-k}{j}(-1)^k\left(T^{n-k}g\right)\tag{3}\\
&=\sum_{j=0}^n\left(\Delta^jf\right)\sum_{k=0}^{n-j}\binom{n}{j}\binom{n-j}{k}(-1)^k\left(T^{n-k}g\right)\tag{4}\\
&=\sum_{j=0}^n\binom{n}{j}\left(\Delta^jf\right)\sum_{k=0}^{n-j}\binom{n-j}{k}(-1)^kT^{n-j-k}\left(T^jg\right)\\
&=\sum_{j=0}^n\binom{n}{j}\left(\Delta^jf\right)\left(T-I\right)^{n-j}\left(T^jg\right)\\
&\,\,\color{blue}{=\sum_{j=0}^n\binom{n}{j}\left(\Delta^jf\right)\left(\Delta^{n-j}T^jg\right)}\\
\end{align*}
and the claim follows.

Comment:

*

*In (1) we use the relationship between delta, shift and identity operator
\begin{align*}
\Delta f(x)=f(x+h)-f(x)=(Tf(x))-(If(x))=(T-I)f(x)
\end{align*}


*In (2) we use $If(x)=f(x)$ and
\begin{align*}
Tfg(x)=fg(x+h)=f(x+h)g(x+h)=(Tf(x))(Tg(x))
\end{align*}


*In (3) we exchange the sums noting equality of the index regions
\begin{align*}
\{(k,j)|0\leq k\leq n, 0\leq j\leq n-k\}=\{(k,j)|0\leq j\leq n, 0\leq k\leq n-j\}
\end{align*}


*In (4) we use the binomial identity $\binom{n}{k}\binom{n-k}{j}=\binom{n}{j}\binom{n-j}{k}$
Note: Here we closely follow section 30, Product of two functions: Differences in Calculus of Finite Differences by C. Jordan.
A: For future reference I did manage to see how to construct a simpler induction argument: the key is to use a slightly different product formula: $\Delta(fg) = f\Delta g + (Tg)\Delta f.$ This, combined with the Pascal identity, quickly yields the required induction.
