Mathe Umformungen, Vollständige Induktion?
Hat jemand ne Idee wie ich hier weiter machen könnte?
2 Antworten
Hallo,
den Index nur noch von 0 bis n laufen zu lassen und stattdessen das letzte Summenglied n+2 zu dieser Summe zu addieren, war richtig.
Ebenso richtig war es, die Identität (n+1) über k=(n über k)+(n über k-1) anzuwenden.
Dann aber hast Du Dich überhaupt nicht mehr um die rechte Seite der Gleichung gekümmert; das war Dein Fehler.
Wenn Du auf beiden Seiten SUMME (k=0 bis k=n): [(k+1)*(n über k)] abziehst, die ja laut Induktionsvoraussetzung das Gleiche ist wie (n+2)*2^(n-1), bekommst Du
SUMME (k=0 bis k=n): [(k+1)*(n über (k-1)+(n+2)]=(n+3)*2^n-(n+2)*2^(n-1).
Addition auf beiden Seiten von (n+2)*2^(n-1)=
SUMME (k=0 bis k=n): [(k+1)*(n über k)] ergibt
SUMME (k=0 bis k=n): [(k+1)*(n über (k-1)+(k+1)*(n über k)+(n+2)]=(n+3)*2^n
Wenn Du jetzt den Index der Summe wieder bis n+1 laufen läßt, verschwindet links der Term (n+2) und die Induktionsbehauptung bleibt übrig.
Herzliche Grüße,
Willy
Hab ich schon gemerkt, daß meine Beweisführung etwas fadenscheinig war.
Blöderweise ist mir aber noch nichts Gescheites eingefallen.
Vielleicht könnte man noch mit der Identität SUMME (k=0 bis k=n): (n über k)=2^n etwas anfangen.
Außerdem gilt: SUMME (k=0 bis k=n+1): ((n+1) über k)=2*SUMME (k=0 bis k=n): (n über k)
Ich habe die Lösung mittlerweile, aber sie ist mir nicht so ganz schlüssig...
https://www.minpic.de/i/9hke/41jiv
1) Warum fängt man bei k=1 an?
2) Wo ist die 1 ab der 3. Zeile hin?
4) Wie kommt von der Summe in Zeile 3 auf die in Zeile 4???
Aber deine Vermutung mit 2^n war richtig :)
Und vor allem, wie soll man denn darauf kommen...
Das mit der 1 kann ich erklären.
(n+1 über k)*(k+1) multipliziert die Binomialkoeffizienten einer Reihe des Pascalschen Dreiecks nacheinander mit den Faktoren 1, 2, 3 usw.
Fängst Du erst bei k=1 an, fehlt Dir das erste Glied in der Reihe.
n über 0 ist bekanntlich 1 und 0+1 ist auch 1.
Das erste Glied in der Kette ist also immer 1.
Läßt Du sie in der Summe weg, mußt Du sie als Ausgleich addieren.
So kommt die 1 vor das Summenzeichen.
Das mit dem n+2 hast Du ja selbst herausgefunden.
Der eigentliche Trick besteht in der Indexverschiebung von 1 bis n zu 0 bis n-1 und der Ersetzung von k durch l.
Darauf wäre ich nicht gekommen.
Zeile 4&5:
Die Summe von k=0 bis n ((k+1)*(n über k-1) existiert nicht. Der erste Summand wäre ja 1*(n über - 1) und n über - 1 ist nicht definiert.
n über -1 ist definiert, wenn man über die Gammafunktion geht. Dann ist n über k immer 0, wenn k eine negative ganze Zahl ist.
Wenn man jedoch über die Erstsemester-Definition (n über k)=n! / (k! * (n-k)!) geht, ist das natürlich kein Argument. Durch deine Antwort sieht man ganz schön, dass die "Zerlegung" des Binomialkoeffizienten (n über k) = (n-1 über k) + (n-1 über k-1) nur funktioniert, wenn k größer als 1 ist.
Dann müsste ich halt den Fall k = 0 aus der Summe ziehen, aber dann komm ich trotzdem nicht weiter :(
Du meinst ,,ist das natürlich ein Argument", oder? Und ich glaube kaum, dass man es bei dieser vollständigen Induktion irgendwie mit der Gamma-Fkt zu tun bekommt, daher habe ich die ,,Erstsemester-Definition", ein etwas abwertender Begriff, benutzt.
Mit "das" meinte ich die Definition über die Gamma-Funktion, nicht deinen Post. Und ja, es kommt doch etwas abwertend rüber, aber das war keineswegs so gemeint.
Ah alles klar :) Und ich meinte, dass du geschrieben hast, dass das KEIN Argument sei, aber wahrscheinlich meinst du, dass das EIN Argument sei.
Diese Funktion brauchst Du gar nicht, weil im Laufe des Beweise (n über (k-1)) wieder verschwindet, ohne jemals tatsächlich berechnet worden zu sein.
Da dieser Binomialkoeffizient ja definiert ist, eigentlich nicht. Es handelt sich ja nicht um etwas wie eine Division durch Null. Wäre halt nur nicht einfach zu berechnen, wenn man es müßte.
Ich fürchte nur, daß der Beweis in meiner Antwort auch nichts taugt, weil ich die Behauptung zwar benutzt habe (darf ich), aber nicht wirklich bewiesen (muß ich aber).
a=b zu beweisen, indem man zeigt, daß a+c=b+c, ist etwas windig.
Stimmt, aber die rechte Seite darf ich nicht verwenden. Mein Prof streicht das sonst alles durch weil "Falsche Beweisrichtung" ...
Ich muss also die linke Seite in die Rechte umformen :(