Calculus of Finite Differences

This is the calculus of computer scientists.
This is the calculus of discrete mathematics I tried to discover when I was bored one day.
This is the calculus of making everything make sense.
This is the calculus of finite differences!

Motivation

Find closed form of the sum

$\sum _{k+1}^{n}k^{2}$

…without looking it up or guessing (then proving) the solution.

Falling Powers

The $m$-th falling power of $n$ is defined as

$n^{\underline {m}}=n(n-1)\dots (n-m+1)$

Conversion from Non-Falling Powers

$n^{m}=\sum _{k=0}^{m}S(m,k)n^{\underline {k}}$

Where $S(m,k)={\frac {1}{k!}}\sum _{j=0}^{k}(-1)^{k-j}{\binom {k}{j}}j^{m}$ is a Stirling number of the second kind.

Examples:

1. $n^{2}=S(2,2)n^{\underline {2}}+S(2,1)n^{\underline {1}}+S(2,0)n^{\underline {0}}=n(n-1)+n$
2. $n^{3}=S(3,3)n^{\underline {3}}+S(3,2)n^{\underline {2}}+S(3,1)n^{\underline {1}}+S(3,0)n^{\underline {0}}=n(n-1)(n-2)+3n(n-1)+n$
3. $n^{4}=S(4,4)n^{\underline {4}}+S(4,3)n^{\underline {3}}+S(4,2)n^{\underline {2}}+S(4,1)n^{\underline {1}}+S(4,0)n^{\underline {0}}=n(n-1)(n-2)(n-3)+6n(n-1)(n-2)+7n(n-1)+n$

Difference Operator

Analogous to derivative of continuous calculus.

$\Delta g(n)=g(n+1)-g(n)\,\!$

Let $E$ denote the shift operator $Eg(n)=g(n+1)$, and $I$ the identity operator, then

$\Delta =E-I\,\!$

Like in calculus, the difference operator is linear:

$\Delta \left(\alpha \,f(n)+\beta \,g(n)\right)=\alpha \Delta f(n)+\beta \Delta g(n)$

Examples:

1. $f(n)=n$: $\Delta f(n)=n+1-n=1$
2. $f(n)=n^{2}$: $\Delta f(n)=(n+1)^{2}-n^{2}=2n+1$
3. $f(n)=n^{3}$: $\Delta f(n)=(n+1)^{3}-n^{3}=3n^{2}+3n+1$

Difference of Falling Powers

$\Delta n^{\underline {m}}=mn^{\underline {m-1}}$

Proof. If $m\geq 0$, then by definition

${\begin{aligned}\Delta n^{\underline {m}}&=(n+1){\color {Blue}n\dots (n-m+2)}-{\color {Blue}n\dots (n-m+2)}(n-m+1)\\&=(m)(n\dots (n-m+2))\end{aligned}}$

If $m<0$, then let $\mu =-m$

First, since ${\tfrac {n^{\underline {m}}}{n^{\underline {m-1}}}}=(n-m+1)$, we expect $n^{\underline {-\mu }}={\tfrac {1}{(n+1)(n+2)\dots (n+\mu )}}$. Thus by definition,

${\begin{aligned}\Delta n^{\underline {-\mu }}&={\frac {1}{(n+2)(n+3)\dots (n+\mu )(n+\mu +1)}}-{\frac {1}{(n+1)(n+2)\dots (n+\mu )}}\\&={\frac {(n+1)-(n+\mu +1)}{(n+1)(n+2)\dots (n+\mu )(n+\mu +1)}}\\&={\frac {-\mu }{(n+1)\dots (n+\mu +1)}}\\&=-\mu n^{\underline {-\mu -1}}\\&=mn^{\underline {m-1}}\end{aligned}}$

Difference of Exponentials

$\Delta c^{n}=(c-1)c^{n}\,\!$

In particular, $\Delta 2^{n}=2^{n}$

Proof.

${\begin{aligned}\Delta c^{n}&=c^{n+1}-c^{n}\\&=c\cdot c^{n}-c^{n}\\&=(c-1)c^{n}\end{aligned}}$

Q.E.D.

Antidifference Operator

Analogous to antiderivative or indefinite integral of continuous calculus.

$\Delta f(n)=g(n)\quad \iff \quad \sum g(n)\,\delta n=f(n)$

The antidifference operator is also linear:

$\sum \left(\alpha f(n)+\beta g(n)\right)\,\delta n=\alpha \sum f(n)\,\delta n+\beta \sum g(n)\,\delta n$

Antidifference of Falling Powers

$\sum n^{\underline {m}}\,\delta n={\frac {1}{m+1}}n^{\underline {m+1}}$

Except in the case of $m=-1$:

$\sum n^{\underline {-1}}\,\delta n=1+{\frac {1}{2}}+\dots +{\frac {1}{n}}=H_{n}$

Where $H_{n}$ is the $n$^th harmonic number! Thus by inverse, $\Delta H_{n}=n^{\underline {-1}}$.

Antidifference of Exponentials

$\sum c^{n}\,\delta n={\frac {1}{c+1}}c^{n}$

Sums

Analogous to definite integrals of continuous calculus.

$\sum _{k=a}^{b}g(k)$ corresponds with $\int _{a}^{b}g(x)\,\mathrm {d} x$

And so,

THE FUNDAMENTAL THEOREM OF CALCULUS
${\frac {\mathrm {d} }{\mathrm {d} x}}f(x)=g(x)\quad \implies \quad \int _{a}^{b}g(x)\,\mathrm {d} x=f(b)-f(a)$

is perfectly paralleled by

THE FUNDAMENTAL THEOREM OF FINITE DIFFERENCES
$\Delta f(n)=g(n)\quad \implies \quad \sum _{n=a}^{b}g(n)=f(b+1)-f(a)$

References

• D. Gleich: Finite Calculus: A tutorial for solving Nasty Sums. . External Link
• Graham, Knuth, Patashnik: Concrete Mathematics, Addison Wesley
• Ch. Jordan: Calculus of finite differences, AMS Chelsea, 1965