Binomialkoeffizient immer eine Natürliche Zahl BEWEIS

Neue Frage »

anderson94 Auf diesen Beitrag antworten »
Binomialkoeffizient immer eine Natürliche Zahl BEWEIS
Meine Frage:
Sehr geehrtes Forum,

War heute den ganzen Tag an meinem wöchentlichen Analysis Üblatt und konnte bis auf eine Teilaufgabe alles lösen. Diese Aufgabe zerbricht mir immer noch den Kopf (ja genau am Sonntag Morgen um 1 uhr Big Laugh DD) obwohl sie nicht so besonders scheint.

Sei n {0}. Zeigen sie:

Für alle k {0,......n} gilt

,

wobei den Binomialkoeffizient "n über k" bezeichne.
Hinweis: Beweisen Sie dafür zunächst die Identität



Meine Ideen:
Die Identität habe ich zunächst mal bewiesen.

Als nächstes war ich mir bei der vollständigen Induktion nicht ganz sicher ob ich nach n oder k gehen soll. Ich habe mal k angenommen.

IA: k=0 => n über 0 ist als 1 definiert somit in den natürlichen Zahlen.

IV: ,

IS: k=>k+1 :=

So nun habe ich meine Identität und meine Induktionsvoraussetzung (IV)

Wenn ich meine Identität umforme bekomme ich ja


Durch meine IV setze ich ja vorraus dass n über k in den natürlichen Zahlen ist. aber was mache ich mit dem ? wenn ich sagen kann dass größergleich hätte ich ja eine Subtraktion zweier natürlichen Zahlen wobei die eine größer ist, oder bin ich komplett auf dem Holzweg? Sollte ich lieber die Induktion über n machen? jedoch hat dann die Identität nicht wirklich eine bedeutung für mich...
Vielleicht ist mein Kopf einfach schon so zuuu dass ich nichts mehr erkenne da ich wirklich lange an dieser Nummer sitze... würde um jede hilfe dankbar sein.

lg
HAL 9000 Auf diesen Beitrag antworten »

Die Lösung aus dem Dilemma ist denkbar einfach: Was du durch Vollständige Induktion über nachweist, ist die Aussage

Zitat:
: Der Binomialkoeffizient ist eine natürliche Zahl für alle (!) .

D.h., nicht nur für ein bestimmtes, festes , sondern wirklich für alle . Dieses "für alle ..." ist einerseits mehr Arbeit im Induktionsschritt, aber du darfst andererseits auch mehr Information in der Induktionsvoraussetzung nutzen. Augenzwinkern

Induktionsanfang ist , d.h., der Nachweis von . Im Induktionsschritt ist dann nachzuweisen, wobei du benutzen darfst.


Vorbereitend noch eine Nachfrage: Du sagst, du hast Identität nachgewiesen, aber für welche ? Vermutlich nicht für alle , sondern nur für , oder? (Was anderes gibt die Definition ja auch gar nicht her. Augenzwinkern ) Auch das ist im Induktionsschritt zu berücksichtigen, d.h., am "Rand" ist da noch was zu tun.
[email protected] Auf diesen Beitrag antworten »

Also Doch über n mhmm na dann gehen wir die Sache mal an ! Freude

Natürlich gilt die Identität nur für k < n Lehrer

IA: n=0 bei n= 0 muss ja k auch gleich 0 sein somit somit fertig.

IV:

IS: n->n+1 somit ist zu zeigen

hier steige ich wieder aus. wie hilft mir die Identität weiter?

laut IV ist heist das dass Laut IV auch ist ? und somit die Subtraktion mir eine natürliche Zahl liefert? Aber die natürlichen Zahlen sind ja bezüglich der subtraktion nicht abgeschlossen wer garantiert mir dann dass größer als ? oder denke ich gerade komplett dumm verwirrt .

Nun noch zum Rand, es gilt ja nur für k<n aber in der Angabe steht ja {0,....,n}
somit kann auch k=n sein.
ist ja 1 und für die Identität gilt dann 1+0=1

da ja im zweiten Summanden n über n+1 steht was ja 0 ist.

War mein Induktionsschritt richtig? würde mich wieder um ein paar Infos sehr freuen.

lg
anderson94 Auf diesen Beitrag antworten »

PS der Post von rexa05... ist von mir Hammer habs nur mit der Anmeldung verkackt ... Big Laugh
HAL 9000 Auf diesen Beitrag antworten »

