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 $\frac{\mathrm{d}}{\mathrm{d}x}$:

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

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

Antidifference Operator

Analogous to indefinite integrals

$\begin{array}{rlrl}\mathrm{\Delta }f(n)& =g(n)g(n)=n^{\underset{\_}{m}}& ⟹f(n)=\frac{1}{m+1}{n}^{\underset{\_}{m+1}}g(n)=c^n& ⟹f(n)=\frac{1}{c+1}{c}^n\end{array}$

Operator given as an indefinite sum:

$\sum f(n)\delta n$

What about $n^{\underset{\_}{-1}}$?

$\sum n^{\underset{\_}{-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={\frac{1}{c-1}{c}^n|}_5^{65}=\frac{c^{65}-c^5}{c-1}$

Linearity

$\begin{array}{rl}\mathrm{\Delta }(af(n)+bg(n))& =a(\mathrm{\Delta }f(n))+b(\mathrm{\Delta }g(n))\\ \sum (af(n)+bg(n)\delta n& =a(\sum f(n)\delta n)+b(\sum g(n)\delta n)\end{array}$

Example

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

$\begin{array}{rl}\sum k^2\delta k& =\sum (k^{\underset{\_}{2}}+k^{\underset{\_}{1}})\delta k\\ & =\frac{1}{3}{k}^{\underset{\_}{3}}+\frac{1}{2}{k}^{\underset{\_}{2}}\\ \sum _{k=1}^n& ={\frac{1}{3}{k}^{\underset{\_}{3}}+\frac{1}{2}{k}^{\underset{\_}{2}}|}_1^{n+1}\end{array}$

Binomial Coefficients

$\begin{array}{rl}\mathrm{\Delta }(\genfrac{}{}{0ex}{}{n}{k+1})& =(\genfrac{}{}{0ex}{}{n}{k})\\ \sum (\genfrac{}{}{0ex}{}{n}{k})\delta n=(\genfrac{}{}{0ex}{}{n}{k+1})\end{array}$

Example

$\sum _{n=0}^m(\genfrac{}{}{0ex}{}{n}{k})=(\genfrac{}{}{0ex}{}{m+1}{k+1})-(\genfrac{}{}{0ex}{}{0}{k+1})=(\genfrac{}{}{0ex}{}{m+1}{k+1})$

Partial Summation

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

The Product Rule

$\begin{array}{rl}\mathrm{\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)\\ & =(\mathrm{\Delta }f(n))g(n+1)+f(n)(\mathrm{\Delta }g(n))\\ & =(\mathrm{\Delta }f(n))Eg(n)+f(n)(\mathrm{\Delta }g(n))\end{array}$

Example

$\begin{array}{rl}\sum _{k=0}^{n}k{2}^k& ={k{2}^k|}_0^{n+1}-\sum _{k=0}^{n}1\cdot 2^{k+1}\\ & ={k{2}^k+2^{k+1}|}_0^{n+1}\end{array}$

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