TU Wien:Algebra und Diskrete Mathematik UE (diverse)/Übungen SS19/Beispiel 224

Aus VoWi
Wechseln zu: Navigation, Suche

Berechnen Sie die folgenden Summen durch Aufstellen und Lösen einer Rekursion mittels Ansatzmethode.

\sum_{i=1}^ni


Lösung von - -Mikazuki 12:10, 10. Jun 2007 (CEST)[Bearbeiten]

Aufstellen einer Rekursion:

x_n=x_{n-1}+n

Homogene Lösung:

x_n^{(h)}=C\cdot\prod_{i=0}^{n-1} 1 = C

x_0=0: c = 0

Partikuläre Lösung:

  • Ansatz 1: x_n^{(p)} = A + n \cdot B A ist in homogener Lösung enthalten ...
  • Ansatz 2: x_n^{(p)} = n \cdot A + n^2 \cdot B

Einsetzen in die inhomogene Gleichung:

n\cdot A + n^2\cdot B - (n-1)\cdot A - (n-1)^2\cdot B = n

n\cdot 2*B + (A-B) = n

Koeffizientenvergleich:

  • n^1: 2\cdot B = 1 \Rightarrow B = \frac{1}{2}
  • n^0: A-B=0 \Rightarrow A = \frac{1}{2}

x_n^{(p)}=\frac{n}{2}+\frac{n^2}{2}=\frac{n\cdot (n+1)}{2}

Allgemeine Lösung:

x_n = x_n^{(h)} + x_n^{(p)} = 0 + \frac{n\cdot (n+1)}{2} = \frac{n\cdot (n+1)}{2}

Anmerkung von Berti[Bearbeiten]

Den Wert von C sollte man eigentlich erst zum Schluss berechnen. Hier ist es zufälligerweise egal, beim Beispiel 226 sieht man aber, dass es nicht immer egal ist.

Lösung von Berti[Bearbeiten]

Die Lösung von Mikazuki ist richtig, allerdings möchte ich ein paar Erklärungen ergänzen:

Zuerst muss man die Rekursion aufstellen, d.h. eine Gleichung finden, die wie eine Differenzialgleichung aussieht. Dabei hilft, wenn man sich die ersten paar Ergebnisse für n ansieht und dann versucht, daraus eine allgemeine Regel abzuleiten. Anschließend kommt man recht schnell auf die Formel x_n = x_{n-1} + n. Mir gefällt allerdings die Form x_{n+1} = x_n + n + 1 besser, da man hier schnell auf die homogene Lösung kommt.

Homogene Lösung[Bearbeiten]

Zuerst suchen wir wie immer die homogene Lösung der Gleichung. Dazu müssen wir wissen, dass alle Terme, die nicht x_n beinhalten, Teil der Störfunktion sind. Unsere Störfunktion ist also n + 1.

Die zu lösende homogene Gleichung ist also: x_{n+1} = x_n. Nachdem a = 1 und b = 0 ist, ist gemäß der Lösungsformel für homogene DGL 1. Ordnung die Lösung x_n = a \cdot x_0 + b \cdot n = 0.

Partikuläre Lösung[Bearbeiten]

Nun zur partikulären Lösung.

Hier verwenden wir die Ansatzmethode. Unsere Störfunktion n + 1 ist ein Polynom 1. Grades. Deshalb verwenden wir als Ansatz A_0 + A_1 \cdot n. Da allerdings die homogene Lösung konstant ist und A_0 ebenfalls konstant und somit Teil der homogenen Lösung ist, müssen wir den Term mit n multiplizieren (Resonanzfall).

Unser Ansatz lautet daher: x_n^{(p)} = A_0 \cdot n + A_1 \cdot n^2. Diesen Ansatz setzen wir nun in die ursprüngliche rekursive Gleichung für x ein:

A_0(n+1) + A_1(n+1)^2 = A_0 \cdot n + A_1 \cdot n^2 + n + 1

A_0 + 2A_1 \cdot n + A_1 = n + 1

Wir haben nun zwei Variablen, aber nur eine Gleichung. Wie geht es also weiter? Mit Hilfe eines Koeffizientenvergleichs können wir den Wert von A_1 bestimmen. Dazu müssen wir wissen, dass nachdem wir ja in die ursprüngliche Gleichung (DGL) eingesetzt haben, die Koeffizienten der DGL und der "Ansatzgleichung" ebenfalls identisch sein müssen:

Anders gesagt muss 2A_1 = 1 sein, weil der Koeffizient von n in der Störfunktion ebenfalls 1 ist und 2A_1 unser Koffizient von n nach Anwenden der Ansatzmethode ist. Dadurch wissen wir nun, dass A_1 = \frac{1}{2} gilt. Womit wir uns auch A_0 berechnen können: A_0 + n + \frac{1}{2} = n + 1 \Rightarrow A_0 = \frac{1}{2}.

Somit haben wir eine partikuläre Lösung gefunden: x_n^{(p)} = \frac{1}{2} n + \frac{1}{2} n^2

Die Lösung lautet somit: x_n = \frac{n + n^2}{2} = \frac{n(n+1)}{2}, auch bekannt unter dem Namen Gaußsche Summenformel.

-- Berti933 (Diskussion) 00:00, 21. Jan. 2015 (CET)

Links[Bearbeiten]

Ähnliche Beispiele: