Beweis durch Induktion < Induktion < eindimensional < reell < Analysis < Hochschule < Mathe < Vorhilfe
|
| Aufgabe | Zeigen Sie mit vollständiger Induktion:
[mm] \summe_{k=1}^{n}\vektor{n \\ k}*k=2^{n-1}*n [/mm] |
Hallo an die Community!
Ich habe soeben mein Mathematikstudium begonnen und das Niveau, welches doch beträchtlich ist, belebt so richtig den Geist.
Diese Aufgabe stellt ein Problem dar, da gleich zwei werte k und n variabel sind.
Die Verankerung lautet:
Für n=1
[mm] \vektor{1 \\ 1}*1=1 [/mm] und [mm] 2^{1-1}*1=1
[/mm]
Der Induktionsschritt: Wir nehmen an, dass die behauptung für n stimmt und müssen zeigen, dass sie für n+1 auch wahr ist.
[mm] \summe_{k=1}^{n+1}\vektor{n+1 \\ k}*k=2^{n}*(n+1).
[/mm]
Weiter komme ich nicht. Ich weiss nicht wie ich die Differenz von (n+1) und n beschreiben soll. (Ich nehme an, dass es sich hier auch um eine Summe handelt).
Wie auch immer, ich hoffe auf ein paar frische Ideen eurerseits. Bitte keine vollständigen Lösungen sondern nur Tipps, Bemerkungen, die anspornen. Mathe bedeutet probieren.
Vielen Dank im Voraus.
GorkyPark
Ich habe diese Frage auf keiner anderen Internetseite gestellt.
|
|
| |
|
| Status: |
(Antwort) fehlerhaft  | | Datum: | 16:49 Do 26.10.2006 | | Autor: | Sashman |
Moin GorkyPark!
> Ich habe soeben mein Mathematikstudium begonnen und das
> Niveau, welches doch beträchtlich ist, belebt so richtig
> den Geist.
 stimmt
