Mathematik online lernen im Mathe-Forum. Nachhilfe online

Startseite » Forum » Vollständige Induktion beim Binomialkoeffizienten?

Vollständige Induktion beim Binomialkoeffizienten?

Universität / Fachhochschule

Binomialkoeffizienten

Tags: Binomialkoeffizient, Vollständig Induktion

Phikor aktiv_icon

13:27 Uhr, 31.01.2019

Ich soll für alle

n, k \in ℕ_{0}

mit

0 \leq k \leq n - 1

beweisen:

\frac{n}{k} + \frac{n}{k + 1} = \frac{n + 1}{k + 1}

(Ohne Bruchstrich also "n über k" leider wird \binom nicht unterstützt.)

Als überschrift hat das ganze "Vollständige Induktion". Ich finde allerdings keinen Weg mit der vollständigen Induktion und auch online hab ich nur solche Wege gefunden: www.youtube.com/watch?v=_hfIutSSjpo

Hat irgendjemand eine Idee wie man das nach dem Prinzip der vollständigen Induktion über n (oder vielleicht k?) lösen kann?

Vielen Dank im Voraus.

Phikor

Für alle, die mir helfen möchten (automatisch von OnlineMathe generiert):
"Ich möchte die Lösung in Zusammenarbeit mit anderen erstellen."

Hierzu passend bei OnlineMathe:

Online-Übungen (Übungsaufgaben) bei unterricht.de:

Kombinatorik: Ziehen ohne Reihenfolge und ohne Zurücklegen

HAL9000

13:38 Uhr, 31.01.2019

LaTeX-Tipp: Hier im Forum geht nur "{{n}\choose {k}}" für den Binomialkoeffizienten.

(\binom{n}{k}) + (\binom{n}{k + 1}) = (\binom{n + 1}{k + 1})

Ich wüsste nicht, warum man das per Vollständiger Induktion beweisen sollte, wo es doch viel einfacher geht. Nimm die Fakultätsrepräsentationen der beiden Terme links, bring die auf einen Bruchstrich mit dem Hauptnenner

(k + 1)! \cdot (n - k)!

, dann steht nach einer geeigneten Zählerzusammenfassung schon fast das Ergebnis da, ohne dass man da eine Induktionsvoraussetzung benötigen würde.

Es ist wohl eher so, dass diese Pascal-Dreieck-Iterationsgleichung sehr häufig in Induktionsschritten von Beweisen anderer Aussagen Verwendung findet, etwa im Beweis des Binomischen Satzes.

Phikor aktiv_icon

13:47 Uhr, 31.01.2019

Ah! Ich hab es nicht doppelt eingeklammert und darum stand dort immer

(\binom{n}{k}) + 1

statt

(\binom{n}{k + 1})

. Danke schon mal dafür.

Wie gesagt den Beweis mit dem Hauptnenner hab ich auch gefunden und verstanden. Ich werde wohl mal versuchen den Tutor zu erreichen, ob dort nun wirklich die vollständige Induktion gefragt ist oder die Überschrift nur missverständlich gewählt wurde.

Danke für die Hilfe.

DerDepp aktiv_icon

13:53 Uhr, 31.01.2019

Hossa :-)

Der Binomaialkoeffizient

(\binom{n}{k})

gibt ja an, wie viele Möglichkeiten es gibt, aus n Elementen genau k ohne Zurücklegen auszuwählen. Damit ist der Zusammenhang eigentlich klar. Kommt ein neues Element hinzu, hast du (n+1) Elemente. Wenn du davon nun (k+1) auswählen sollst, also

(\binom{n + 1}{k + 1})

gesucht ist, gibt es 2 Möglichkeiten: (a) Das neu hinzugekommene Element ist dabei, dann müssen k Elemente aus den alten n ausgewählt werden, das gibt den Beitrag

(\binom{n}{k})

. (b) Das neu hinzugekommene Element ist nicht dabei, dann müssen (k+1) Elemente aus den alten n ausgewählt werden, das gibt den Beitrag

(\binom{n}{k + 1}) .

Um den Beweis formal zu führen, musst du ja eine Definition vom Binomialkoeffizienten vorlíegen haben, etwa:

(\binom{n}{k}) = \frac{n!}{k! \cdot (n - k)!}

Hast du die? Dann kannst du die vollständige Induktion damit durchführen.

Phikor aktiv_icon

14:13 Uhr, 31.01.2019

Ja die hab ich.

Hab auch schon mal den IA gemacht für

n = 1

woraus dann ja folgt

k = 0

, da

0 \leq k \leq n - 1

.

Dann hab ich also

(\binom{1}{0}) + (\binom{1}{1}) = (\binom{2}{1})

Daraus folgt:

\frac{1!}{0! * (1 - 0)!} + \frac{1!}{1! * (1 - 1)!} = \frac{2!}{1! * (2 - 1)!}

Was dann ergibt:

1 + 1 = 2

IA gilt also. Und nach der IV kommen wir ja dann zu:

IS

n \to n + 1

(\binom{n + 1}{k}) + (\binom{n + 1}{k + 1}) = (\binom{n + 2}{k + 1})

(\binom{n + 2}{k + 1}) = \frac{(n + 2)!}{(k + 1)! * ((n + 2) - (k + 1))!} = \frac{(n + 2)}{(n - k + 1)} * \frac{(n + 1)!}{(k + 1)! * ((n + 1) - (k + 1))!} = \frac{(n + 2)}{(n - k + 1)} * (\binom{n + 1}{k + 1})

Also wenn wir die IV einsetzen:

\frac{(n + 2)}{(n - k + 1)} * ((\binom{n}{k}) + (\binom{n}{k + 1})) = \frac{(n + 2)}{(n - k + 1)} * (\binom{n}{k}) + \frac{(n + 2)}{(n - k + 1)} * (\binom{n}{k + 1})

Und wenn ich das doch nun richtig sehe muss ich von hier doch auf

(\binom{n + 1}{k}) + (\binom{n + 1}{k + 1})

kommen oder? Und da liegt mein Problem, da ich nicht verstehe wie ich dort hinkommen soll.

HAL9000

15:25 Uhr, 31.01.2019

Die Forderung "unbedingt Induktionsbeweis" ist an sich albern, aber man kann die Schildbürgerei natürlich formal mitmachen, indem man aus einem vorliegenden induktionsfreien Beweis "einen mit Induktion" zaubert:

Man deklariert seinen induktionsfreien Beweis zum Induktionsschritt, in dem man aber auf eine Nutzung der Induktionsvoraussetzung verzichtet (es gibt keine "Pflicht", die zu nutzen). Noch einen Induktionsanfang ergänzt - voila, fertig ist der Induktionsbeweis.

Phikor aktiv_icon

15:31 Uhr, 31.01.2019

Die Information, das man die Induktionsvoraussetzung nicht verpflichtend braucht hat mir noch gefehlt, das macht das Ganze machbar.

Danke für die Hilfe HAL9000 und DerDepp ich denke da wurde einfach ein Fehler beim erstellen der Aufgabe gemacht, aber eine mögliche Lösung hab ich ja nun auch.

1457655

1457640

	Status: nicht eingeloggt	Noch nicht registriert?