Vollständige Induktion einer rekursiven Folge

Erste Frage Aufrufe: 57     Aktiv: 05.04.2021 um 18:01

1

Hi,

ich lerne gerade für eine Mathematik Klausur und komme bei dem beweis dieser Aufgabe nicht weiter:

 

Gegeben: \(c_{0} = a\); \(c_{1} = b\); \(c_{n} = \frac{1}{2}(c_{n-1} + c_{n-2})\)

Zu Beweisen ist, dass

\(c_{n}=a+ \sum_{i=0}^{n-1} (- \frac {1}{2})^i * (b-a)\)

gilt.

Ich weiß, dass ich im Induktionsanfang Geltung der Aussage für \(c_{1}\) und \(c_{2}\) zeigen muss, was auch selbst erklärend ist.

Ich weiß allerdings nicht, was im Induktionsschritt zu tun ist, um Geltung der Aussage für \(c_{n+1}\) zu beweisen.


Ich hoffe es gibt jemanden, der mir dabei helfen kann.

Vielen Dank im Voraus!

Diese Frage melden
gefragt

Punkte: 15

 

1
Mit \(c_{n-1}\) (c_{n-1}) kannst du übrigens Indizes korrekt darstellen.   ─   posix 05.04.2021 um 16:24

Sorry, bin nicht ganz vertraut mit dem Code. Hab es korrigiert.   ─   cazo0 05.04.2021 um 16:29

Kommentar schreiben

1 Antwort
1
Betrachte das Folgenglied \(c_{n+1}\) indem du zu dessen Berechnung die Rekursionsvorschrift verwendest. Benutze nun für die vorherigen Folgenglieder die Induktionsvorraussetzung \(c_n = a + \sum_{i=0}^{n-1} (-\frac{1}{2})^i (b-a) \) und versuche den Ausdruck zu \(c_{n+1} = \frac{1}{2} (c_n + c_{n-1} = ... = a + \sum_{i=0}^{n} (-\frac{1}{2})^i (b-a)\) umzuformen.

Übrigens ist das ganze natürlich umgekehrt möglich, also \(c_{n+1} = a + \sum_{i=0}^{n} (-\frac{1}{2})^i (b-a) = ... = \frac{1}{2} (c_n + c_{n-1}\), indem du die Summe auseinanderziehst und mit Indexshifts usw. auf die richtige Form bringst.

Noch ein kleiner Hinweis/Tipp: \( (-\frac{1}{2})^i = -2 (-\frac{1}{2}) (-\frac{1}{2})^{i} = -2(-\frac{1}{2})^{i+1}\)
Diese Antwort melden
geantwortet

Student, Punkte: 595
 

Diesen Ansatz hatte ich bereits verfolgt aber möglicherweise einen Fehler gemacht.

Mit \(c_{n+1} = \frac{1}{2}(c_{n} + c_{n-1})\)

erhalte ich

\(\frac{1}{2}(a+ \sum_{i = 0}^{n-1}(- \frac {1}{2})^i(b-a) + a + \sum_{i=0}^{n-2})(- \frac{1}{2})(b-a))\)

da mein Ziel ist (glaube ich jedenfalls) die Gleichung in \(c_{n+1} = a+\sum_{i = 0}^{n}(\frac{1}{2})^i)(b-a)\) umzuwandeln habe ich ein Summenglied der ersten Summenfolge herausgezogen um dann beide Summenfolgen zusammen zu setzen:

\(\frac{1}{2}(2a+\sum_{i=0}^{n-2}2((-\frac{1}{2})^i)(b-a)) + (-\frac{1}{2})^{n-1}(b-a)\)

Dann habe ich die 2 in der Summenfolge herausgezogen und das Summenglied wieder zur Summe hinzugefügt:

\(\frac{1}{2}(2a+2\sum_{i=0}^{n-1}(-\frac{1}{2})^i(b-a))\)

Nach dem Ausmultiplizieren erhalte ich:

\(a+\sum_{i=0}^{n-1}(-\frac{1}{2})^i)(b-a)\)

Das Ergebnis sieht zwar richtig aus aber die Summe müsste bis \(c_{n}\) gehen und nicht bis \(c_{n-1}\) oder nicht?



  ─   cazo0 05.04.2021 um 17:09

Du kannst das Summenglied nicht einfach wieder in die Summe ziehen, da der Faktor 2 fehlt.
Ich würde zuerst das \(n-1\)-te Summenglied hinzufügen und wieder abziehen (den Faktor \((b-a)\) hab ich im folgenden ausgeklammert), also \[2\sum_{i=0}^{n-2} (-\frac{1}{2})^i + (-\frac{1}{2})^{n-1}= 2\sum_{i=0}^{n-1} (-\frac{1}{2})^i \; - 2(-\frac{1}{2})^{n-1} + (-\frac{1}{2})^{n-1} =\\ =2 \sum_{i=0}^{n-1} (-\frac{1}{2})^i \; -(-\frac{1}{2})^{n-1} = 2 \sum_{i=0}^{n-1} (-\frac{1}{2})^i \; + 2 (-\frac{1}{2})^n \;\]
Der hintere Summand kann nun einfach als n-ter Summand in die Summe gezogen werden und man erhält das gewünschte Ergebnis.
  ─   posix 05.04.2021 um 17:52

Das leuchtet ein!

Ich bedanke mich!
  ─   cazo0 05.04.2021 um 18:01

Kommentar schreiben