Binomialkoeffizient / Natürliche Zahl / Beweis

Aufrufe: 161     Aktiv: 11.05.2021 um 23:53

0

Aufgabe (︶^︶)

Beweisen Sie mit Induktion und OHNE Benutzung des Binomischen Lehrsatzes, dass 


Problem ╰(‵□′)╯

Hallu!

Ich habe hier ein folgendes Problemchen und zwar, ich weiß nicht genau wie hier der Induktionsschritt funktioniert bzw. was ich denn genau machen muss, ich habe mal bis jetzt folgendes (bitte ignoriert den Bruchstrich, ich weiß, dass der nicht hingehört): 


Induktionsanfang: 



Induktionsannahme: 



Induktionsschritt: 




Nun stellt sich jetzt hier die Frage, was ich hier mit den (k+1) über (n+1) anfangen soll? Damit ist ja noch nicht bewiesen, dass der Binominalkoeffiezient ein Element der natürlichen Zahlen ist, oder? 😅
 

gefragt

Punkte: 24

 

Kommentar schreiben

1 Antwort
1
Man nimmt die Aussage:
Für alle \(n\) gilt: Für alle \(k\in\{0,1,\ldots,n\}\) gilt \(\binom{n}k\in N\).
Dann kommt es mit Induktion über \(n\) hin, weil in der Ind.Ann. "für alle \(k\)" drin vorkommt. Und mit Deiner letzten Zeile, dem "Additionstheorem" für Binomialkoeffizienten, ist der Ind.Schritt dann sofort klar.
Schau es Dir nochmal in Ruhe an und frag ggf. nach.
Diese Antwort melden
geantwortet

Lehrer/Professor, Punkte: 14.12K
 

Dankeschön für deine Antwort! ヽ(゜▽゜ )-

Aber ich denke, ich verstehe nicht ganz was Du hier meinst, weil ich ein bisschen zu kompliziert denke.

Meinst Du vielleicht, dass wenn ich die Aussage "Für alle n gilt: Für alle k....." noch hinzufüge, dass ich dann beim Induktionsschritt noch beweisen muss, dass k => n + 1 auch gilt, denn so würde dann der Additionstheorem in dem Fall gelten und zeigen, dass der Binomialkoeffizient ein Element der natürlichen Zahlen ist, oder?
  ─   thepeasant 10.05.2021 um 20:20

1
In meiner Antwort meinte ich, dass in der Ind.ANN. das "für alle k" vorkommt (hab ich oben verbessert).
Zu zeigen ist ja "für alle n,k gilt....". Mir ging es darum, das aufzuteilen: "Für alle n gilt:" und dann kommt eine von n abhängige Aussage (in der "für alle k" steht). Die Induktion geht über n, also der Ind.Schritt ist "n->n+1".
Das Additionstheorem brauchen wir auf jeden Fall, wenn das nicht in der Vorlesung war, muss das hier nachgewiesen werden (aber nicht in der Induktion, sondern als Nebenrechnung vorneweg). Schreib Dir die Ind.Ann. und die Ind.Beh. genau hin, dann ist klar, was zu zeigen ist.
  ─   mikn 10.05.2021 um 20:42

Also, ich habe jetzt nun folgendes:



> Induktionsvoraussetzung (k = n) :

"Für alle n gilt: Für alle k = {0, 1, ...., n}" und sei (n / k) ∈ N.

> Induktionsbehauptung (k = n + 1):

"Für alle n + 1 gilt: Für alle k = {0, 1, ...., n + 1}" und sei sei (n + 1 / k) ∈ N.

> Induktionsschritt:

n => n + 1