Du musst gründlicher arbeiten:

Der Nachweis von im Induktionsschritt erfordert, dass du für alle nachweisen musst.

Nun weißt du nach der Vorbetrachtung (Achtung: Indexverschiebung!), dass für alle gilt. Gemäß Induktionsvoraussetzung darfst du nun benutzen, dass sowohl als auch gilt. Da die Summe zweier natürlicher Zahlen wieder eine natürliche Zahl ist, bist du damit für diese fertig.

Es fehlen aber noch die beiden Randwerte und , für die musst du noch in einer Extrabetrachtung zeigen, dass auch da gilt. Das kann aber so schwer nicht sein, das geht direkt per Definition des Binomialkoeffizienten.


P.S.: Salopp könnte man das Beweisprinzip so zusammenfassen: Wir betrachten das Pascalsche Dreieck, und schließen aus der Natürlichkeit der Einträge in einer Zeile auf die Natürlichkeit der Einträge in einer Folgezeile, was angesichts des Bildungsgesetzes des Pascalsche Dreieck ja unmittelbar folgt.
anderson94 Auf diesen Beitrag antworten »

Ok nun ist mir klas dass ich bei A(n+1) für alle k= 0,1...,n+1 zeigen muss.

wie kommst du auf (durch Indexverschiebung) ? ich kenne diese Formel, jedoch dachte ich dass ich mit der Identität aus der Angabe zum Ziel kommen sollte. Der nächste Schritt mit der Summe zweier natürlichenn Zahlen ist mir dann auch klar. Somit sind wir für k fertig jedoch fehlen uns ja noch die 0 und n+1

für K=0 ergibt sich ja aus der Rekursionsformel
für k=n+1 somit sind auch die Randfälle erledigt. Das einzige was jetzt noch überbleibt ist die Indexverschiebung, weil so kommt mir der Hinweis aus der Angabe ja eher ein bischen sinnlos vor geschockt

lg
 
 
HAL 9000 Auf diesen Beitrag antworten »

Ich verstehe leider nicht, welches Problem du mit der Indexverschiebung hast? Erstaunt1
anderson94 Auf diesen Beitrag antworten »

Also ich habe nicht wirklich ein Problem damit, nur wie komme ich auf diese? Ich müsste diese ja zu erst auch beweisen oder? Mein Problem ist die Identität aus der Angabe , kann ich durch die Angabe mit indexverschiebung auf kommen? sonst wäre ja die und dessen Beweis für den Hugo Big Laugh Big Laugh

oder sehe ich da wieder etwas falsch?

lg und danke schonmal für deine Hilfe
HAL 9000 Auf diesen Beitrag antworten »

Also mal ganz, ganz langsam erklärt, was man mit Indexverschiebung hier meint:

Wir wissen, dass für gilt, das hast du ja vorher nachgewiesen.

Nun benötigen wir in unserem Beweis aber eine Darstellung von statt einer von . Zu diesem Zweck betrachten wir statt den Index , das ist der "verschobene" Index. Das bedeutet zum einen, dass bei Durchlaufen der Werte die Variable die Werte durchläuft (alle jeweils 1 höher als bei ), und zum anderen dass wir überall, wo in der Ausgangsgleichung steht, nun einfach einsetzen, was letztlich zur Gleichung führt.

Nun sind die Symbole nur irgendwelche Platzhalter, d.h., die gewonnene Aussage

Zitat:
Es gilt für alle .

kann man genausogut auch

Zitat:
Es gilt für alle .

schreiben. Jetzt verstanden?


P.S.: Bis auf die Umindizierung passiert hier schlicht NICHTS, es ist also eher eine organisatorische Fingerübung statt dass irgendwelche "echten" Rechnungen passieren. Weswegen man solche Sachen auch nur kurz in dem einen Wort "Indexverschiebung" abhandelt, dann sollte ein aufmerksamer einigermaßen geübter Leser damit zurechtkommen, ohne gleich eine Krise zu bekommen. Da solltest du dich also dran gewöhnen.
anderson94 Auf diesen Beitrag antworten »

sooooooo ich danke dir wirklich herzlich für deine Hilfe smile

deine erklärung über die Indexverschiebung hat mir das Aha Moment gebracht haha, und hab da auch was dazu gelernt danke

lg
Neue Frage »
Antworten »



Verwandte Themen

Die Beliebtesten »
Die Größten »
Die Neuesten »