Leibniz' Rule for Finite Differences

Question

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

Answer 1

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.

Answer 2

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.