Beweis durch vollständige Induktion

28.10.2010, 18:40

Martin Matschke

Beweis durch vollständige Induktion

Meine Frage:
Hallo!

Ich soll für alle $\begin{eqnarray*} n \in \mathbb N /\{0\} \end{eqnarray*}$ folgendes zeigen:

$\begin{eqnarray*} \sum_{k = 1} ^{n} a_{k}b_{k} = a_{n} \sum_{k = 1} ^{n} b_{k} - \sum_{k = 1} ^{n-1} (a_{k+1} - a_{k}) \sum_{j = 1} ^{k} b_{j} \end{eqnarray*}$

komme aber nicht weiter.

Meine Ideen:
Als erstes den Induktionsanfang:

ich wähle n = 1

$\begin{eqnarray*} \sum_{k = 1} ^{1} a_{k}b_{k} = a_{1} \sum_{k = 1} ^{1} b_{k} - \sum_{k = 1} ^{0} (a_{k+1} - a_{k}) \sum_{j = 1} ^{k} b_{j} \end{eqnarray*}$

ergibt:

$\begin{eqnarray*} a_{1}b_{1} = a_{1}b_{1} - 0 \end{eqnarray*}$

Die Aussage stimmt also für 1.

Jetzt die Induktionsbehauptung:

$\begin{eqnarray*} \sum_{k = 1} ^{n+1} a_{k}b_{k} = a_{n+1} \sum_{k = 1} ^{n+1} b_{k} - \sum_{k = 1} ^{n} (a_{k+1} - a_{k}) \sum_{j = 1} ^{k} b_{j} \end{eqnarray*}$

So jetzt der schwierige Teil:

$\begin{eqnarray*} \sum_{k = 1} ^{n+1} a_{k}b_{k} = \sum_{k = 1} ^{n} a_{k}b_{k} + a_{k+1}b_{k+1} \end{eqnarray*}$

Hier ergibt sich schon die erste Unsicherkeit: ist k als Index richtig gewählt?

Das oben kann man noch umformen zu

$\begin{eqnarray*} \sum_{k = 1} ^{n+1} a_{k}b_{k} = a_{n} \sum_{k = 1} ^{n} b_{k} - \sum_{k = 1} ^{n-1} (a_{k+1} - a_{k}) \sum_{j = 1}^{k} b_{j} + a_{k+1}b_{k+1} \end{eqnarray*}$

Und jetzt weiss ich überhaupt nicht mehr wie's weitergehen könnte, ich weiss insbesondere nicht, was mit diesem $\begin{eqnarray*} \sum_{j = 1} ^{k} b_{j} \end{eqnarray*}$ zu tun ist ;-(

Wäre für einen Fingerzeig dankbar!

mfg

Martin

28.10.2010, 18:57

tmo

Auf diesen Beitrag antworten »

Im Großen und Ganzen reduziert sich mit $\begin{eqnarray*} B_k := \sum_{j=1}^k b_j \end{eqnarray*}$ das ganze auf den Beweis von:

$\begin{eqnarray*} \sum_{k=1}^{n-1} (a_{k+1}-a_k)B_k = -a_1b_1 + \sum_{k=2}^{n-1} (a_k(B_{k-1}-B_k)) ~ + a_nB_{n-1} \end{eqnarray*}$

Das kannst du induktiv beweisen. Mache es dir aber vielleicht auch mal so klar, das ist so etwas wie eine Teleskopsumme.

Das gilt übrigens für alle Folgen $\begin{eqnarray*} a_n,B_n \end{eqnarray*}$ also unabhängig davon, wie $\begin{eqnarray*} B_k \end{eqnarray*}$ oben definiert ist.

Erst wenn man dieses Puzzleteil dann (ohne Induktion, sondern direkt) zum Beweis der Behauptung zusammensetzt, sollte man sich das wieder in Erinnerung rufen.

28.10.2010, 19:06

Martin Matschke

Auf diesen Beitrag antworten »

Danke für deine Antwort, nur kann ich dir leider nicht ganz folgen. Warum reduziert sich der Beweis darauf?

28.10.2010, 19:11

tmo

Auf diesen Beitrag antworten »

Nunja, du hast dir nicht viel Zeit gelassen um das herauszufinden.

Setz das doch einfach mal in deiner Behauptung ein und sieh selbst, dass man dann recht schnell fertig ist.

Natürlich sollte man sich vorher bewusst machen, was $\begin{eqnarray*} B_{k-1}-B_k \end{eqnarray*}$ ist.

29.10.2010, 13:57

Martin Matschke

Auf diesen Beitrag antworten »

Auch mit einmal darüber schlafen werde ich nicht schlauer daraus. Außerdem kann

$\begin{eqnarray*} \sum_{k=1}^{n-1}(a_{k+1}-a_{k})B_{k} = -a_{1}b{1} + \sum_{k=2}^{n-1}(a_{k}(B_{k-1}-B_{k}))+a_{n}B_{n-1} \end{eqnarray*}$

