Vollständige Induktion

01.12.2007, 10:58

Musti

Auf diesen Beitrag antworten »

Vollständige Induktion

Hallo

Wink

Da ich mal wieder Zeit habe möchte ich die Vollständige Induktion verinnerlichen und besser können.
Bisher konnte ich es nur grob, also da war nichts halbes und nichts ganzes.
Es wäre nett wenn ihr mir Schrittweise dabei helfen würdet die Induktion zu beherrschen, am besten direkt anhand einer Aufgabe.

Die Aufgabe lautet: Beweise induktiv die Gleichung: $\begin{eqnarray*} {k \choose k}+{k+1\choose k}+...+{n \choose k}={n+1 \choose k+1} \end{eqnarray*}$ für $\begin{eqnarray*} n=k, k+1,... \end{eqnarray*}$

Also ich gehe davon aus, dass ich ne Induktion über n machen muss.

Induktionsanfang: $\begin{eqnarray*} n=k \end{eqnarray*}$

$\begin{eqnarray*} {k \choose k}={k+1 \choose k+1} \end{eqnarray*}$

$\begin{eqnarray*} 1=1 \end{eqnarray*}$

Induktionsvoraussetzung: Es gilt für alle $\begin{eqnarray*} n=k, k+1,... \end{eqnarray*}$

Induktionsschritt: $\begin{eqnarray*} n\rightarrow n+1 \end{eqnarray*}$

$\begin{eqnarray*} {k \choose k}+{k+1\choose k}+...+{n \choose k}+{n+1 \choose k}={n+2 \choose k+1} \end{eqnarray*}$

Ich denke/ hoffe mal bishierhin ist alles ok.
Jetzt wüsste ich nicht wie ich weitermachen soll, um das zu zeigen.

01.12.2007, 11:13

riwe

Auf diesen Beitrag antworten »

RE: Vollständige Induktion

Zitat:

Original von Musti
Hallo Wink

Wink

Da ich mal wieder Zeit habe möchte ich die Vollständige Induktion verinnerlichen und besser können.
Bisher konnte ich es nur grob, also da war nichts halbes und nichts ganzes.
Es wäre nett wenn ihr mir Schrittweise dabei helfen würdet die Induktion zu beherrschen, am besten direkt anhand einer Aufgabe.

Die Aufgabe lautet: Beweise induktiv die Gleichung: $\begin{eqnarray*} {k \choose k}+{k+1\choose k}+...+{n \choose k}={n+1 \choose k+1} \end{eqnarray*}$ für $\begin{eqnarray*} n=k, k+1,... \end{eqnarray*}$

Also ich gehe davon aus, dass ich ne Induktion über n machen muss.

Induktionsanfang: $\begin{eqnarray*} n=k \end{eqnarray*}$

$\begin{eqnarray*} {k \choose k}={k+1 \choose k+1} \end{eqnarray*}$

$\begin{eqnarray*} 1=1 \end{eqnarray*}$

Induktionsvoraussetzung: Es gilt für alle $\begin{eqnarray*} n=k, k+1,... \end{eqnarray*}$

Induktionsschritt: $\begin{eqnarray*} n\rightarrow n+1 \end{eqnarray*}$

$\begin{eqnarray*} {k \choose k}+{k+1\choose k}+...+{n \choose k}+{n+1 \choose k}={n+2 \choose k+1} \end{eqnarray*}$

Ich denke/ hoffe mal bishierhin ist alles ok.
Jetzt wüsste ich nicht wie ich weitermachen soll, um das zu zeigen.

du mußt auf die letzte zeile doch nur die IV anwenden

$\begin{eqnarray*} {n+1 \choose k+1}+{n+1 \choose k}={n+2 \choose k+1} \end{eqnarray*}$

linke seite "ausmultiplizieren" und auf gleichen nenner bringen, ergibt die rechte seite.

01.12.2007, 11:34

Musti

Auf diesen Beitrag antworten »

RE: Vollständige Induktion
Also:

