Hi,
auf einem der Klausurabschriebe von 2001 findet sich folgende Induktionsaufgabe:
Zeige, dass für alle i >= r gilt:
Summe_von_ i=r _bis_ n ( i über r ) = ( n+1 über n-r )
Meine Lösung bisher:
I. Induktionsanfang: Beh. ist wahr für n = 1
(1 über 1) = (1+1 über 1-1)
1 = 1
II. Induktionsvorraussetzung: Beh. sei wahr für n € N.
III. Induktionsschritt: Beh. ist wahr für n + 1
Summe von i=r bis n+1 (i über r) = Summe von i=r bis n (i über r) + (n+1 über r) = (n+1 über n-r) + (n+1 über r) = (n+2 über n+1-r)
So weit so gut.. jetzt fällt mir erstmal nix mehr ein.. ausser eine Fallunterscheidung:
1. Fall: n = r
(n+1 über n-n) + (n+1 über n) = (n+2 über 1)
(n+1 über 0) + (n+1) = (n+2)
n+2 = n+2
Kommt schonmal hin..
2. Fall: n > r
Hier weiss ich nicht mehr weiter.. kann mir da jemand helfen?
Danke schonmal !
Du bist schon fertig und brauchst keine Fallunterscheidung mehr machen…
(n+2 über n+1-r) ist doch schon das Ergebnis, denn das ist
((n+1)+1 über ((n+1)-r))…
;)
hm? nein das kann nicht sein… zumindest schnall ich´s noch nicht.. die fallunterscheidung ist eh quatsch..
sagen wir mal ich bin im induktionsschritt an der stelle:
nach voraussetzung gilt:
(n+1 über n-r) + (n+1 über r) = (n+2 über n+1-r)
Wie mache ich da weiter?
Das ist doch dein Ergebnis…
Also:
Die Aufgabe war doch:
"Zeige, dass für alle i >= r gilt:
Summe_von_ i=r _bis_ n ( i über r ) = ( n+1 über n-r ) "
Und genau das hast du gezeigt..
Du häst nämlich bei
Summe von i=r bis n+1 (i über r) angefangen und bist zu (n+2 über n+1-r) gekommen.
d.h. Summe von i=r bis n+1 (i über r) = (n+2 über n+1-r)
das ist genau was gefordert war… jetzt klarer?
hm joa… vielen dank.. manchmal hab ich echt ein brett vorm kopf ;)
Hallo guiltyguy,
der Beweis ist imho keineswegs bereits fertig, denn
es wurde ja nur der Fall n=r gezeigt. Auch wenn die
Aufgabenstellung hier nicht vollständig erscheint,
dürfte wohl kaum anzunehmen sein, dass nur zu zeigen
ist, dass bloß irgendein r existiert für das die Behauptung
für alle n wahr wird. Vielmehr muss die Behauptung für
alle r gezeigt werden (und sie gilt ja auch für alle r!).
Die Behauptung muss also insbesondere noch für die Fälle
n ungleich r gezeigt werden. Die Fallunterscheidung
macht insofern keinen Sinn, denn man kann die Behauptung
für alle n >=r >= 1 durch die Addition des Binomialkoeffizienten
von n+1 über r zum Bin.koeffizienten aus der Induktionsannahme
ohne Fallunterscheidung beweisen.
Grüße
Matthias
der Beweis ist imho keineswegs bereits fertig, denn
es wurde ja nur der Fall n=r gezeigt.
Vielleicht bin ich ja auch zu sehr aus der Übung und sehe einfach nicht was du meinst, aber vor der Fallunterscheidung wurde doch garnix von n=r geschrieben. Was bis dahin gezeigt wurde ist doch also für alle r gültig, da es keine Einschränkungen gab (ausser vielleicht n >=r >= 1, was hier zwar nicht gesagt wurde, aber als gegeben vorausgesetzt werden kann denke ich mal..).
der Beweis ist imho keineswegs bereits fertig, denn
es wurde ja nur der Fall n=r gezeigt.
Vielleicht bin ich ja auch zu sehr aus der Übung und sehe einfach nicht was du meinst, aber vor der Fallunterscheidung wurde doch garnix von n=r geschrieben. Was bis dahin gezeigt wurde ist doch also für alle r gültig, da es keine Einschränkungen gab (ausser vielleicht n >=r >= 1, was hier zwar nicht gesagt wurde, aber als gegeben vorausgesetzt werden kann denke ich mal..).
Ja, genauso hätte ich auch argumentiert, man beweist es doch ganz allgemein?!
Was hier Probleme macht, ist der Induktionsanfang.
Da wird für r ebenfalls 1 eingesetzt. Eigentlich
müsste man den Induktionsanfang für n=r machen.
Für n<r ist die linke Seite der zu zeigenden
Gleichung nicht definiert und daher ist die Aufgabe
wohl nur für n>=r gemeint.
Was hier Probleme macht, ist der Induktionsanfang.
Da wird für r ebenfalls 1 eingesetzt. Eigentlich
müsste man den Induktionsanfang für n=r machen.
Für n<r ist die linke Seite der zu zeigenden
Gleichung nicht definiert und daher ist die Aufgabe
wohl nur für n>=r gemeint.
Wie gesagt, dass n >=r gelten soll, nehme ich einfach mal an, ansonsten wär "Summe_von_ i=r _bis_ n" ja auch eh leer, oder? Und aus welcher Menge r stammt wurde nicht geschrieben, aber ich schätze mal dass natürliche Zahlen gemeint sind. Und dann ist der Induktionsanfang schon richtig so.
Was mich eher wundert ist die Angabe "für alle i >= r", denn i ist doch eh nur die Variable aus der Summe.. egal [img]
http://www.fb18.de/gfx/25.gif[/img]
edit: sehe grad dass ich dir z.T. nachplapper. Lesen will gelernt sein [img]
http://www.fb18.de/gfx/22.gif[/img]
Hallo, ich zitiere nochmal die Beweisführung des ursprünglichen Fragestellers, da offenbar einige die Fallunterscheidung "überlesen" haben:
Hi,
1. Fall: n = r
(n+1 über n-n) + (n+1 über n) = (n+2 über 1)
(n+1 über 0) + (n+1) = (n+2)
n+2 = n+2
Offensichtlich ergibt sich bei dieser Umformung nur deshalb nach Induktionsannahme (n+1 über 0), weil n=r gilt (denn die 0 kommt ja von n-r = n-n = 0). Man muss jedoch n>=r annehmen, und dann lassen sich die Binomialkoeefizienten (n+1 über n-r) [was nach Induktionsannahme gilt] und (n+1 über r) [was der n+1-te Summand, also der eigentliche Induktionsschritt ist] nicht mehr durch eine so einfache "Rechenregel" erreichen. Man muss dann die B-Koeff. zunächst in einem Bruch umwandeln und schließlich wieder den B-Koeff. herleiten.
Grüße
Matthias
Ich zitiere auch gerne nochmal:
Anonymer User:
So weit so gut.. jetzt fällt mir erstmal nix mehr ein.. ausser eine Fallunterscheidung:
Guiltyguy:
Du bist schon fertig und brauchst keine Fallunterscheidung mehr machen…
Die Fallunterscheidung hat hier keiner übersehen, die Behauptung war aber schon vorher bewiesen.
Jo, aber nur für n=r. Oder könntest du mir bitte nochmal zeigen, wo sie für n > r bewiesen wurde?
Grüße
Matthias
III. Induktionsschritt: Beh. ist wahr für n + 1
Summe von i=r bis n+1 (i über r) = Summe von i=r bis n (i über r) + (n+1 über r) = (n+1 über n-r) + (n+1 über r) = (n+2 über n+1-r)
Wo wird denn hier n=r angenommen? Seh ich nicht, deshalb würde ich glatt mal behaupten dass gilt auch für r kleiner n
Wo wird denn hier n=r angenommen?
Dort wird es nirgendwo angenommen, aber da wird auch nichts bewiesen. Das ist ja gerade der noch zu zeigende Induktionsschritt. Könntest du mir bitte jetzt nochmal die Stelle quoten, wo dieser Induktionsschritt bewiesen wurde? Ich sehe sie nämlich nach wie vor nicht.
Grüße
Matthias
III. Induktionsschritt: Beh. ist wahr für n + 1
Summe von i=r bis n+1 (i über r) = Summe von i=r bis n (i über r) + (n+1 über r) = (n+1 über n-r) + (n+1 über r) = (n+2 über n+1-r)
Nochmal zur Verdeutlichung: Es gibt keine Rechenregel für Binomialkoeffizienten, nach der einfach (n+1 über n-r) + (n+1 über r) = (n+2 über n+1-r) angenommen werden kann. Es sei denn, man macht hier die zu zeigende Aussage schon zur Voraussetzung. Somit ist also der Binomialkoeffizient, der sich aus (n+1 über n-r) + (n+1 über r) ergibt, noch zu zeigen. Ansonsten argumentiert man etwa nach dem Motto "Wir zeigen, dass 1+1=2 ist. Laut Addition ist 1+1=2. Also ist 1+1=2." Das ist in etwa die logische Struktur der bisherigen Beweisführung.
Grüße
Matthias
Es gibt keine Rechenregel für Binomialkoeffizienten, nach der einfach (n+1 über n-r) + (n+1 über r) = (n+2 über n+1-r) angenommen werden kann.
(n+1 über n-r) + (n+1 über r)
= (n+1 über (n+1)-1-r) + (n+1 über r)
= (n+1 über (n+1)-1-r) + (n+1 über (n+1)-r)
= (n+2 über (n+1)-r)
1. Gleichung Umformung
2. Gleichung nach der Regel (n über k) = (n über n-k) , bei meinem alten Skript S.46
3. Gleichung nach der Regel (n über k) = (n-1 über k) + (n-1 über k-1) , bei mir auf S. 43
Mit ein paar Regeln bekommt man das also schon hin, sollte man natürlich auch hinschreiben, stimmt schon [img]
http://www.fb18.de/gfx/22.gif[/img]
So kann man's stehen lassen ;-).
Eine andere Möglichkeit wäre die Umformung über die Formel (n über k) n!/((n-k)! k!), die aber vermutlich ein wenig mehr Arbeit macht.
Viele Grüße
Matthias
