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 Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \tfrac{\mathrm{d}}{\mathrm{d}x}} :

Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \begin{align} \Delta f(x) &= f(x+1) - f(x) \\ \Delta n^{\underline{m}} &= mn^{\underline{m-1}} \\ \Delta c^n &= (c-1)c^n \end{align}}

where the falling power Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle n^{\underline{m}}} is defined as Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle n^{\underline{m}} = n(n-1)(n-2)\dots(n-m+2)(n-m+1)} .

Antidifference Operator

Analogous to indefinite integrals

Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \begin{align} \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{align}}

Operator given as an indefinite sum:

Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \sum f(n) \, \delta n}

What about Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle n^{\underline{-1}}} ?

Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \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 Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle f(n)} be an antidifference of Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle g(n)} . Then

Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \sum_{n=a}^b g(n) = f(b+1) - f(a)}

Example

Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \sum_{n=5}^{64} c^n = \left. \frac{1}{c-1}c^n \right|_5^{65} = \frac{c^{65} - c^5}{c-1}}

Linearity

Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \begin{align} \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{align}}

Example

Find a closed form for the sum Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \sum_{k=1}^n k^2} .

Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \begin{align} \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{align}}

Binomial Coefficients

Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \begin{align} \Delta \binom{n}{k+1} &= \binom{n}{k} \\ \sum \binom{n}{k} \, \delta n = \binom{n}{k+1} \end{align}}

Example

Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \sum_{n=0}^m \binom{n}{k} = \binom{m+1}{k+1} - \binom{0}{k+1} = \binom{m+1}{k+1}}

Partial Summation

Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \sum f(n) (\Delta g(n)) \delta n = f(n) g(n) - \sum (\Delta f(n)) Eg(n)}

The Product Rule

Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \begin{align} \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{align}}

Example

Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \begin{align} \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{align}}

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