$\begin{eqnarray*} \frac{(n+1)(n)(n-1)...(n-k+1)}{(k+1)!}+\frac{(k+1) (n+1)(n)(n-1)...(n-k+2)}{(k+1)!}=\frac{(n-k+1+k+1)(n+1)(n)(n-1)...(n-k+2)}{(k+1)!} = \frac{(n+2)(n+1)(n)(n-1)...(n-k+2)}{(k+1)!}={n+2 \choose k+1} \end{eqnarray*}$

So müsste das doch stimmen oder?

01.12.2007, 11:49

riwe

Auf diesen Beitrag antworten »

RE: Vollständige Induktion
ist mir zu lange, aber sicher richtig Freude

Freude

$\begin{eqnarray*} \begin{pmatrix} n+1 \\ k+1 \end{pmatrix} +\begin{pmatrix} n+1 \\ k \end{pmatrix} =\frac{(n+1)!}{(n+1-k-1)!(k+1)!}+\frac{(n+1)!}{(n+1-k)!k!}=\frac{(n+1)!(n-k+1+k+1)}{(n-k+1)!(k+1)!}=\begin{pmatrix}n+2\\ k+1 \end{pmatrix} \end{eqnarray*}$

01.12.2007, 12:09

Musti

Auf diesen Beitrag antworten »

RE: Vollständige Induktion
Cool, danke dir riwe smile

smile

Ich habs mit der Definition: $\begin{eqnarray*} {n \choose k}=\frac{n(n-1)...(n-k+1)}{k!} \end{eqnarray*}$ gemacht und du mit $\begin{eqnarray*} {n \choose k}=\frac{n!}{(n-k)!k!} \end{eqnarray*}$ , wobei deins natürlich kürzer ist Augenzwinkern

Augenzwinkern

So nun möchte ich den binomischen Satz induktiv beweisen.

$\begin{eqnarray*} (a+b)^n=\sum_{k=0}^n~{n \choose k}a^kb^{n-k} \end{eqnarray*}$

Induktionsanfang: $\begin{eqnarray*} n=0 \end{eqnarray*}$

$\begin{eqnarray*} (a+b)^0=\sum_{k=0}^0~{0 \choose k}a^kb^{0-k} \end{eqnarray*}$

$\begin{eqnarray*} 1=1 \end{eqnarray*}$

Induktionsvoraussetzung: Es gilt für $\begin{eqnarray*} n\in \mathbb N \end{eqnarray*}$

Induktionsschritt: $\begin{eqnarray*} n\rightarrow n+1 \end{eqnarray*}$

$\begin{eqnarray*} (a+b)^{n+1}=\sum_{k=0}^{n+1}~{n+1 \choose k}a^kb^{n+1-k} \end{eqnarray*}$

$\begin{eqnarray*} (a+b)(a+b)^n=(a+b)\sum_{k=0}^n~{n \choose k}a^kb^{n-k} \end{eqnarray*}$

Ab hier weiß ich leider nicht mehr weiter.

01.12.2007, 12:40

tmo

Auf diesen Beitrag antworten »

du solltest vielleicht beim induktionsschritt bei der summe anfangen und die umformen:
$\begin{eqnarray*} \sum_{k=0}^{n+1} \binom{n+1}{k}a^kb^{n+1-k} = \sum_{k=0}^{n+1} \left(\binom{n}{k-1}+\binom{n}{k} \right)a^kb^{n+1-k} \end{eqnarray*}$

jetzt kannst du die summe auseinanderziehen und dann bietet sich ein indexverschiebung an um letztendlich zum ziel zu gelangen. beachte dabei auch, dass a und b konstanten sind, du kannst sie also aufgrund des distributivgesetzes aus der summe rausziehen.

Anzeige

01.12.2007, 12:47

Musti

Auf diesen Beitrag antworten »

Wie meinst du das mit Summer auseinanderziehen?

Meinst du etwa: $\begin{eqnarray*} \sum_{k=0}^{n+1}~{n \choose k-1}a^kb^{n+1-k} + \sum_{k=0}^{n+1}~{n \choose k}a^kb^{n+1-k} \end{eqnarray*}$
Eine Indexverschiebung habe ich noch nie gemacht unglücklich