nicht stimmen, denn wenn ich für n = 2 einsetze ergibt das doch

$\begin{eqnarray*} \sum_{k=1}^{1}(a_{k+1}-a{k})B_{k} = -a_{1}b_{1} + \sum_{k=2}^{1}(a_{k}(B_{k-1}-B_{k}))+a_{2}B_{1} \end{eqnarray*}$

und das ist

$\begin{eqnarray*} (a_{2} - a_{1})B_{1} = -a_{1}b_{1} + a_{2}B_{1} \end{eqnarray*}$

was ja falsch ist?!

29.10.2010, 14:00

tmo

Auf diesen Beitrag antworten »

Zitat:

Original von Martin Matschke
und das ist

$\begin{eqnarray*} (a_{2} - a_{1})B_{1} = -a_{1}b_{1} + a_{2}B_{1} \end{eqnarray*}$

was ja falsch ist?!

Überzeuge dich davon, dass das richtig ist.

Allerdings muss ich hier einen Rückzieher machen, dass das für alle Folgen $\begin{eqnarray*} B_n \end{eqnarray*}$ richtig ist. Aber man ersetze einfach $\begin{eqnarray*} b_1 \end{eqnarray*}$ durch $\begin{eqnarray*} B_1 \end{eqnarray*}$ und dann ist es wieder für alle Folgen richtig. Hier gilt ja aber sowieso $\begin{eqnarray*} b_1=B_1 \end{eqnarray*}$

Man kommt übrigens ganz ohne Induktion aus. Aber mit Induktion ist es vielleicht ein bisschen einfacher.

29.10.2010, 16:19

Martin Matschke

Auf diesen Beitrag antworten »

Ok, es stimmt dass $\begin{eqnarray*} b_{1} = B_{1} \end{eqnarray*}$ , da ja $\begin{eqnarray*} B_{k} = \sum_{j=1}^{k}b_{j} \end{eqnarray*}$ und somit ist $\begin{eqnarray*} B_{1} = \sum_{j=1}^{1}b_{j} = b_{1} \end{eqnarray*}$

Und $\begin{eqnarray*} B_{k-1} - B_{k} = b_{k} \end{eqnarray*}$ wegen $\begin{eqnarray*} B_{k-1} - B_{k} = \sum_{j=1}^{k-1}b_{j} - \sum_{j=1}^{k}b_{j} = b_{1} + b_{2} + \dots + b_{k-1} - (b_{1} + b_{2} + \dots + b_{k-1} + b_{k}) = b_{k} \end{eqnarray*}$

Aber wie man die Umformung von dir hinbekommt raff ich immer noch nicht. Bin wohl ungewöhnlich begriffstutzig :-/

29.10.2010, 16:22

Martin Matschke

Auf diesen Beitrag antworten »

$\begin{eqnarray*} -b_{k} \end{eqnarray*}$

29.10.2010, 16:27

tmo

Auf diesen Beitrag antworten »

Das wäre ja immerschon mal geklärt. Jetzt habe ich noch die Frage, was genau dir jetzt unklar ist:

- Die Gleichung, die ich meinem 1. Post geschrieben habe

- Oder wie man von der Gleichung dann letztendlich zur ursprünglichen Behauptung kommt

Oder noch beides?

29.10.2010, 16:51

Martin Matschke

Auf diesen Beitrag antworten »

Beides.

Ich beginne mal mit dieser Umformung:

$\begin{eqnarray*} \sum_{k=1}^{n-1}(a_{k+1}-a_{k})B_{k} = -a_{1}b_{1} + \sum_{k=2}^{n-1}(a_{k}(B_{k-1}-B_{k})) + a_{n}B_{n-1} \end{eqnarray*}$

Ich könnte mir vorstellen, dass als erstes mit $\begin{eqnarray*} B_{k} \end{eqnarray*}$ multipliziert wird:

$\begin{eqnarray*} \sum_{k=1}^{n-1}(a_{k+1}B_{k}-a_{k}B_{k}) \end{eqnarray*}$

dann wird $\begin{eqnarray*} a_{k} \end{eqnarray*}$ herausgehoben:

$\begin{eqnarray*} \sum_{k=1}^{n-1}(a_{k}(a_{1}B_{k}-B_{k})) \end{eqnarray*}$

und dann gehts nicht mehr weiter, keine Ahnung was man jetzt machen kann verwirrt

29.10.2010, 16:59

tmo

Auf diesen Beitrag antworten »

Du brauchst doch eine Teleskopsumme.

Also $\begin{eqnarray*} \sum_{k=1}^{n-1} (a_{k+1}-a_k)B_k = \sum_{k=1}^{n-1} (a_{k+1}B_{k+1}-a_kB_k +a_{k+1}B_k-a_{k+1}B_{k+1}) \end{eqnarray*}$

Nun Summe auseinanderziehen: die ersten 2 Summanden als Teleskopsumme auswerten und wie man die letzten 2 Summanden bearbeitet, sollte eigentlich klar sein.

