Doppelpost! Umformulierung einer Summe

18.08.2015, 12:47	lowbrow	Auf diesen Beitrag antworten »
Umformulierung einer Summe Hallo zusammen, ich beschäftige mich derzeit mit der Performance von Quicksort, genauer mit dem Erwartungswert der Anzahl der nötigen Vergleiche. Hierbei wird eine Summe umgeformt, ich kann den Schritt aber nicht ganz nachvollziehen, vielleicht kann mir jemand auf die Sprünge helfen. $\begin{eqnarray} <br /> \sum_{k=1}^{n}\frac{2(k-1)}{k(k+1)}=2H_{n}-\frac{4n}{n+1},\qquad H_{n} \text{ ist die nte harmonische Reihe}<br /> \end{eqnarray}$ Vielen Dank im Voraus!
18.08.2015, 12:59	HAL 9000	Auf diesen Beitrag antworten »
Es ist $\begin{align} \sum_{k=1}^n \frac{2(k-1)}{k(k+1)} = \sum_{k=1}^n \frac{2(k+1)-4}{k(k+1)} = 2\sum_{k=1}^n \frac{1}{k} - 4\sum_{k=1}^n \frac{1}{k(k+1)} = 2H_n - 4\left(1-\frac{1}{n+1}\right) \end{align}$ , die zweite Summe ist infolge $\begin{align} \frac{1}{k(k+1)} = \frac{1}{k}-\frac{1}{k+1} \end{align}$ eine Teleskopsumme.
18.08.2015, 17:56	Mathema	Auf diesen Beitrag antworten »
Mein Weg war übrigens identisch mit dieser Empfehlung, also: $\begin{eqnarray} \sum\limits_{k=1}^{n} \frac{2(k-1)}{k(k+1)}=2\sum\limits_{k=1}^{n} \frac{k-1}{k(k+1)}=2\sum\limits_{k=1}^{n} (\frac{2}{k+1}-\frac{1}{k})=2(2\sum\limits_{k=1}^{n} (\frac{1}{k}-\frac{1}{k(k+1)})-\sum\limits_{k=1}^{n} \frac{1}{k})=2(\sum\limits_{k=1}^{n} \frac{1}{k}-2\sum\limits_{k=1}^{n} \frac{1}{k(k+1)}) \end{eqnarray}$ Der Weg von HAL ist aber mal wieder wesentlich eleganter und kürzer. PS: Es wäre nett, wenn du in Zukunft solche Doppelposts unterlässt. Das kannst du auch dort nachlesen. Prinzip "Mathe online verstehen!"
18.08.2015, 23:20	rg	Auf diesen Beitrag antworten »
Weil das letztens so gut ankam, poste ich noch eine alternative Loesung mit Finite Calculus und partieller Summation: $\begin{eqnarray} \sum_{k=1}^n\frac{k-1}{k(k+1)}=\sum\nolimits_0^n x\cdot x^{\underline{-2}}\,\,\delta x=\left[-x\cdot x^{\underline{-1}}\right]_0^n+\sum\nolimits_0^n(x+1)^{\underline{-1}}\,\,\delta x=-\frac{n}{n+1}+H_{n+1}-1 \end{eqnarray}$ Kommst tasaechlich dasselbe raus wie oben.
27.08.2015, 14:54	lowbrow	Auf diesen Beitrag antworten »
Super, vielen Dank für die Antworten! Habe mir schon gedacht, dass es was mit Partialbruchzerlegung sein würde, habe es aber nicht richtig hinbekommen.

1

Verwandte Themen

Die Beliebtesten »

Die Größten »

Die Neuesten »