Induktion Binomialkoeffiziente < Aussagenlogik < Logik < Logik+Mengenlehre < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 07:31 Mo 28.11.2011 | | Autor: | Rip |
| Aufgabe | Aufgabe 2: Binomialkoeffizienten
Benutzen Sie die grundlegenden Identitäten
[mm] \vektor{n + 1 \\ m} [/mm] = [mm] \vektor{n \\ m}+ \vektor{n \\ m - 1}
[/mm]
und
[mm] \summe_{i=0}^{n} \vektor{n \\ i} [/mm] = [mm] 2^{n}
[/mm]
um per Induktion für alle natürlichen Zahlen n >= 1 zu beweisen:
[mm] \summe_{k=1}^{n} k*\vektor{n \\ k} [/mm] = [mm] n*2^{n-1} [/mm] |
Hi,
Ich weiß nicht womit ich anfangen soll. ich zerbrech mir schon die ganze nacht den kopf darüber, aber irgendwie ist der Wurm drin.
Ich habe diese Frage in keinem Forum auf anderen Internetseiten gestellt
EDIT:
Ich hab mir erstmal eine Induktionsvoraussetzung gezogen:
[mm] \summe_{k=1}^{n} k*\vektor{n \\ k}=n*2^{n-1}
[/mm]
danach einen Induktionsanfang:
mit n = 1
[mm] \summe_{k=1}^{1} 1*\vektor{1 \\ 1}=1*2^{1-1}
[/mm]
[mm] \gdw 1*\vektor{1! \\ \overline{(1!*(1-1)!)}}=1*2^{1-1}
[/mm]
[mm] \gdw [/mm] 1 = 1
ich komme aber nicht beim Induktionsschritt weiter... -.-
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 07:46 Mo 28.11.2011 | | Autor: | fred97 |
> Aufgabe 2: Binomialkoeffizienten
> Benutzen Sie die grundlegenden Identitäten
> [mm]\vektor{n + 1 \\ m}[/mm] = [mm]\vektor{n \\ m} \vektor{n \\ m - 1}[/mm]
Das stimmt doch nicht. Richtig:
$ [mm] \vektor{n + 1 \\ m} [/mm] $ = $ [mm] \vektor{n \\ m}+ \vektor{n \\ m - 1} [/mm] $
>
> und
> [mm]\summe_{i=0}^{n} \vektor{n \\ i}[/mm] = [mm]2^{n}[/mm]
> um per Induktion für alle natürlichen Zahlen n >= 1 zu
> beweisen:
> [mm]\summe_{k=1}^{n} k*\vektor{n \\ k}[/mm] = [mm]n*2^{n-1}[/mm]
>
> Hi,
> Ich weiß nicht womit ich anfangen soll. ich zerbrech mir
> schon die ganze nacht den kopf darüber, aber irgendwie ist
> der Wurm drin.
Mache einen üblichen Induktionsbeweis , aber mit der richtigen Formel
$ [mm] \vektor{n + 1 \\ m} [/mm] $ = $ [mm] \vektor{n \\ m}+ \vektor{n \\ m - 1} [/mm] $
FRED
>
> Ich habe diese Frage in keinem Forum auf anderen
> Internetseiten gestellt
>
>
> EDIT:
> Ich hab mir erstmal eine Induktionsvoraussetzung gezogen:
> [mm]\summe_{k=1}^{n} k*\vektor{n \\ k}=n*2^{n-1}[/mm]
>
> danach einen Induktionsanfang:
> mit n = 1
> [mm]\summe_{k=1}^{1} 1*\vektor{1 \\ 1}=1*2^{1-1}[/mm]
> [mm]\gdw 1*\vektor{1! \\ \overline{(1!*(1-1)!)}}=1*2^{1-1}[/mm]
>
> [mm]\gdw[/mm] 1 = 1
>
>
> ich komme aber nicht beim Induktionsschritt weiter... -.-
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 07:54 Mo 28.11.2011 | | Autor: | Rip |
ah, entschuldige, natürlich stimmt die formel von dir. hab nur das + vergessen... danke!
stimmen meine ansätze mit der Induktionsvoraussetzung und dem Anfang?
wie bring ich denn die grundlegenden Identitäten in den Indutkionsschritt ein? ich versteh nicht ganz, wie ich die Formel unterbringen soll. ich habe es schon versucht, aber jedes mal wenn ich dann so nachrechne, stimmt das ergebnis nicht und ich hab nen widerspruch. das ist ja nicht sinn und zweck der sache^^
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 08:31 Mo 28.11.2011 | | Autor: | Rip |
Aber wie beziehe ich die Formel ein?
Das wäre mein Lösungsanatz:
[mm] \summe_{k=1}^{n+1} k\vektor{n \\ k} [/mm] = [mm] \summe_{k=1}^{n} k\vektor{n\\ k-1}+\vektor{n\\ k}
[/mm]
|
|
|
| |
|
Hallo Rip, ![[willkommenmr]](/images/smileys/willkommenmr.png "[willkommenmr]")
> Aber wie beziehe ich die Formel ein?
> Das wäre mein Lösungsanatz:
>
> [mm]\summe_{k=1}^{n+1} k\vektor{n \\
k}[/mm] = [mm]\summe_{k=1}^{n} k\vektor{n\\
k-1}+\vektor{n\\
k}[/mm]
Das stimmt doch gar nicht!
Die Induktionsvoraussetzung sollte für n gelten, im Induktionsschritt willst Du dann zeigen, dass sie auch für n+1 gilt.
Zu zeigen ist also:
[mm] \summe_{k=1}^{n+1}k\vektor{\blue{n+1}\\k}=(n+1)*2^n
[/mm]
Das sollst Du nun unter Anwendung elementarer Umformungen und Identitäten auf die Induktionsvoraussetzung zurückführen. Das fängt so an:
[mm] \summe_{k=1}^{n+1}k\vektor{n+1\\k}=(n+1)\vektor{n+1\\n+1}+\summe_{k=1}^{n}k\left(\vektor{n\\k}+\vektor{n\\k-1}\right)=n+1+\left(\summe_{k=1}^{n}k\vektor{n\\k}\right)+\left(\summe_{k=1}^{n}k\vektor{n\\k-1}\right)=\cdots
[/mm]
Das letzte Summationsglied musste ich herauslösen, um die Summen nur noch bis n laufen zu lassen. Von den beiden nun verbliebenen Summen ist die eine aus der Induktionsvoraussetzung bekannt, und die andere bedarf noch einer Umformung und einer Indexverschiebung, damit sie ebenfalls auf die Induktionsvoraussetzung zurückgeführt werden kann.
Dann wird auch die zweite in der Aufgabe gegebene Identität benutzt werden müssen.
Mach Du mal ab hier weiter, und wenns hakt, dann melde Dich wieder und rechne vor, wie weit Du gekommen bist.
Grüße
reverend
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 12:10 Mo 28.11.2011 | | Autor: | Rip |
hi, danke schon mal für die antwort,
irgendwie kam das so nicht in meinen vorlesungen vor, hab von dieser schreibweise noch nie was gesehen^^ außer beim googlen, aber da habe ich es auch schon nicht verstanden!
[mm] n+1+n*2^{n-1}+(\summe_{k=1}^{n} k\vektor{n \\ k-1})
[/mm]
so hab ich es jetzt weiter vereinfacht,
aber wie soll ich denn von der letzten summe auf meine induktionsvoraussetzung kommen?
|
|
|
| |
|
Hallo Rip,
> hi, danke schon mal für die antwort,
> irgendwie kam das so nicht in meinen vorlesungen vor, hab
> von dieser schreibweise noch nie was gesehen^^ außer beim
> googlen, aber da habe ich es auch schon nicht verstanden!
Hm. Dann ist so eine Aufgabe fast nicht zu schaffen, und auch das folgende wird Dir wahrscheinlich nicht einleuchten. Schau Dir mal andere Beispiele der Summenschreibweise an, die ja eine Abkürzung ist. Dabei wird unter der Summe die Summationsvariable festgelegt, mit der dann "in" der Summe gearbeitet wird. Sie hat - wie in einem Software-Unterprogramm - nur lokale Bedeutung, kann also in der nächsten Summe wieder neu und unabhängig von einer vorherigen Verwendung festgelegt werden. Deswegen darf allerdings die Summationsvariable keine Bezeichnung tragen, die sonst einen festen Wert in der Rechnung haben soll.
Außer dieser Variablen werden auch ihr Anfangs- und Endwert mit angegeben (unter und über der Summe). Die Summationsvariable "läuft" in Einerschritten vom einen zum andern Wert.
Dabei muss man sich recht genau überlegen, was da eigentlich summiert wird. So ist nicht sofort offensichtlich, dass
[mm] \summe_{k=1}^{10}k=\summe_{i=0}^{9}(i+1)=55
[/mm]
Hier ist eine sog. Indexverschiebung geschehen. Dabei ist ganz unerheblich, dass die Summationsvariable ihren Namen gewechselt hat. Bedeutend ist aber, dass Anfangs- und Endwert sich geändert haben, wodurch die Summe eine andere wird. Zugleich ist aber der Summationsterm auch verändert worden, so dass nach wie vor hier einfach die Zahlen von 1 bis 10 summiert werden, auch wenn i dabei von 0 bis 9 läuft.
Genau so etwas kommt nun in Deiner Aufgabe vor.
> [mm]n+1+n*2^{n-1}+(\summe_{k=1}^{n} k\vektor{n \\
k-1})[/mm]
> so hab
> ich es jetzt weiter vereinfacht,
Ja, ok so. ![[ok]](/images/smileys/ok.gif "[ok]")
> aber wie soll ich denn von der letzten summe auf meine
> induktionsvoraussetzung kommen?
Ich bearbeite mal nur die Summe und lasse die Terme davor mal weg. Die müssen am Ende aber natürlich wieder mit dazu bzw. die ganze Zeit mit durchgeschleift werden.
[mm] \summe_{k=1}^{n}k\vektor{n\\k-1}=\summe_{k=0}^{n-1}(k+1)\vektor{n\\k}=1*\vektor{n\\0}-(n+1)*\vektor{n\\n}+\summe_{k=1}^{n}(k+1)\vektor{n\\k}=1-n-1+\summe_{k=1}^{n}k\vektor{n\\k}+\summe_{k=1}^{n}\vektor{n\\k}=\cdots
[/mm]
edit: Sorry, da hatte sich vorhin ein Fehler eingemogelt! Ich hoffe, jetzt stimmts...
Das sind schon einmal ein paar Schritte, die Du erstmal nachvollziehen musst. Über das erste Gleichheitszeichen hinweg geschieht eine Indexverschiebung, die gleiche Summe wird also nur anders geschrieben. Dann wird die eigentliche Summe verschoben; dazu muss der erste Summand herausgelöst werden, nämlich [mm] 1*\vektor{n\\0}, [/mm] und da die Summe nun noch einen neuen Summanden enthält, muss dieser vorab noch subtrahiert werden, nämlich [mm] (n+1)*\vektor{n\\n}. [/mm] Und zum Schluss wird der Summationsterm per Distributivgesetz ausmultipliziert und die Summe so in zwei Summen aufgeteilt.
Von hier ist es nun nur noch ein kleiner Schritt. Wende die in der Aufgabenstellung gegebenen Identitäten an - und vergiss die beiden Terme nicht, die ich hier aus Bequemlichkeit weggelassen habe, s.o.
Grüße
reverend
|
|
|
|
