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^{\underset{\_}{m}}=n(n-1)\dots (n-m+1)$

Conversion from Non-Falling Powers

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

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

Examples:

1. $n^2=S(2,2)n^{\underset{\_}{2}}+S(2,1)n^{\underset{\_}{1}}+S(2,0)n^{\underset{\_}{0}}=n(n-1)+n$
2. $n^3=S(3,3)n^{\underset{\_}{3}}+S(3,2)n^{\underset{\_}{2}}+S(3,1)n^{\underset{\_}{1}}+S(3,0)n^{\underset{\_}{0}}=n(n-1)(n-2)+3n(n-1)+n$
3. $n^4=S(4,4)n^{\underset{\_}{4}}+S(4,3)n^{\underset{\_}{3}}+S(4,2)n^{\underset{\_}{2}}+S(4,1)n^{\underset{\_}{1}}+S(4,0)n^{\underset{\_}{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.

$\mathrm{\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

$\mathrm{\Delta }=E-I$

Like in calculus, the difference operator is linear:

$\mathrm{\Delta }(\alpha f(n)+\beta g(n))=\alpha \mathrm{\Delta }f(n)+\beta \mathrm{\Delta }g(n)$

Examples:

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

Difference of Falling Powers

$\mathrm{\Delta }{n}^{\underset{\_}{m}}=m{n}^{\underset{\_}{m-1}}$

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

$\begin{array}{rl}\mathrm{\Delta }{n}^{\underset{\_}{m}}& =(n+1)n\dots (n-m+2)-n\dots (n-m+2)(n-m+1)\\ & =(m)(n\dots (n-m+2))\end{array}$

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

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

$\begin{array}{rl}\mathrm{\Delta }{n}^{\underset{\_}{-\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^{\underset{\_}{-\mu -1}}\\ & =m{n}^{\underset{\_}{m-1}}\end{array}$

Difference of Exponentials

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

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

Proof.

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

Q.E.D.

Antidifference Operator

Analogous to antiderivative or indefinite integral of continuous calculus.

$\mathrm{\Delta }f(n)=g(n)⟺\sum g(n)\delta n=f(n)$

The antidifference operator is also linear:

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

Antidifference of Falling Powers

$\sum n^{\underset{\_}{m}}\delta n=\frac{1}{m+1}{n}^{\underset{\_}{m+1}}$

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

$\sum n^{\underset{\_}{-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, $\mathrm{\Delta }{H}_n=n^{\underset{\_}{-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 $\underset{a}{\overset{b}{\int }}g(x)\mathrm{d}x$

And so,

THE FUNDAMENTAL THEOREM OF CALCULUS
$\frac{\mathrm{d}}{\mathrm{d}x}f(x)=g(x)⟹\underset{a}{\overset{b}{\int }}g(x)\mathrm{d}x=f(b)-f(a)$

is perfectly paralleled by

THE FUNDAMENTAL THEOREM OF FINITE DIFFERENCES
$\mathrm{\Delta }f(n)=g(n)⟹\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