z.Z. ( (n + 1) / k) := ( (n+1)! / (k! ((n+1) - k)! ) für k = 0, 1, ... , n + 1

((n + 1) / k) + ( n / k ) = ..... = ( (n + 1) / (k + 1) )




Ist das so nun richtig ? ( ̄ε(# ̄)







  ─   thepeasant 10.05.2021 um 21:39

Mal ehrlich: Du schreibst da so Sätze hin, aber was die bedeuten und was Induktion ist, hast Du nicht verstanden. Das ist dann gerade bei so einer Behauptung wie dieser hier schwierig.
Die Ind. Ann. lautet: Es gelte für EIN \(n\in N\): Für alle \(k\in\{0,1,...,n\}\) ist \(\binom{n}k\in N\).
(Die Ind.Ann. lautet immer wie die zu zeigende Aussage, aber eben nur für EIN n.)
Ind.Beh.: Dann gilt die Beh. für n+1, d.h. es gilt: Für alle \(k\in\{0,1,...,n+1\}\) ist \(\binom{n+1}k\in N\).
Ind. Schritt.:
Sei also \(k\in\{0,1,...,n+1\}\).
1. Fall: \(1\le k\le n\):
Dann gilt: \(\binom{n+1}k=\binom{n}{k-1}+\binom{n}k \in N\) nach Ind. Ann. (Summe zweiter natürlicher Zahlen).
Die beiden noch fehlenden Fälle schaffst Du bestimmt selbst, ohne Induktion durch direktes Nachrechnen. Die gehören auch noch hier in den Ind.Schritt (auch wenn die Ind.Ann. dabei nicht benötigt wird).
  ─   mikn 10.05.2021 um 22:02

Also mit Induktion komme ich eigentlich ziemlich gut zurecht, da hatte ich sonst nie Schwierigkeiten, aber einen Binomialkoeffizienten mithilfe eines Induktionsverfahrens zu beweisen, ist leider mein erstes Mal... tut mir leid. ( ̄ε(# ̄)

2. Fall: 1 ≤ n ≤ k
Dann gilt: (n / k + 1) = (( n + 1 ) / (k + 1)) - (n / k) <--- Subtraktion mit zwei natürlichen Zahlen lt. Induktionsannahme

3. Fall: k > n
Dann gilt ( n / k ) = 0 <---- 0 ist eine natürliche Zahl
  ─   thepeasant 10.05.2021 um 22:26

So wie Du Ind.Ann. mit "für alle n" und genauso die Ind.Beh. "für alle n+1..." geschrieben hast, hast Du vielleicht(!) schonmal einen Ind.Beweis richtig gerechnet, aber nicht verstanden, was das Prinzip ist. Das sage ich so deutlich, um Dich zu ermuntern das unbedingt nachzuholen. Hier ist eben für Dich NICHT das Problem dass es was mit Bin.Koeff ist, sondern hier fliegt auf, dass Du Induktion nicht verstanden hast. Kümmer Dich um diese Lücke.
Auch die zwei fehlenden Fälle zeigen, dass Du nicht wirklich weißt, was hier abgeht.
Wir müssen was für alle k=0,...,n+1 zeigen. Den Fall k=1,...,n, hab ich schon gemacht. Was fehlt jetzt noch?
  ─   mikn 10.05.2021 um 22:34

Ja, da stimme ich Dir natürlich voll und ganz zu, diese Lücke versuche ich grundsätzlich schon die ganze Zeit zu schließen, aber im Internet wird man leider nie wirklich fündig und mein Professor weigert sich mit Händen und Füßen, das ganze nochmals genauer zu erklären. 😐

Ich glaube, dass wird noch denn Fall für k = 0,...,n - 1 zeigen müssen, oder?
  ─   thepeasant 10.05.2021 um 22:52

Ohje, wo hakt das denn jetzt? Angenommen man soll eine Aussage für k=0,1,2,3,4,5 zeigen. Für k=1,2,3,4 sei es schon gezeigt. Welche Fälle bleiben dann noch? Nicht raten, nachdenken!   ─   mikn 10.05.2021 um 22:55

Ich denke es hakt bei mir einfach überall.... :<

Hm, wenn ich es mir so ansehe, dann fehlt also noch der Fall k = 0 und k = n + 1?

  ─   thepeasant 10.05.2021 um 23:02

1
Aha, geht doch.   ─   mikn 10.05.2021 um 23:04

1
Hier, ungefragt, nochmal die Induktionsidee für diese Aufgabe aus einer anderen Sicht, nämlich mit der Idee, dass die Binomialkoeffizienten \(\binom{n}k\) alle in der n-ten Zeile im Pascalschen Dreieck stehen (die Spitze ist die 0-te Zeile).
Ind. Anf.: An der Spitze des Pascalschen Dreiecks steht eine nat. Zahl.
Ind. Ann.: Für ein n gilt: In der n-ten Zeile des PD stehen nur nat. Zahlen.
Ind. Beh.: Dann stehen in der n+1-ten Zeile des PD auch nur nat. Zahlen.

Und das PD wird ja zeilenweise mit dem Additionstheorem aufgebaut.
  ─   mikn 10.05.2021 um 23:22

Oh, das hat mir jetzt ein wenig mehr Durchblick verschafft, sehr gute Erklärung! Danke! 😄

Kann das sein, dass nun die folgenden Fälle wie gefolgt lauten:

2. Fall: 1 ≤ k ≤ n+1
(( n + 1) / k ) = (( n + 1) / k - 1 )) + (n / k)


3. Fall n = k = 0
( 0 / 0 ) = 1 <---- ist eine natürliche Zahl


Ich denke, dass es (sehr) wahrscheinlich wieder falsch ist, vielleicht sollte ich besser morgen weiter machen.... (╯°□°)╯︵ ┻━┻
  ─   thepeasant 10.05.2021 um 23:37

1
Ja, gute Idee. Du hast die Fälle richtig benannt, aber willst sie doch nicht nehmen.   ─   mikn 11.05.2021 um 00:06

Hab jetzt folgenden Ansatz, ich denke, dass es diesmal stimmen sollte: (︶^︶)


2. Fall: 1 ≤ k ≤ n+1
(n + 1) über (n + 1) = (n über n + 1) + (n über n) = 0 + 1 = 1


3. Fall: k = 0
(n+1) über 0 = (n über 0) + (n über -1) = 1 + 0 = 1


Ich habe hier bloß eine kleine Frage, warum müssen wir hier die Fälle eigentlich betrachten?


  ─   thepeasant 11.05.2021 um 20:27

1
Oben hab ich den größten Teil des Beweises schon hingeschrieben ("Mal ehrlich...."). Arbeite das durch, bis Du es verstanden hast. Lies nach, was zu zeigen ist, insb. für welche k etwas zu zeigen. Dann prüfe, welche k's ich schon erledigt habe.Darauf hast Du gesagt, nach einigen Anläufen, es fehlt noch k=n+1 und k=0. Was auch richtig ist. Also, Du weißt, was noch fehlt, dann mach das (und nichts anderes bitte).
Und schau Dir meinen 1.Fall an, ob die beiden fehlenden Fälle auch damit gehen bzw. wenn nicht, warum nicht.
  ─   mikn 11.05.2021 um 21:21

Frage:
Ist eigentlich der Induktionsschritt den ich ganz am Anfang gemacht habe eigentlich für den Hugo? Oder muss ich den schon beim Induktionsschritt mit berücksichtigen?

Du hast die k's nicht für bestimmtes, festes k betrachtet sondern für alle k's betrachtet, also {0, 1, ... n}.

Und es fehlt deshalb k = n + 1, weil wir ja wissen müssen, ob dies für das nächste k auch gilt, also wegen der Behauptung, dass es für das nächste k auch mit allen möglichen Werten stimmt bzw. ein Element der natürlichen Zahlen noch ist.

k = 0 fehlt, weil wir nur den Fall 1 ≤ k ≤ n bzw. 1 ≤ k ≤ n+1 betrachtet haben, also die 0 wurde hier nicht berücksichtigt.


Und ja, die beiden fehlenden Fälle funktionieren auch bzw. sind ein Element der natürlichen Zahl:

Fall 2: k = n + 1
(n + 1) über (n + 1) = (n über n + 1) + (n über n) = 0 + 1 = 1 <--- 1 ist ein Element der natürlichen Zahlen


3. Fall: k = 0
(n+1) über 0 = (n über 0) + (n über -1) = 1 + 0 = 1 <--- 1 ist ein Element der natürlichen Zahlen
  ─   thepeasant 11.05.2021 um 21:42

Dein Ind.Schritt ganz oben hilft gar nicht, weil Du k->k+1 machst, aber wir brauchen n->n+1. Was man davon brauchen kann, ist der Nachweis des Additionstheorems (wie schon gesagt: bitte als Nebenrechnung vorweg, nicht im Induktionsbeweis mittendrin).
Fälle 2., 3: Du schreibst irgendwas hin, hast Du es Dir mal angeschaut? Lies es Dir durch und sag, warum das so nicht geht (und wenn es ginge, wäre es auch noch zu kompliziert).
  ─   mikn 11.05.2021 um 21:49

Warum sollen Fall 2 und Fall 3 nicht stimmen? Was genau stimmt denn hier nicht? Ich habe es so eingesetzt und fertig. Was soll ich denn noch machen? Ich befasse mich zum ersten Mal mit diesem Thema, bitte nicht vergessen... Also ich weiß nicht was Du denkst, aber ich kann da jetzt nicht gleich wirklich ein "Wunderwerk" zaubern, ich brauche auch ein Bisschen eine Erklärung damit ich überhaupt weiter komme, denn wie gesagt, ich werde im Internet überhaupt nicht fündig und weiß ja auch nicht wie das geht, ich fühle mich gerade ein Bisschen im Stich gelassen...😅

Funktioniert es vielleicht deshalb nicht, weil z.B.

(n+1) über 0 = (n über 0) + (n über -1) = 1 + 0 = 1

Hier haben wir eine 0 stehen in der Addition, und 0 ist kein Element der natürlichen Zahlen?
  ─   thepeasant 11.05.2021 um 21:58

Was ist denn \(\binom{n}{-1}\)? Ich meine immer, man lernt am meisten, wenn man es, ggf. mit Hilfe, selbst raus findet. Und ich lasse hier für Dich nichts wirklich schwieriges übrig.
Aber: Du hast Induktion nicht verstanden, und Bin.Koeff. auch nicht. Das ist nicht schlimm, aber schlimm ist, wenn man das nicht vorher klärt, bevor man so eine formal nicht leichte Aufgabe angeht.
  ─   mikn 11.05.2021 um 22:16

Ich weiß, kann Dich gut verstehen, vorrechnen lassen ist nie die beste Lösung, aber ein paar Erklärungen oder Informationen wären grundsätzlich schon ganz nett, sonst schwimme ich eben jedes Mal im Kreis herum.... (︶^︶)

Und ja, ich habe nicht gerade sehr viel mitbekommen, das Problem ist, die Kombination von meinem Professor, der (leider) nichts erklären möchte und Informationen, die kaum im Internet zu finden sind machen mich leider nicht schlauer. Ich probiere es natürlich gerne und versuche auch schon alles mögliche, aber irgendwie klappt es nicht ganz...Ich bin nicht gerade ein Mathe-Freund und kann es auch nicht wirklich... 😅

Also (n über -1) = 0. Oder meinst du eher von wo es genau herkommt bzw. wie ich da drauf komme...?
  ─   thepeasant 11.05.2021 um 22:34

Ein sinnvolles Vorgehen beim Lernen wäre:
1. Induktion an einfachen Beispielen lernen und üben, bis das Prinzip verstanden ist.
2. Bin.Koeff. lernen, indem man die Def. (die Du anscheinend nicht kennst) anschaut, ein paar Beispiele ausrechnet, um ein Gefühl dafür zu kriegen, und einfache Eigenschaften nachweist
3. Diese Aufgabe probieren.
Du hast Schritt 1 und 2 übersprungen, dann ist klar, dass bei dieser Aufgabe Frust bevorsteht.

Du behauptest einfach mal \(\binom{n}{-1}=0\). Schau Dir die Def. an, siehe Schritt 2.
  ─   mikn 11.05.2021 um 22:44

So mache ich es grundsätzlich auch, aber wenn man mir sowas nicht zeigt bzw. wenn der Professor kein Wort darüber fallen lässt wie es funktioniert, was man damit macht und dass es noch weitere Definitionen gibt... Na wie soll ich denn das am Besten machen? Und dann werden noch solche Aufgaben verteilt, die von über 50% der Studenten nicht selbständig gelöst werden können.

Im Moment bin ich mit der Aufgabe ein Bisschen unter Zeitdruck... Und wie gesagt, ich habe ja schon überall im Internet nachgeschaut und da stand auf verschiedene Seiten, dass (n über -1) = 1 und auf einer andere Seite stand dann wieder (n über -1) = 0.... Also daraus werde ich halt echt nicht schlau und wenn es mir jemand sagen bzw. zeigen würde, dann lerne ich daraus wesentlich mehr irgendwie.... war bis jetzt immer so. 😅
  ─   thepeasant 11.05.2021 um 22:53

Man kann z.B. gleich bei wikipedia nachschauen, da muss man nicht lange suchen und wird gleich fündig. Insb. steht da die Def.. https://de.wikipedia.org/wiki/Binomialkoeffizient
Lies Dir alles(!) bis einschl. des Pascalschen Dreiecks durch. Und rechne einige selbst ausgedachte(!!!) Zahlenbeispiele.
  ─   mikn 11.05.2021 um 23:26

Ja okay ich werde es mir ansehen, aber der tatsächliche Grund ist eher, dass ich beim Beweisen hauptsächlich Schwierigkeiten habe! Es liegt weder an den Definitionen von Binomialkoeffizienten noch an Induktionsbeweis, ja klar, man kennt natürlich nicht alle Definitionen und ich war auf Wikipedia schon tausend mal, aber dennoch kann ich die Aufgabe nicht lösen, weil ich einfach nicht verstehe was ich jetzt machen soll?

Ich verstehe eben nicht ganz was Du möchtest? Auf der anderen Seite stimmen anscheinend die Fälle nicht, auf der anderen Seite stimmt wieder so wie ich die Fälle gelöst habe nicht? Das hilft mir eben gar nicht wirklich weiter.... Ich denke wir sollten es an dieser Stelle lieber sein lassen. Du hast es wenigstens versucht, aber langsam habe ich jetzt echt ein Bisschen die Nerven bekommen, denn dieses hin und her, macht mich ein wenig wahnsinnig. Nicht jeder versteht Mathe so schnell und manchmal hilft es einfach, wenn man doch ein bisschen was darüber erzählt oder sagt, WARUM es überhaupt falsch ist. Man kann daraus eben nichts schließen, wenn man nur sagt FALSCH, aber keine Begründung dazu gibt. Warum macht man wohl Fehler? Genau weil man es nicht versteht, und deshalb sollte man auch sagen weshalb und warum, damit ich es nachvollziehen kann und dann kann ich gezielt suchen und diesen Fehler eher beheben.

Wie Du sagtest, die Aufgabe ist nicht einfach, und auch wenn man versteht wie es funktioniert, kann man nicht immer alles lösen und beweisen etc. Und ein Induktionsbeweis mit einem Binomialkoeffizienten ist natürlich wieder ein "Sonderfall" und weicht stark von einer normalen Induktion ab, zumindest der Induktionsschritt.
  ─   thepeasant 11.05.2021 um 23:51

Kommentar schreiben