Mathematik online lernen im Mathe-Forum. Nachhilfe online

Startseite » Forum » Vollständige Induktion bei Doppelsumme

Vollständige Induktion bei Doppelsumme

Universität / Fachhochschule

Tags: Summenformel, Vollständig Induktion

Ninad aktiv_icon

21:55 Uhr, 04.05.2014

Hallo zusammen,

ich bräuchte mal ein wenig Erklärungsbedarf bei einer vollständigen Induktion mit einer Doppelsumme. Wie die vollständige Induktion an sich funktioniert, weiß ich. Hab das allerdings noch nie an so einer Doppelsummenformel gesehen.
Wir haben eine Aufgabe dazu und auch eine Musterlösung bekommen, allerdings kann ich die einzelnen Schritte nicht ganz nachvollziehen.

Die Aufgabe sieht so aus:

Es seien

a_{i, k}

reelle Zahlen für

i, k \in ℕ

. Zeigen Sie, dass für alle

n \in ℕ

gilt:

\sum_{k = 0}^{n} \sum_{i = 0}^{n - k} a_{i, k} = \sum_{m = 0}^{n} \sum_{k = 0}^{m} a_{m - k, k}

.

Mit Doppelsumen habe ich generell noch nie gearbeitet, deswegen habe ich keine Ahnung, wie eine Induktion dazu aussehen würde.

Hier die Musterlösung:

Induktionsanfang

= 0

Das ist mir noch klar, da beide Seiten der Formel dann nur aus dem Term

a_{00}

bestehen.

Induktionsschritt

n \to n + 1

\sum_{k = 0}^{n + 1} \sum_{i = 0}^{n + 1 - k} a_{i, k}

= \sum_{k = 0}^{n + 1} (\sum_{i = 0}^{n - k} a_{i, k} + a_{n + 1 - k, k})

(ab diesem Schritt verstehe ich nichts mehr...)

= \sum_{k = 0}^{n} (\sum_{i = 0}^{n - k} a_{i, k} + a_{n + 1 - k, k}) + a_{0, n + 1}

= \sum_{k = 0}^{n} \sum_{i = 0}^{n - k} a_{i, k} + \sum_{k = 0}^{n} a_{n + 1 - k, k} + a_{0, n + 1}

(IV)

= \sum_{m = 0}^{n} \sum_{k = 0}^{m} a_{m - k, k} + \sum_{k = 0}^{n + 1} a_{n + 1 - k, k}

= \sum_{m = 0}^{n + 1} \sum_{k = 0}^{m} a_{m - k, k}

.

Kann mir jemand zu den einzelnen Schritten was erklären? Vom Prinzip her verstehe ich das, man will so lange umformen, bis man die Iv einsetzen kann und am Ende wieder auf das gleiche kommt, aber die einzelnen Umformungen kann ich nicht nachvollziehen.

Wäre für jede Erklärung dankbar! :-)

Für alle, die mir helfen möchten (automatisch von OnlineMathe generiert):
"Ich möchte die Lösung in Zusammenarbeit mit anderen erstellen."

Bummerang

07:53 Uhr, 05.05.2014

Hallo,

"ab diesem Schritt verstehe ich nichts mehr..."

Das kann daran liegen, dass dieser erste Schritt den zweiten unverständlich macht. Dadurch, dass die innere Summe von

i = 0

bis

n + 1 - k

geht, ist es nachvollziehbar, wie diese Summe für

k = n + 1

aussieht, nämlich von

i = 0

bis 0. Zerlegt man diese Summe aber wie hier im ersten Schritt, dann hat man eine Summe, die von

i = 0

bis

n - k

geht und damit für

k = n + 1

eine Summe, die von

i = 0

bis

n - n - 1 = - 1

geht. Deshalb ist dieses Vorgehen fragwürdig. richtiger würde man die Summe von aussen her auflösen:

\sum_{k = 0}^{n + 1} (\sum_{i = 0}^{n + 1 - k} a_{i, k})

= \sum_{k = 0}^{n} (\sum_{i = 0}^{n + 1 - k} a_{i, k}) + \sum_{i = 0}^{n + 1 - (n + 1)} a_{i, n + 1}

= \sum_{k = 0}^{n} (\sum_{i = 0}^{n + 1 - k} a_{i, k}) + \sum_{i = 0}^{0} a_{i, n + 1}

= \sum_{k = 0}^{n} (\sum_{i = 0}^{n + 1 - k} a_{i, k}) + a_{0, n + 1}

= \sum_{k = 0}^{n} ((\sum_{i = 0}^{n - k} a_{i, k}) + a_{n + 1 - k, k}) + a_{0, n + 1}

An dieser Stelle sind wir wieder in der Spur der Vorlage und ich denke, dass hier die einzelnen Schritte klarer sind. Jetzt haben wir hier in der Doppelsumme lauter Summanden, die wiederum Summanden sind, eine Summe und ein einfacher Summand. Jetzt ordnet man diese endliche Anzahl von Summanden einfach um, indem man zunächst alle ersten Summanden addiert (da das die inneren Summen sind ergibt das wieder eine Doppelsumme) und dann alle zweiten Summanden (Summe einfacher Summanden):

= \sum_{k = 0}^{n} (\sum_{i = 0}^{n - k} a_{i, k}) + \sum_{k = 0}^{n} (a_{n + 1 - k, k}) + a_{0, n + 1}

Auf die Doppelsumme wird die Induktionsvoraussetzung angewandt, der letzte Summand wird mit einem Trick

(a_{0, n + 1} = a_{n + 1 - (n + 1), n + 1} = a_{n + 1 - k, k}

für

k = n + 1)

so umgewandelt, dass er in die zweite einfache Summe integriert werden kann als Summand für

k = n + 1 :

= \sum_{m = 0}^{n} (\sum_{k = 0}^{m} a_{m - k, k}) + \sum_{k = 0}^{n + 1} a_{n + 1 - k, k}

Jetzt wird die zweite Summe wieder etwas umgeformt, denn wenn man

m = n + 1

einsetzt, dann ergibt sich

\sum_{k = 0}^{n + 1} a_{n + 1 - k, k} = \sum_{k = 0}^{m} a_{m - k, k}

und das ist nichts anderes als der Summand, der für

m = n + 1

in die erste Summe integriert werden kann:

= \sum_{m = 0}^{n + 1} (\sum_{k = 0}^{m} a_{m - k, k})

Ninad aktiv_icon

20:21 Uhr, 05.05.2014

Danke für die Mühe! :-)
Das macht es in der Tat etwas klarer. Musste mir auch selbst erstmal richtig klar machen, was sind Doppelsummen, wie funktionieren sie, usw. Aber ich denke, ich hab es so ganz gut verstanden.

Viele Grüße.

1162769

1162572

	Status: nicht eingeloggt	Noch nicht registriert?