unglücklich

01.12.2007, 12:48

klarsoweit

Auf diesen Beitrag antworten »

RE: Vollständige Induktion

Zitat:

Original von Musti
Induktionsvoraussetzung: Es gilt für alle $\begin{eqnarray*} n=k, k+1,... \end{eqnarray*}$

Formal unsauber. Wenn es so wäre, brauchtest du den Induktionsschritt gar nicht mehr machen. Augenzwinkern

Augenzwinkern

Richtig wäre der Satz: Es gelte die Behauptung für ein beliebiges, aber festes n aus N mit n >= k.

01.12.2007, 12:49

Musti

Auf diesen Beitrag antworten »

RE: Vollständige Induktion
Danke für den Hinweis klarsoweit smile

smile

01.12.2007, 12:58

tmo

Auf diesen Beitrag antworten »

ja das meine ich.

der rechte summand hat ja jetzt schon eine sehr gute form Augenzwinkern

Augenzwinkern

ziehe noch ein b aus der summe raus und dann lautet dieser summand $\begin{eqnarray*} b(a+b)^n \end{eqnarray*}$ (natürlich nach der IV).

also musst der andere summand folglich $\begin{eqnarray*} a(a+b)^n \end{eqnarray*}$ lauten. damit hast du schonmal das ziel vor augen, was immer von vorteil ist.

die indexverschiebung führst du folgendermaßen durch:
statt bei k = 0, fängst du bei k = -1 an und gehst dafür nur bis n.
in der summe musst du dann jedes k durch k+1 ersetzen.

01.12.2007, 13:05

Musti

Auf diesen Beitrag antworten »

Mal gucken ob ich dich richtig verstanden habe:

$\begin{eqnarray*} \sum_{k=1}^{n}~{n \choose k}a^kb^{n+1-k+1} + \sum_{k=0}^{n+1}~{n \choose k}a^kb^{n-k}+\sum_{k=0}^{n+1}~{n \choose k}b \end{eqnarray*}$

Ich glaube hier ist einiges durcheinander geraten verwirrt

verwirrt

Muss ich die Indexverschiebung bei beiden Summanden durchführen?
Hab sie jetzt nur versucht beim ersten anzuwenden.

01.12.2007, 14:36

klarsoweit

Auf diesen Beitrag antworten »

Fangen wir nochmal vorne an:

$\begin{eqnarray*} \sum_{k=0}^{n+1} \binom{n+1}{k}a^kb^{n+1-k} = a^{n+1} + b^{n+1} + \sum_{k=1}^{n} \binom{n+1}{k}a^kb^{n+1-k} = a^{n+1} + b^{n+1} + \sum_{k=1}^{n} \binom{n}{k-1}a^kb^{n+1-k} + \sum_{k=1}^{n} \binom{n}{k}a^kb^{n+1-k} \end{eqnarray*}$

$\begin{eqnarray*} = a^{n+1} + \sum_{k=1}^{n} \binom{n}{k-1}a^kb^{n+1-k} + \sum_{k=0}^{n} \binom{n}{k}a^kb^{n+1-k} \end{eqnarray*}$

Bei der ersten Summe kannst du mit k=j+1 eine Indexverschiebung machen. Bei der zweiten Summe kann du einmal den Faktor b rausziehen und die Induktionsvoraussetzung anwenden.

01.12.2007, 17:31

Musti

Auf diesen Beitrag antworten »

Zitat:

Original von klarsoweit

$\begin{eqnarray*} \sum_{k=0}^{n+1} \binom{n+1}{k}a^kb^{n+1-k} = a^{n+1} + b^{n+1} + \sum_{k=1}^{n} \binom{n+1}{k}a^kb^{n+1-k} \end{eqnarray*}$

Diese erste Umformung verstehe ich nicht, nichtsdestotrotz versuche ich mal deinen Rat zu verfolgen, in der Hoffnung, dass ich diesen Schritt nochmal erläutert bekomme.

