Difference calculation

The difference calculus is a branch of mathematics that the discrete correspondence to the analysis ( differential and integral calculus forms). While analysis deals with functions that are defined on continuous spaces (in order to be able to establish a limit value concept), in particular with functions on real numbers , difference calculus is interested in functions on whole numbers ℤ. The difference calculation can be used to calculate series .

Differences and sums

The well-known continuous differential calculus is based on the differential operator , which is defined as follows: ${\displaystyle \mathrm {D} }$

${\displaystyle \mathrm {D} f(x)=\lim _{h\rightarrow 0}{\frac {f(x+h)-f(x)}{h}}}$

The difference calculation, on the other hand, uses a so-called difference operator : ${\displaystyle \Delta }$

${\displaystyle \Delta f(x)=f(x+1)-f(x)}$.

The opposite operation is not achieved with the indefinite integral as in the continuous differential calculus , but with an indefinite sum , which is related to the difference operator as follows: ${\displaystyle \sum f(x)}$

${\displaystyle g(x)=\Delta f(x)\quad \Longleftrightarrow \quad \sum g(x)\;\delta x=f(x)+C}$.

${\displaystyle \delta }$is related to here as to the continuous differential calculus. stands for the value of any function that is constant for integer ( ). ${\displaystyle \Delta }$ ${\displaystyle \mathrm {d} }$ ${\displaystyle \mathrm {D} }$ ${\displaystyle C}$ ${\displaystyle x}$ ${\displaystyle C(x+1)=C(x)}$

The counterpart to certain integrals are certain sums. These correspond to ordinary sums without the value at the highest index:

${\displaystyle \sideset {}{_{a}^{b}}\sum f(x)\;\delta x=\sum _{k=a}^{b-1}f(k)=[F(x)]_{a}^{b}=F(b)-F(a)}$.

properties

Invariant function

A function invariant under the differential operator is the exponential function of the base e . In the difference calculus, the exponential function of base 2 is invariant, as can easily be determined:

${\displaystyle {\begin{aligned}&\Delta f(x)=f(x)\\\Longleftrightarrow \quad &f(x+1)-f(x)=f(x)\\\Longleftrightarrow \quad &f(x+1)=2f(x)\\\Longleftrightarrow \quad &\exists C:f(x)=C\cdot 2^{x}\\\end{aligned}}}$

Falling faculties

There is a simple calculation rule for decreasing factorials , which are defined for every integer as follows: ${\displaystyle m}$

${\displaystyle x^{\underline {m}}={\frac {x!}{(x-m)!}}={\begin{cases}\overbrace {x(x-1)\ldots (x-m+1)} ^{m{\text{ Faktoren}}}&{\text{, wenn }}m\geq 0\\&\\\underbrace {\frac {1}{(x+1)(x+2)\ldots (x-m)}} _{|m|{\text{ Faktoren}}}&{\text{, wenn }}m<0\end{cases}}}$

This expression behaves in the difference calculation as follows:

• ${\displaystyle \Delta (x^{\underline {m}})=mx^{\underline {m-1}}}$
• ${\displaystyle \sideset {}{_{a}^{b}}\sum x^{\underline {m}}\;\delta x={\begin{cases}\left[{\frac {x^{\underline {m+1}}}{m+1}}\right]_{a}^{b}&{\text{, wenn }}m\neq -1\\\left[H_{x}\right]_{a}^{b}&{\text{, wenn }}m=-1\end{cases}}}$

where is the -th harmonic number . The harmonic series is thus the counterpart to the natural logarithm . The agreement goes so far that also applies. ${\displaystyle H_{n}}$ ${\displaystyle n}$ ${\displaystyle \Delta (x\cdot H_{x}-x)=H_{x}}$

Falling faculties and powers can always be converted into one another using Stirling numbers of the first or second kind:

${\displaystyle x^{\underline {m}}=\sum _{k}\left[{\begin{matrix}m\\k\end{matrix}}\right](-1)^{m-k}x^{k}}$,

${\displaystyle x^{m}=\sum _{k}\left\{{\begin{matrix}m\\k\end{matrix}}\right\}x^{\underline {k}}}$

In addition, the binomial theorem also applies to falling faculties.

Example for calculating the sum of the first square numbers: ${\displaystyle n}$

${\displaystyle \sum _{k=0}^{n}k^{2}=\sideset {}{_{0}^{n+1}}\sum x^{2}\delta x=\sideset {}{_{0}^{n+1}}\sum (x^{\underline {2}}\,+\,x^{\underline {1}})\delta x={\frac {(n+1)^{\underline {3}}}{3}}+{\frac {(n+1)^{\underline {2}}}{2}}={\frac {n(n+{\frac {1}{2}})(n+1)}{3}}}$.

Product rule and partial summation

The product rule of continuous differential calculus is valid in the following form:

${\displaystyle \Delta (u(x)v(x))=u(x)\Delta v(x)+v(x+1)\Delta u(x)}$.

This rule can be expressed more compactly by introducing a shift operator , defined as : ${\displaystyle \mathrm {E} }$ ${\displaystyle \mathrm {E} f(x)=f(x+1)}$

${\displaystyle \Delta (uv)=u\Delta v+\mathrm {E} v\Delta u}$.

The rearrangement of the terms leads to the formula of partial summation similar to partial integration :

${\displaystyle \sum u\,\Delta v=uv-\sum \mathrm {E} v\,\Delta u}$.

Example for calculating the sum : ${\displaystyle \sum _{k=0}^{n}k2^{k}}$

Here is and , so , and . ${\displaystyle u(x)=x}$ ${\displaystyle \Delta v(x)=2^{x}}$ ${\displaystyle \Delta u(x)=1}$ ${\displaystyle v(x)=2^{x}}$ ${\displaystyle \mathrm {E} v(x)=2^{x+1}}$

The formula for partial summation gives: . ${\displaystyle \sum x2^{x}\;\delta x=x2^{x}-\sum 2^{x+1}\;\delta x=x2^{x}-2^{x+1}+C}$

This ultimately leads to the solution:

${\displaystyle {\begin{aligned}\sum _{k=0}^{n}k2^{k}&=\sideset {}{_{0}^{n+1}}\sum x2^{x}\;\delta x\\&=\left[x2^{x}-2^{x+1}\right]_{0}^{n+1}\\&=(n-1)2^{n+1}+2\end{aligned}}}$

See also

• Difference equation

literature

• AO Gelfond : difference calculation. German Publishing house d. Wiss., Berlin, 1958
• Ronald Graham et al: Concrete Mathematics . Addison-Wesley, Upper Saddle River 2008, ISBN 0-201-55802-5
• NE Nörlund : Lectures on calculus of differences. Springer-Verlag, Berlin, 1924; Reprint Chelsea, New York, 1954

Web links

• Brian Hamrick: Discrete Calculus (PDF, 70 kB)