TU Wien:Algebra und Diskrete Mathematik VU (diverse)/Übungen 2025W/Beispiel 231

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

$\sum _{i=1}^{n}i$

Dieses Beispiel hat einen unbekannten Lösungsstatus. Bitte editiere diese Seite und schreibe den dir bekannten Status ins Beispiel. Die möglichen Werte sind hier: Vorlage:Beispiel dokumentiert. Führe folgende Änderung durch:

{{Beispiel|1=
Angabetext
}}

oder

{{Beispiel|
Angabetext
}}

zu (im Falle einer korrekten, unverifizierten Lösung "solved". Auch möglich "unsolved", "wrong", "verified_by_tutor". Alle möglichen Werte sind hier: Vorlage:Beispiel dokumentiert.)

{{Beispiel|status=solved|1=
Angabetext
}}

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

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

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

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

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

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

• Diskussion im Informatik-Forum / SS07 Beispiel E10

Ähnliche Beispiele:

• TU Wien:Mathematik 2 UE (diverse)/Übungen WS07/Beispiel 235
• TU Wien:Mathematik 2 UE (diverse)/Übungen WS07/Beispiel 236