30.10.2010, 15:57

Martin Matschke

Auf diesen Beitrag antworten »

Mir ist nicht mal deine Teleskopsumme klar, ich hab zwar im Internet gesucht, aber da steht nur wie man das Teleskop zusammenklappt, aber nicht wie man es auseinanderzieht.

Nun gut:

$\begin{eqnarray*} \sum_{k=1}^{n-1} (a_{k+1}-a_k)B_k = \sum_{k=1}^{n-1} (a_{k+1}B_{k+1}-a_kB_k +a_{k+1}B_k-a_{k+1}B_{k+1}) \end{eqnarray*}$

Ausgehend von

$\begin{eqnarray*} \sum_{k=1}^{n-1} (a_{k+1}-a_k)B_k = \sum_{k=1}^{n-1} (a_{k+1}B_{k} - a_{k}B_{k}) \end{eqnarray*}$

ist mir nur klar, dass du

$\begin{eqnarray*} \sum_{k=1}^{n-1} a_{k+1}B_{k+1} - a_{k+1}B_{k+1} \end{eqnarray*}$

zu

$\begin{eqnarray*} \sum_{k=1}^{n-1} (a_{k+1}B_{k} - a_{k}B_{k}) \end{eqnarray*}$

dazuaddierst.

Woher du das bekommst ist mir allerdings ein Rätsel. Ich dachte daran, zwei Glieder der Summe auszuschreiben
also

$\begin{eqnarray*} \sum_{k=1}^{n-1} (a_{k+1}B_{k} - a_{k}B_{k}) = \sum_{k=1}^{n-1}(a_{k+1}B_{k} - a_{k}B_{k}) + (a_{k+2}B_{k+1} - a_{k+1}B_{k+1}) = \sum_{k=1}^{n-1}-a_{k+1}B_{k+1}-a_{k}B_{k} + a_{k+1}B_{k} + a_{k+2}B_{k+1} \end{eqnarray*}$

was aber, wie ich gerne zugebe, ganz offensichtlich NICHT das erwünschte Ergebnis bringt... unglücklich

30.10.2010, 21:34

Martin Matschke

Auf diesen Beitrag antworten »

So ich denke ich habe ungefähr heraußen wie es geht, bis auf ein paar Kleinigkeiten:

Wir gehen aus von:

$\begin{eqnarray*} \sum_{k=1}^{n-1} (a_{k+1}B_{k} - a_{k}B_{k}) \end{eqnarray*}$

davon subtrahieren wir das Folgeglied:

$\begin{eqnarray*} \sum_{k=1}^{n-1} (a_{k+1}B_{k} - a_{k}B_{k}) = \sum_{k=1}^{n-1} (a_{k+1}B_{k} - a_{k}B_{k}) - (a_{k+2}B_{k+1}-a_{k+1}B_{k+1}) \end{eqnarray*}$

das stellen wir um:

$\begin{eqnarray*} \sum_{k=1}^{n-1} (a_{k+1}B_{k+1} - a_{k}B_{k} + a_{k+1}B_{k} -a_{k+1}B_{k+1}) \end{eqnarray*}$

(bei dir steht $\begin{eqnarray*} a_{k+1} \end{eqnarray*}$ anstatt $\begin{eqnarray*} a_{k+2} \end{eqnarray*}$ was ich nicht verstehe, aber mal übernehme)

jetzt wird die Teleskopsumme links ausgewertet und bei den beiden Summanden rechts eine Indexverschiebung durchgeführt

$\begin{eqnarray*} -a_{1}B_{1} + a_{n}B_{n} + \sum_{k=2}^{n-1} a_{k}B_{k-1} - a_{k}B_{k} \end{eqnarray*}$

Zu guter letzt wird $\begin{eqnarray*} a_{k} \end{eqnarray*}$ herausgehoben und das $\begin{eqnarray*} a_{n}B_{n} \end{eqnarray*}$ rechts von der Summe geschrieben (aus ästhetischen Gründen?)

$\begin{eqnarray*} -a_{1}B_{1} + \sum_{k=2}^{n-1} (a_{k}(B_{k-1} - B_{k})) + a_{n}B_{n} \end{eqnarray*}$

Natürlich gibt's Schönheitsfehler:

erstens das $\begin{eqnarray*} a_{k+2} \end{eqnarray*}$ anstatt dem $\begin{eqnarray*} a_{k+1} \end{eqnarray*}$
zweitens das $\begin{eqnarray*} a_{n}B_{n} \end{eqnarray*}$ anstatt dem $\begin{eqnarray*} a_{n}B_{n-1} \end{eqnarray*}$
drittens fehlt mir immer noch meine Behauptung

und natürlich:

WIE soll man denn auf das ganze VON ALLEINE draufkommen? Erstaunt2

Neue Frage »

Antworten »

Beweis durch vollständige Induktion

Verwandte Themen