$\begin{eqnarray*} a^{n+1}\sum_{k=1}^n~{n \choose k-1}a^kb^{n+1-k}+\sum_{k=0}^n~{n \choose k}a^kb^{n+1-k} \end{eqnarray*}$
$\begin{eqnarray*} =a^{n+1}\sum_{j=0}^n~{n \choose j}a^{j+1}b^{n-j}+(a+b)^nb \end{eqnarray*}$

Bis hierhin ok?
Wie gehts weiter?

Zurück zu der ersten Umformung: Du holst aus der Summe das $\begin{eqnarray*} a^{n+1}+b^{n+1} \end{eqnarray*}$ raus und die Summe geht nur noch von $\begin{eqnarray*} k=1 \end{eqnarray*}$ bis $\begin{eqnarray*} n \end{eqnarray*}$ , aber wieso ist das so?

Mir fällt grade auf, dass es auch beim dritten Gleichheitszeichen von dir hapert.
Wohin verschwindet das $\begin{eqnarray*} b^{n+1} \end{eqnarray*}$ verwirrt

verwirrt

01.12.2007, 17:38

tmo

Auf diesen Beitrag antworten »

guck dir doch einfach mal an, wie sich die indizes verändert haben.

dann wird klar woher die anderen terme alle kommen oder wohin sie verschwinden.

01.12.2007, 17:40

klarsoweit

Auf diesen Beitrag antworten »

Zitat:

Original von Musti
Zurück zu der ersten Umformung: Du holst aus der Summe das $\begin{eqnarray*} a^{n+1}+b^{n+1} \end{eqnarray*}$ raus und die Summe geht nur noch von $\begin{eqnarray*} k=1 \end{eqnarray*}$ bis $\begin{eqnarray*} n \end{eqnarray*}$ , aber wieso ist das so?

Setz doch mal k=0 bzw. k=n+1 in die Summe ein. Welche Summanden bekommst du dann?

Zitat:

Original von Musti
$\begin{eqnarray*} a^{n+1}\sum_{k=1}^n~{n \choose k-1}a^kb^{n+1-k}+\sum_{k=0}^n~{n \choose k}a^kb^{n+1-k} \end{eqnarray*}$
$\begin{eqnarray*} =a^{n+1}\sum_{j=0}^n~{n \choose j}a^{j+1}b^{n-j}+(a+b)^nb \end{eqnarray*}$

Bei mir war ein Pluszeichen vor der ersten Summe. Ich baue das mal wieder ein:

$\begin{eqnarray*} a^{n+1} + \sum_{k=1}^n~{n \choose k-1}a^kb^{n+1-k}+\sum_{k=0}^n~{n \choose k}a^kb^{n+1-k} \end{eqnarray*}$
$\begin{eqnarray*} =a^{n+1} + \sum_{j=0}^{n-1}~{n \choose j}a^{j+1}b^{n-j}+(a+b)^nb \end{eqnarray*}$

Außerdem läuft die erste Summe durch die Indexverschiebung nur bis n-1.

Zitat:

Original von Musti
Mir fällt grade auf, dass es auch beim dritten Gleichheitszeichen von dir hapert.
Wohin verschwindet das $\begin{eqnarray*} b^{n+1} \end{eqnarray*}$ verwirrt

verwirrt

Das verschwindet wieder in der Summe. Dafür fängt die bei k=0 an. Augenzwinkern

Augenzwinkern

01.12.2007, 17:49

Musti

Auf diesen Beitrag antworten »

Zitat:

Original von klarsoweit

Zitat:

Original von Musti
Zurück zu der ersten Umformung: Du holst aus der Summe das $\begin{eqnarray*} a^{n+1}+b^{n+1} \end{eqnarray*}$ raus und die Summe geht nur noch von $\begin{eqnarray*} k=1 \end{eqnarray*}$ bis $\begin{eqnarray*} n \end{eqnarray*}$ , aber wieso ist das so?

Setz doch mal k=0 bzw. k=n+1 in die Summe ein. Welche Summanden bekommst du dann?

Genial!

Zitat:

Original von klarsoweit

Zitat:

