Behauptung beweisen?

... komplette Frage anzeigen

3 Antworten

Schau dir beim  Erweitern mal an, was die Fakultätschreibweise bedeutet! Du solltest nur mit den noch zu ergänzenden Faktoren erweitern.

Antwort bewerten Vielen Dank für Deine Bewertung
Kommentar von ehochicks
20.10.2016, 16:03

Ja ich habe gerade ein Video gefunden, in dem jemand diese Behauptung beweist und der macht das auch nach deinem Tipp. Das kannte ich bis eben noch nicht... Vielen Dank! :)

0
Kommentar von Wechselfreund
20.10.2016, 16:08

Das Endergebnis der ersten Zeile ist außerdem falsch, im Nenner muss (k+1)!(n-k)! stehen.

0

Oje… dieser Ansatz ist mathematisch gesehen völlig sinnlos und liefert kein Verständnis, wie einem überhaupt diese Gleichung einfällt. Zum Schluss daher stehen kombinatorische Beweise (genauer genommen einer), der eben diese Gleichung herleitet und vollständig beweist. Zunächst aber die Umformung mit „!“:

  n!/(k!(n–k)!) + n!/((k+1)!(n–(k+1))!)
= (k+1) · n!/((k+1)·k!(n–k)!)
+ (n–k) · n!/((k+1)!·(n–k)·(n–k-1)!)
= (k+1) · n!/((k+1)!(n–k)!)
+ (n–k) · n!/((k+1)!(n–k)!)
= (n-k+k+1) · n!/((k+1)!(n–k)!)
= (n+1) · n!/((k+1)!(n–k)!)
= (n+1)!/((k+1)!(n–k)!)

Darum gilt 

(n+1)!/((k+1)!(n–k)!) = n!/(k!(n–k)!)
+ n!/((k+1)!(n–(k+1))!)

Mit diesen hässlichen Darstellung zu arbeiten aber liefert kein Verständnis. Man sieht nicht warum sich diese kombinatorischen Größen in einem solchen Verhältnis stehen soll. Hierfür ein…

...KOMBINATORISCHER BEWEIS (kurz). (n über k) ist definiert als die Anzahl der Möglichkeiten, k Elementen aus einer n-elementigen Menge auszuwählen. Um k+1 Elementen aus einer n+1-elementigen Menge (o. E. der X={1;2;…;n;n+1}) zu wählen zählen wir auf:

  • eines (1) der gewählten Elemente ist n+1. Dann müssen die restlichen k+1–1(=k) Elemente aus der Menge X\\{n+1} = {1;2;…;n}, welche n-elementig ist, gewählt werden. Per Definition gibt es hierfür exakt (n über k) Möglichkeiten.
  • keines der gewählten Elemente ist n. Dann werden alle k+1 Elemente aus der n-elementigen Menge X\\{n+1} = {1;2;…;n} gewählt. Per Definition gibt es hierfür exakt (n über k+1) Möglichkeiten.

Diese zwei erschöpfen alle Auswahle und sind offensichltich paarweise disjunkt. Daher gilt

(n+1 über k+1) = #Möglichkeiten k aus n-el. Menge
= (n über k) + (n über k+1)

QED.

...KOMBINATORISCHER BEWEIS (formal/vollständig).

Defn. (n über k) := |{A⊆X : |A|=k}| für eine Menge X mit #X=n. ⊣
Lemma. Diese Def. ist wohldefiniert (hängt nur von n,k ab und nicht X). ⊣
Satz. (n+1 über k+1) = (n über k) + (n über k+1).
Beweis. Sei X eine n+1-elementige Menge und sei x₀∈X fixiert, sodass insbesondere Y := X \\{x₀} eine n-elementige Menge ist. Dann gilt per Definition (n+1 über k+1) = |{A⊆X : |A|=k+1}|. Andererseits gelten

(S:=){A⊆X : |A|=k+1} = {A⊆X : |A|=k+1, x₀∈A} (=:S₁)
∪ {A⊆X : |A|=k+1, x₀∉A} (=:S₂)

S₁ = {A⊆X : |A|=k+1, x₀∈A}
= {B∪{x₀} : B⊆X\\{x₀}, |B|=k}
= {B∪{x₀} : B⊆Y, |B|=k}

S₂ = {A⊆X : |A|=k+1, x₀∉A}
= {A⊆X\\{x₀} : |A|=k+1}
= {A⊆Y : |A|=k+1}

Per Definition von (· über ·) geht aus der Beschreibung von S₂ hervor, dass |S₂| = (n über k+1), da |Y|=n.
Da S₁={B∪{x₀} : B⊆Y, |B|=k} und Y, {x₀} disjunkt sind, gibt es offensichtlich eine Bijektion zwischen S₁ und {B⊆Y : |B|=k}. Per Definition von Kardinalität folgt aus der Existenz einer Bijektion |S₁| = |{B⊆Y : |B|=k}|, welches wiederum per Definition gleich (n über k) ist.
Da S₁, S₂ disjunkt sind und S=S₁∪S₂, gilt per Definition von Kardinaladdition |S₁|+|S₂| = |S₁∪S₂| = |S|. Darum gilt

(n+1 über k+1) = |S| 
= |S₁|+|S₂|
= (n über k) + (n über k+1).

QED.

Antwort bewerten Vielen Dank für Deine Bewertung

Bist auf dem Richtigen weg, als Tipp würde ich sagen, dass du (n+1)!=(n+1) * n! benutzen könntest.

Antwort bewerten Vielen Dank für Deine Bewertung
Kommentar von ehochicks
20.10.2016, 16:59

Danke! :) Mit dem Rechnen mit Fakultäten tu ich mich noch ein wenig schwer, aber ich bleib dran :)

0