CSCE 411 Lecture 39

Lecture Slides

« previous | Friday, November 30, 2012 | next »

Calculus of Finite Differences (cont'd)

Calculus for Computer Scientists!

Difference Operator

Equivalent to differential operator ${\tfrac {\mathrm {d} }{\mathrm {d} x}}$:

${\begin{aligned}\Delta f(x)&=f(x+1)-f(x)\\\Delta n^{\underline {m}}&=mn^{\underline {m-1}}\\\Delta c^{n}&=(c-1)c^{n}\end{aligned}}$

where the falling power $n^{\underline {m}}$ is defined as $n^{\underline {m}}=n(n-1)(n-2)\dots (n-m+2)(n-m+1)$.

Antidifference Operator

Analogous to indefinite integrals

${\begin{aligned}\Delta f(n)&=g(n)g(n)=n^{\underline {m}}&\implies f(n)={\frac {1}{m+1}}n^{\underline {m+1}}g(n)=c^{n}&\implies f(n)={\frac {1}{c+1}}c^{n}\end{aligned}}$

Operator given as an indefinite sum:

$\sum f(n)\,\delta n$

What about $n^{\underline {-1}}$?

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

Thus the harmonic number plays the role of a discrete logarithm.

Fundamental Theorem of FDC

Let $f(n)$ be an antidifference of $g(n)$. Then

$\sum _{n=a}^{b}g(n)=f(b+1)-f(a)$

Example

$\sum _{n=5}^{64}c^{n}=\left.{\frac {1}{c-1}}c^{n}\right|_{5}^{65}={\frac {c^{65}-c^{5}}{c-1}}$

Linearity

${\begin{aligned}\Delta (af(n)+bg(n))&=a(\Delta f(n))+b(\Delta g(n))\\\sum (af(n)+bg(n)\,\delta n&=a\left(\sum f(n)\,\delta n\right)+b\left(\sum g(n)\,\delta n\right)\end{aligned}}$

Example

Find a closed form for the sum $\sum _{k=1}^{n}k^{2}$.

${\begin{aligned}\sum k^{2}\,\delta k&=\sum \left(k^{\underline {2}}+k^{\underline {1}}\right)\,\delta k\\&={\frac {1}{3}}k^{\underline {3}}+{\frac {1}{2}}k^{\underline {2}}\\\sum _{k=1}^{n}&=\left.{\frac {1}{3}}k^{\underline {3}}+{\frac {1}{2}}k^{\underline {2}}\right|_{1}^{n+1}\end{aligned}}$

Binomial Coefficients

${\begin{aligned}\Delta {\binom {n}{k+1}}&={\binom {n}{k}}\\\sum {\binom {n}{k}}\,\delta n={\binom {n}{k+1}}\end{aligned}}$

Example

$\sum _{n=0}^{m}{\binom {n}{k}}={\binom {m+1}{k+1}}-{\binom {0}{k+1}}={\binom {m+1}{k+1}}$

Partial Summation

$\sum f(n)(\Delta g(n))\delta n=f(n)g(n)-\sum (\Delta f(n))Eg(n)$

The Product Rule

${\begin{aligned}\Delta (f(n)\,g(n))&=f(n+1)\,g(n+1)-f(n)\,g(n)\\&=f(n+1)\,g(n+1)-f(n)\,g(n+1)+f(n)\,g(n+1)-f(n)\,g(n)\\&=(\Delta f(n))\,g(n+1)+f(n)\,(\Delta g(n))\\&=(\Delta f(n))\,Eg(n)+f(n)\,(\Delta g(n))\end{aligned}}$

Example

${\begin{aligned}\sum _{k=0}^{n}k2^{k}&=\left.k2^{k}\right|_{0}^{n+1}-\sum _{k=0}^{n}1\cdot 2^{k+1}\\&=\left.k2^{k}+2^{k+1}\right|_{0}^{n+1}\end{aligned}}$

References

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