Original von Musti
$\begin{eqnarray*} a^{n+1}\sum_{k=1}^n~{n \choose k-1}a^kb^{n+1-k}+\sum_{k=0}^n~{n \choose k}a^kb^{n+1-k} \end{eqnarray*}$
$\begin{eqnarray*} =a^{n+1}\sum_{j=0}^n~{n \choose j}a^{j+1}b^{n-j}+(a+b)^nb \end{eqnarray*}$

Bei mir war ein Pluszeichen vor der ersten Summe. Ich baue das mal wieder ein:

Hatte ich vergesse sorry Augenzwinkern

Augenzwinkern

Zitat:

Original von klarsoweit
$\begin{eqnarray*} a^{n+1} + \sum_{k=1}^n~{n \choose k-1}a^kb^{n+1-k}+\sum_{k=0}^n~{n \choose k}a^kb^{n+1-k} \end{eqnarray*}$
$\begin{eqnarray*} =a^{n+1} + \sum_{j=0}^{n-1}~{n \choose j}a^{j+1}b^{n-j}+(a+b)^nb \end{eqnarray*}$

Außerdem läuft die erste Summe durch die Indexverschiebung nur bis n-1.

Ok, das mit der Indexverschiebung mache ich wie gesagt zum ersten Mal.

Zitat:

Original von klarsoweit

Zitat:

Original von Musti
Mir fällt grade auf, dass es auch beim dritten Gleichheitszeichen von dir hapert.
Wohin verschwindet das $\begin{eqnarray*} b^{n+1} \end{eqnarray*}$ verwirrt

verwirrt

Das verschwindet wieder in der Summe. Dafür fängt die bei k=0 an. Augenzwinkern

Augenzwinkern

Wieder Genial Big Laugh

Big Laugh

Und wie geht es jetzt weiter?

Sorry, dass ich auf Anhieb nichts verstehe und dauernd nachfrage. unglücklich

unglücklich

01.12.2007, 17:54

tmo

Auf diesen Beitrag antworten »

lass das $\begin{eqnarray*} a^{n+1} \end{eqnarray*}$ auf geniale art und weise in der summe verschwinde und ziehe dann a einmal aus der summe heraus.

danach kannst du die induktionsvorraussetzung anwenden.

01.12.2007, 18:06

Musti

Auf diesen Beitrag antworten »

$\begin{eqnarray*} a^{n+1} + \sum_{j=0}^{n-1}~{n \choose j}a^{j+1}b^{n-j}+(a+b)^nb \end{eqnarray*}$
$\begin{eqnarray*} =\sum_{j=0}^{n}~{n \choose j}a^{j+1}b^{n-j}+(a+b)^nb \end{eqnarray*}$
$\begin{eqnarray*} =a\sum_{j=0}^{n}~{n \choose j}a^{j}b^{n-j}+(a+b)^nb \end{eqnarray*}$

Richtig so?
Kann ich hierdrauf jetzt die Induktionsvoraussetzung anwenden?

01.12.2007, 18:07

tmo

Auf diesen Beitrag antworten »

ja jetzt kannst du die IV anwenden.

01.12.2007, 18:11

Musti

Auf diesen Beitrag antworten »

$\begin{eqnarray*} a\sum_{j=0}^{n}~{n \choose j}a^{j}b^{n-j} +(a+b)^nb \end{eqnarray*}$ $\begin{eqnarray*} =a(a+b)^n+(a+b)^nb=(a+b)(a+b)^n=(a+b)^{n+1} \end{eqnarray*}$

Wieso ist denn:

$\begin{eqnarray*} \sum_{j=0}^{n}~{n \choose j}a^{j}b^{n-j}=(a+b)^n \end{eqnarray*}$ verwirrt

verwirrt

01.12.2007, 18:15

tmo

Auf diesen Beitrag antworten »

das ist doch gerade die induktionsvorraussetzung.

ob als laufvariable k oder j oder was auch immer benutzt wird, ist doch völlig egal.

01.12.2007, 18:17

Musti

Auf diesen Beitrag antworten »

Verstehe,

vielen dank smile

smile

1

Verwandte Themen

Die Beliebtesten »

Die Größten »

Die Neuesten »