> Diese Aufgabe stellt ein Problem dar, da gleich zwei werte
> k und n variabel sind.
nur n ist variabel. k ist die Laufvariable für die du bei jedem Summanden was einzusetzen hast. Dazu ein Beispiel:
Die Summe der ersten $n$ natürlichen Zahlen:
[mm] \sum_{k=1}^{n}k=1+2+3+4+5+\dots [/mm] +n oder verkürzen wir das ganze nochmals:
[mm] \sum_{k=1}^{1}k=1
[/mm]
[mm] \sum_{k=1}^{2}k=1+2
[/mm]
[mm] \sum_{k=1}^{3}k=1+2+3 [/mm] oder anders geschrieben
[mm] \sum_{k=1}^{3}k=\sum_{k=1}^{2}k+3=1+2+3
[/mm]
also du fängst beim Startwert an (k=1) und setzt diesen in den Summanden für k ein, danach ein Plus gesetzt und k um einserhöt nächster Summand - solange, bis der Endwert (oben auf dem Summenzeichen) erreicht wird.
> Die Verankerung lautet:
>
> Für n=1
>
> [mm]\vektor{1 \\ 1}*1=1[/mm] und [mm]2^{1-1}*1=1[/mm]
>
> Der Induktionsschritt: Wir nehmen an, dass die behauptung
> für n stimmt und müssen zeigen, dass sie für n+1 auch wahr
> ist.
>
>
> [mm]\summe_{k=1}^{n+1}\vektor{n+1 \\ k}*k=2^{n}*(n+1).[/mm]
>
> Weiter komme ich nicht. Ich weiss nicht wie ich die
> Differenz von (n+1) und n beschreiben soll. (Ich nehme an,
> dass es sich hier auch um eine Summe handelt).
Von dort kannst du auch nicht weiterkommen, da das was du dort hingeschrieben hast gerade das ist was du zeigen mußt fast jedenfalls.
Zum Vergleich siehe unten. SIEHE DORT
Bei der Induktionsvoraussetzung ( und es meist günstig sich die irgendwo zu notieren) nehmen wir an, das unsere Aussage für ein beliebiges aber fest bestimmtes n (die Verankerung sichert das es wenigstens ein solches n gibt) wahr ist.
also [mm] \sum_{k=1}^{n}\vektor{n\\k}*k=2^{n-1}*n [/mm] ist eine wahre Aussage
Im Beweis hast du dann zu zeigen das dann auch ( unter Anwendung der Induktionsvoraussetzung) die Aussage für $n+1$ wahr ist.
Sogesehen hangelst du dich dann vom Startwert 1 (Verankerung) durch die natürlichen Zahlen und hast mit einem Schlag die Aussage für alle natürlichen Zahlen gezeigt oder auch das es nicht für alle gilt - je nach Ausgang deines Beweises.
nun zu deiner Aufgabe zurück SIEHE HIER
zu zeigen:
[mm] \sum_{k=1}^{n+1}\vektor{n\\k}*k=2^n*(n+1)
[/mm]
wie im Beispiel mit den natürlichen Zahlen schreiben wir:
[mm] \sum^n+(n+1)ter [/mm] Summand = [mm] \sum^{n+1} [/mm] also
[mm] \sum_{k=1}^{n+1}\vektor{n\\k}k=\sum_{k=1}^{n}\vektor{n\\k}*k+\vektor{n\\n+1}*(n+1)
[/mm]
An dieser Stelle sind wir froh das wir die Voraussetzung haben, weil wir können sie einsetzen.
[mm] \sum_{k=1}^{n+1}\vektor{n\\k}k=\sum_{k=1}^{n}\vektor{n\\k}*k+\vektor{n\\n+1}*(n+1)\stackrel{IV}{=}2^{n-1}*n+\vektor{n\\n+1}*(n+1)=\dots
[/mm]
die Gleichungskette mußt du nun durch geeignete Maßnahmen derart bearbeiten das am Ende [mm] =2^n*(n+1) [/mm] dasteht und du bist fertig.
mfG
Sashman
|
|
|
| |
|
Hey!
Vielen Dank für die schnelle und überaus lehrreiche Antwort. Das Prinzip der vollständigen Induktion ist mir jetzt klar. Ich hab jetzt eine Stunde versucht die Aufgabe zu lösen und es klappt leider noch nicht.
> Moin GorkyPark!
>
> > Ich habe soeben mein Mathematikstudium begonnen und das
> > Niveau, welches doch beträchtlich ist, belebt so richtig
> > den Geist.
>
> stimmt
>
> > Diese Aufgabe stellt ein Problem dar, da gleich zwei werte
> > k und n variabel sind.
>
> nur n ist variabel. k ist die Laufvariable für die du bei
> jedem Summanden was einzusetzen hast. Dazu ein Beispiel:
>
> Die Summe der ersten [mm]n[/mm] natürlichen Zahlen:
>
> [mm]\sum_{k=1}^{n}k=1+2+3+4+5+\dots[/mm] +n oder verkürzen wir das
> ganze nochmals:
>
> [mm]\sum_{k=1}^{1}k=1[/mm]
> [mm]\sum_{k=1}^{2}k=1+2[/mm]
> [mm]\sum_{k=1}^{3}k=1+2+3[/mm] oder anders geschrieben
> [mm]\sum_{k=1}^{3}k=\sum_{k=1}^{2}k+3=1+2+3[/mm]
>
> also du fängst beim Startwert an (k=1) und setzt diesen in
> den Summanden für k ein, danach ein Plus gesetzt und k um
> einserhöt nächster Summand - solange, bis der Endwert (oben
> auf dem Summenzeichen) erreicht wird.
>
> > Die Verankerung lautet:
> >
> > Für n=1
> >
> > [mm]\vektor{1 \\ 1}*1=1[/mm] und [mm]2^{1-1}*1=1[/mm]
> >
> > Der Induktionsschritt: Wir nehmen an, dass die behauptung
> > für n stimmt und müssen zeigen, dass sie für n+1 auch wahr
> > ist.
> >
> >
> > [mm]\summe_{k=1}^{n+1}\vektor{n+1 \\ k}*k=2^{n}*(n+1).[/mm]
> >
> > Weiter komme ich nicht. Ich weiss nicht wie ich die
> > Differenz von (n+1) und n beschreiben soll. (Ich nehme an,
> > dass es sich hier auch um eine Summe handelt).
>
> Von dort kannst du auch nicht weiterkommen, da das was du
> dort hingeschrieben hast gerade das ist was du zeigen mußt
> fast jedenfalls.
> Zum Vergleich siehe unten. SIEHE DORT
>
> Bei der Induktionsvoraussetzung ( und es meist günstig sich
> die irgendwo zu notieren) nehmen wir an, das unsere Aussage
> für ein beliebiges aber fest bestimmtes n (die Verankerung
> sichert das es wenigstens ein solches n gibt) wahr ist.
>
> also [mm]\sum_{k=1}^{n}\vektor{n\\k}*k=2^{n-1}*n[/mm] ist eine wahre
> Aussage
>
> Im Beweis hast du dann zu zeigen das dann auch ( unter
> Anwendung der Induktionsvoraussetzung) die Aussage für [mm]n+1[/mm]
> wahr ist.
>
> Sogesehen hangelst du dich dann vom Startwert 1
> (Verankerung) durch die natürlichen Zahlen und hast mit
> einem Schlag die Aussage für alle natürlichen Zahlen
> gezeigt oder auch das es nicht für alle gilt - je nach
> Ausgang deines Beweises.
>
>
> nun zu deiner Aufgabe zurück SIEHE HIER
>
> zu zeigen:
>
> [mm]\sum_{k=1}^{n+1}\vektor{n\\k}*k=2^n*(n+1)[/mm]
>
> wie im Beispiel mit den natürlichen Zahlen schreiben wir:
>
> [mm]\sum^n+(n+1)ter[/mm] Summand = [mm]\sum^{n+1}[/mm] also
>
> [mm]\sum_{k=1}^{n+1}\vektor{n\\k}k=\sum_{k=1}^{n}\vektor{n\\k}*k+\vektor{n\\n+1}*(n+1)[/mm]
Hier habe ich Mühe. Man ersetzt jedes k durch (n+1) ??? Warum?
>
> An dieser Stelle sind wir froh das wir die Voraussetzung
> haben, weil wir können sie einsetzen.
>
> [mm]\sum_{k=1}^{n+1}\vektor{n\\k}k=\sum_{k=1}^{n}\vektor{n\\k}*k+\vektor{n\\n+1}*(n+1)\stackrel{IV}{=}2^{n-1}*n+\vektor{n\\n+1}*(n+1)=\dots[/mm]
>
> die Gleichungskette mußt du nun durch geeignete Maßnahmen
> derart bearbeiten das am Ende [mm] 2^n*(n+1) [/mm] dasteht und du
> bist fertig.
>
Ich hab's versucht:
also: [mm] 2^{n-1}*n+\vektor{n\\n+1}*(n+1)=2^n*(n+1)
[/mm]
[mm] \vektor{n \\ n+1}, [/mm] ergibt aber ein Problem. Mein taschenrechner zeigt an, dass es kein Resultat gibt.
Ich hab dann im Lehrbuch nachgeschaut. da steht das für n<k, [mm] \vektor{n \\ k}=0 [/mm] ergibt.
Falls ich das aber in die vorige Gleichung bekomme ich eine falsche Lösung:
[mm] 2^{n-1}*n+\vektor{n\\n+1}*(n+1)=2^n*(n+1)
[/mm]
[mm] 2^{n-1}*n+0*(n+1)=2^n*(n+1)
[/mm]
[mm] 2^{n-1}*n=2^n*(n+1)\ldots
[/mm]
Wo ist da der Fehler? oder muss ich anders umformen? Eine Hilfestellung, bitte.
Gorky
> mfG
> Sashman
>
|
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 16:44 Fr 27.10.2006 | | Autor: | Sashman |
Moin nochmal!
Bin jetzt durch den Beweis durch. Der Gonozal hat mit seinem Hinweis recht und hat den Fehler markiert bevor ich meine Ausführungen berichtigen konnte. Nun gut
Also zu zeigen ist:
[mm] \sum_{k=1}^{n+1}\vektor{n+1\\k}*k=2^n*(n+1)
[/mm]
mein Fehler. Darum schnell ein Hinweis damit du die verlorene Zeit wieder aufholst.
[mm] \sum_{k=1}^{n+1}\vektor{n+1\\k}*k=\sum_{k=1}^{n+1}(\vektor{n\\k-1}+\vektor{n\\k})*k=\sum_{k=1}^{n+1}\vektor{n\\k-1}*k+\sum_{k=1}^{n+1}\vektor{n\\k}*k=\sum_{k=1}^{n+1}\vektor{n\\k-1}k+\sum_{k=1}^{n}\vektor{n\\k}*k=
[/mm]
[mm] =\sum_{k=0}^{n}\vektor{n\\k}*(k+1)+\sum_{k=1}^{n}\vektor{n\\k}*k=\sum_{k=0}^{n}\vektor{n\\k}+\sum_{k=1}^{n}\vektor{n\\k}*k+\sum_{k=1}^{n}\vektor{n\\k}*k=...
[/mm]
von hier aus sollte es mit Induktionsvoraussetzung und [mm] \sum_{k=0}^n\vektor{n\\k}=2^n [/mm] ein Kinderspiel sein.
MfG
Sashman
|
|
|
| |
|
| Status: |
(Korrektur) Korrekturmitteilung  | | Datum: | 16:23 Fr 27.10.2006 | | Autor: | Gonozal_IX |
Hiho,
wenn du den Schritt von n auf n+1 betrachtest, musst du natürlich auch alle n's auf n+1 setzen, d.h. du musst die Summe
[mm]\sum_{k=1}^{n+1}\vektor{n+1\\k}k[/mm]
betrachten.
D.h. du kannst nicht mal eben so die Induktionsvoraussetzung nehmen und die Einsetzen, denn es gilt:
[mm]\sum_{k=1}^{n+1}\vektor{n+1\\k}k = \sum_{k=1}^{n}\vektor{n+1\\k}k + \vektor{n+1\\n+1}(n+1)[/mm]
....
|
|
|
|
