Differenzenrechnung

Die Differenzenrechnung ist ein Teilgebiet der Mathematik, das die diskrete Entsprechung zur Analysis (Differenzial- und Integralrechnung) bildet. Während sich die Analysis mit Funktionen beschäftigt, die auf kontinuierlichen Räumen definiert sind (um einen Grenzwertbegriff etablieren zu können), im Besonderen mit Funktionen auf den reellen Zahlen, interessiert man sich in der Differenzenrechnung für Funktionen auf den ganzen Zahlen ℤ. Die Differenzenrechnung kann zur Berechnung von Reihen angewandt werden.

Differenzen und Summen

Die bekannte kontinuierliche Differentialrechnung basiert auf dem Differenzialoperator $\mathrm {D}$ , der wie folgt definiert ist:

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

Die Differenzenrechnung hingegen verwendet einen sogenannten Differenzenoperator $\Delta$ :

\Delta f(x)=f(x+1)-f(x)

.

Die umgekehrte Operation wird nicht wie in der kontinuierlichen Differentialrechnung mit dem unbestimmten Integral, sondern mit einer unbestimmten Summe $\sum f(x)$ erreicht, die sich zum Differenzenoperator wie folgt verhält:

g(x)=\Delta f(x)\quad \Longleftrightarrow \quad \sum g(x)\;\delta x=f(x)+C

.

$\delta$ verhält sich hier zu $\Delta$ wie $\mathrm {d}$ zu $\mathrm {D}$ in der kontinuierlichen Differentialrechnung. $C$ steht für den Wert einer beliebigen Funktion, die für ganzzahlige $x$ konstant ist ( $C(x+1)=C(x)$ ).

Das Pendant zu bestimmten Integralen sind bestimmte Summen. Diese entsprechen gewöhnlichen Summen ohne den Wert am höchsten Index:

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

.

Eigenschaften

Invariante Funktion

Eine unter dem Differenzialoperator invariante Funktion ist die Exponentialfunktion der Basis e. In der Differenzenrechnung ist die Exponentialfunktion der Basis 2 invariant, wie sich leicht ermitteln lässt:

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

Fallende Fakultäten

Eine einfache Rechenregel gibt es für fallende Fakultäten, die für jede Ganzzahl $m$ wie folgt definiert sind:

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

Dieser Ausdruck verhält sich in der Differenzenrechnung folgendermaßen:

$\Delta (x^{\underline {m}})=mx^{\underline {m-1}}$
$\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}}$

wobei $H_{n}$ die $n$ -te harmonische Zahl ist. Die harmonische Reihe ist somit das Gegenstück zum natürlichen Logarithmus. Die Übereinstimmung geht so weit, dass $\Delta (x\cdot H_{x}-x)=H_{x}$ ebenfalls gilt.

Fallende Fakultäten und Potenzen können stets mittels Stirling-Zahlen erster bzw. zweiter Art ineinander umgewandelt werden:

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

,

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

Außerdem gilt der binomische Lehrsatz auch für fallende Fakultäten.

Beispiel zur Berechnung der Summe der ersten $n$ Quadratzahlen:

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

.

Produktregel und partielle Summation

Die Produktregel der kontinuierlichen Differentialrechnung ist in folgender Form gültig:

\Delta (u(x)v(x))=u(x)\Delta v(x)+v(x+1)\Delta u(x)

.

Diese Regel lässt sich durch Einführung eines Verschiebeoperators $\mathrm {E}$ , definiert als $\mathrm {E} f(x)=f(x+1)$ , kompakter ausdrücken:

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

.

Die Umstellung der Terme führt zur Formel der partiellen Summation ähnlich der partiellen Integration:

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

.

Beispiel zur Berechnung der Summe $\sum _{k=0}^{n}k2^{k}$ :

Hier ist $u(x)=x$ und $\Delta v(x)=2^{x}$ , sodass $\Delta u(x)=1$ , $v(x)=2^{x}$ und $\mathrm {E} v(x)=2^{x+1}$ .

Die Formel zur partiellen Summation ergibt: $\sum x2^{x}\;\delta x=x2^{x}-\sum 2^{x+1}\;\delta x=x2^{x}-2^{x+1}+C$ .

Dies führt schließlich zur Lösung:

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

Siehe auch

Literatur

A. O. Gelfond: Differenzenrechnung. Dt. Verlag d. Wiss., Berlin, 1958
Ronald Graham u. a.: Concrete Mathematics. Addison-Wesley, Upper Saddle River 2008, ISBN 0-201-55802-5
N. E. Nörlund: Vorlesungen über Differenzenrechnung. Springer-Verlag, Berlin, 1924; Reprint Chelsea, New York, 1954

Weblinks

Brian Hamrick: Discrete Calculus (PDF, 70 kB)