Calculus of Finite Differences

From Notes
Jump to navigation Jump to search

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

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}

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


Falling Powers

The 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 m} -th falling power 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 n} 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)\dots(n-m+1)}


Conversion from Non-Falling Powers

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^{m} = \sum_{k=0}^m S(m,k) n^{\underline{k}}}

Where 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 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. 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^2 = S(2,2) n^{\underline{2}} + S(2,1) n^{\underline{1}} + S(2,0) n^{\underline{0}} = n(n-1) + n}
  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 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. 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^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.

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 \Delta g(n) = g(n+1) - g(n) \,\!}

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 E} denote the shift 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 Eg(n) = g(n+1)} , and 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 I} the identity operator, 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 \Delta = E - I\,\!}

Like in calculus, the difference operator is linear:

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 \Delta \left( \alpha \, f(n) + \beta \, g(n) \right) = \alpha \Delta f(n) + \beta \Delta g(n)}

Examples:

  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 f(n) = n} : 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 \Delta f(n) = n+1 - n = 1}
  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 f(n) = n^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 \Delta f(n) = (n+1)^2 - n^2 = 2n+1}
  3. 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) = n^3} : 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 \Delta f(n) = (n+1)^3 - n^3 = 3n^2 + 3n + 1}

Difference of Falling Powers

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 \Delta n^{\underline{m}} = mn^{\underline{m-1}}}

Proof. If 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 m \ge 0} , then by definition

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 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{align}}


If 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 m < 0} , then 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 \mu = -m}

First, since 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{n^{\underline{m}}}{n^{\underline{m-1}}} = (n-m+1)} , we expect 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{-\mu}} = \tfrac{1}{(n+1)(n+2) \dots (n+\mu)}} . Thus by definition,

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 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{align}}

Difference of Exponentials

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 \Delta c^n = (c-1)c^n\,\!}

In particular, 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 \Delta 2^n = 2^n}

Proof.

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 c^n &= c^{n+1} - c^n \\ &= c \cdot c^n - c^n \\ &= (c - 1) c^n \end{align}}

Q.E.D.


Antidifference Operator

Analogous to antiderivative or indefinite integral of continuous calculus.

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 \Delta f(n) = g(n) \quad \iff \quad \sum g(n) \, \delta n = f(n)}

The antidifference operator is also linear:

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 \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

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{m}} \, \delta n = \frac{1}{m+1} n^{\underline{m+1}}}

Except in the case 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 m = -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 = 1 + \frac{1}{2} + \dots + \frac{1}{n} = H_n}

Where 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 H_n} is the 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} th harmonic number! Thus by inverse, 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 \Delta H_n = n^{\underline{-1}}} .

Antidifference of Exponentials

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 c^n \, \delta n = \frac{1}{c+1}c^n}


Sums

Analogous to definite integrals of continuous calculus.

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=a}^b g(k)} corresponds with 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 \int_a^b g(x) \,\mathrm{d}x}

And so,

THE FUNDAMENTAL THEOREM OF CALCULUS
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 \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
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 \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. Local PDF. External Link
  • Graham, Knuth, Patashnik: Concrete Mathematics, Addison Wesley
  • Ch. Jordan: Calculus of finite differences, AMS Chelsea, 1965
Retrieved from "https://notes.komputerwiz.net/w/index.php?title=Calculus_of_Finite_Differences&oldid=2154"