Mathematik online lernen im Mathe-Forum. Nachhilfe online

Startseite » Forum » vollständige Induktion - Binomialkoeffizienten

vollständige Induktion - Binomialkoeffizienten

Universität / Fachhochschule

Tags: Binomialkoeffizient, Induktion, Vollständig Induktion

Frizzem aktiv_icon

14:26 Uhr, 16.11.2015

Hallo! :-)

Folgende Aufgabe sollen wir in einer Übungsaufgabe bearbeiten:

Sei

ℕ 0 = ℕ \cup {0}

die Menge der natürlichen Zahlen mit 0. Die Fakultät einer natürlichen
Zahl

n

ist definiert durch

n! := 1 \cdot 2 \cdot ... \cdot n

. Außerdem definiert man

0! := 1

.
Die Binomialkoeffizienten

(\begin{matrix} n \\ k \end{matrix})

sind wie folgt definiert:

1. Für

n \in ℕ 0

setzt man

(\begin{matrix} n \\ 0 \end{matrix}) := 1

und

(\begin{matrix} n \\ n \end{matrix}) := 1

.

2. Für

k, n \in ℕ, 0 < k < n

setzt man

(\begin{matrix} n \\ k \end{matrix}) := (\begin{matrix} n - 1 \\ k - 1 \end{matrix}) + (\begin{matrix} n - 1 \\ k \end{matrix})

Dann gilt

(\begin{matrix} 0 \\ 0 \end{matrix}) = (\begin{matrix} 1 \\ 0 \end{matrix}) = (\begin{matrix} 1 \\ 1 \end{matrix}) = 1, (\begin{matrix} 2 \\ 0 \end{matrix}) = 1, (\begin{matrix} 2 \\ 1 \end{matrix}) = (\begin{matrix} 1 \\ 0 \end{matrix}) + (\begin{matrix} 1 \\ 1 \end{matrix}) = 1 + 1 = 2,

etc.
Damit ist der Binomialkoeffizient

(\begin{matrix} n \\ k \end{matrix})

für alle

n, k \in ℕ 0, k \leq n

definiert.

Zeigen sie mittels vollständiger Induktion:

Für alle

n, k \in ℕ 0, k \leq n

gilt

: (\begin{matrix} n \\ k \end{matrix}) = \frac{n!}{k! (n - k)!}

Ich komme beim Induktionsbeweis nicht weiter und ich bin mir nicht sicher welcher Ansatz richtig ist, erst gucken für

k + 1

oder

n + 1

. Außerdem hat uns unser Tutor noch angemerkt, dass wir die Randfälle beachten sollten.
Wäre sehr hilfreich, wenn jemand heute noch eine Antwort liefern könnte, bin am verzweifeln und weiß echt nicht weiter!

: (

Für alle, die mir helfen möchten (automatisch von OnlineMathe generiert):
"Ich benötige bitte nur das Ergebnis und keinen längeren Lösungsweg."

Hierzu passend bei OnlineMathe:

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

Kombinatorik: Ziehen ohne Reihenfolge und ohne Zurücklegen

Bummerang

14:38 Uhr, 16.11.2015

Hallo,

Du hast hier nur eine Induktion über

n!

Aus der Definition kannst Du ableiten, dass wegen

0 < k < n

Du eine Induktion nur für

n \geq 2

führen kannst. Für alle Binomialkoeffizienten

(\begin{matrix} n \\ k \end{matrix})

mit

n < 2

musst Du die Werte explizit im Induktionsanfang ermitteln und mit der zu beweisenden Formel vergleichen. Dann sagst Du in der Induktionsvoraussetzung, dass es ein

n

gibt, so dass für

0 \leq k \leq n

die zu beweisende Formel gilt. Hier an dieser Stelle ist das "

\leq

" wichtig! Dann behauptest Du, dass dann die Formel auch für

n + 1

gilt und alle

k

mit

0 \leq k \leq n + 1

gilt. Im Beweis der Induktionsbehauptung zeigst Du nun zuerst, dass die Formel für

k = 0

nach Definition gilt. Dann zeigst Du, dass sie für alle

k

mit

0 < k \leq n

ebenfalls gilt (

\leq n

heisst ja nichts anderes als

< n + 1

. Damit erfüllt dieses

k

im Beweis die Voraussetzung

0 < k < n + 1

für die Anwendung des zweiten Teils der Definition des Binomialkoeffizienten und Du kannst die Vorschrift zur Berechnung von

(\begin{matrix} n + 1 \\ k \end{matrix})

benutzen). Zuletzt zeigst Du dann noch, dass sie auch für

k = n + 1

nach Definition gilt.

Frizzem aktiv_icon

14:50 Uhr, 16.11.2015

Muss man hier wirklich nicht zwei mal Induktion anwenden ?

Unser Tutor hat uns nämlich an die Tafel noch geschrieben:

Für alle

n \in ℕ 0

gilt:
Für alle

k \in ℕ 0

mit

k \leq n

gilt

(\begin{matrix} n \\ k \end{matrix}) = \frac{n!}{k! (n - k)!}

Achtung Randfälle beachten wenn

k = n

ist oder wenn

k = 0

ist

Bummerang

14:57 Uhr, 16.11.2015

Hallo,

Du zeigst für ein beliebiges

k

bei

n + 1

(also

0 < k \leq n),

dass die Definition zur Gültigkeit der Formel führt. Du schließt in (aus der Sicht des Pascalschen Dreiecks) doch nur von zwei in der n-ten Zeile gültigen Werten auf einen in der n+1-ten Zeile gültigen Wert. Du hast doch keine Möglichkeit für einen Schluß aus dem k-ten Element einer Zeile auf den Wert des k+1-ten Elements der selben Zeile! Da geht keine Induktion!

Frizzem aktiv_icon

15:08 Uhr, 16.11.2015

Okay, das Problem ist, dass ich noch nicht genau deinen ersten Text verstehe.
Könntest du das, wenn es dir keine Umstände macht ausschreiben (also die Induktion ein mal bei dem Beispiel ausführen) mit kurzen Kommentaren, sodass ich das nachvollziehen kann ?

Wäre sehr hilfreich!

ledum aktiv_icon

15:44 Uhr, 16.11.2015

Hallo
führe den Beweis zuerst für festes

k

und damit Induktion über

n

Gruß ledum.

Frizzem aktiv_icon

16:02 Uhr, 16.11.2015

Und was mache ich dann ?

Frizzem aktiv_icon

16:06 Uhr, 16.11.2015

Ich bräuchte jemanden der mir das kurz vorrechnen kann, damit ich das nachvollziehen kann.

ledum aktiv_icon

16:47 Uhr, 16.11.2015

Hallo
die Anweisung von B. ist doch sehr genau, alao fang mal an, wir sind keine Vorrechner
Gruß ledum

Bummerang

16:49 Uhr, 16.11.2015

Hallo,

Induktionsanfang:

n = 0 :

Es ist nur

k = 0

möglich!

\frac{n!}{k! \cdot (n - k)!} = \frac{0!}{0! \cdot (0 - 0)!} = \frac{0!}{0! \cdot 0!} =_{(D e f f u e r F a k u l t a e t)} \frac{1}{1 \cdot 1} = 1

Das entspricht dem Wert aus der Definition des Binomialkoeffizienten:

(\begin{matrix} n \\ 0 \end{matrix}) = 1

für alle

n,

also auch für

n = 0

n = 1 :

Es ist nur

k = 0

und

k = 1

möglich!

k = 0 :

\frac{n!}{k! \cdot (n - k)!} = \frac{1!}{0! \cdot (1 - 0)!} = \frac{1!}{0! \cdot 1!} =_{(D e f f u e r F a k u l t a e t)} \frac{1}{1 \cdot 1} = 1

Das entspricht dem Wert aus der Definition des Binomialkoeffizienten:

(\begin{matrix} n \\ 0 \end{matrix}) = 1

für alle

n,

also auch für

n = 1

k = 1 :

\frac{n!}{k! \cdot (n - k)!} = \frac{1!}{1! \cdot (1 - 1)!} = \frac{1!}{1! \cdot 0!} =_{(D e f f u e r F a k u l t a e t)} \frac{1}{1 \cdot 1} = 1

Das entspricht dem Wert aus der Definition des Binomialkoeffizienten:

(\begin{matrix} n \\ n \end{matrix}) = 1

für alle

n,

also auch für

n = 1

.

Induktionsvoraussetzung:

Es gibt ein

n \in ℕ, n \geq 1,

so dass für alle

k \in ℕ

mit

0 \leq k \leq n

gilt:

(\begin{matrix} n \\ k \end{matrix}) = \frac{n!}{k! \cdot (n - k)!}

Induktionsbehautung:

Dann gilt auch für

n + 1,

so dass für alle

k \in ℕ

mit

0 \leq k \leq n + 1

gilt:

(\begin{matrix} n + 1 \\ k \end{matrix}) = \frac{(n + 1)!}{k! \cdot ((n + 1) - k)!}

Fall

1 : k = 0

Es gilt:

\frac{(n + 1)!}{k! \cdot ((n + 1) - k)!}

= \frac{(n + 1)!}{0! \cdot ((n + 1) - 0)!}

= \frac{(n + 1)!}{0! \cdot (n + 1)!}

=_{(D e f f u e r F a k u l t a e t)} \frac{(n + 1)!}{1 \cdot (n + 1)!}

= \frac{(n + 1)!}{(n + 1)!}

= 1

Das entspricht dem Wert aus der Definition des Binomialkoeffizienten:

(\begin{matrix} n + 1 \\ 0 \end{matrix}) = 1

für alle

n

.

Fall

2 : 0 < k \leq n

\frac{(n + 1)!}{k! \cdot ((n + 1) - k)!}

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

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

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

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

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

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

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

=_{(I n d - v o r)} (\begin{matrix} n \\ k - 1 \end{matrix}) + (\begin{matrix} n \\ k \end{matrix})

=_{(D e f d e s B i n o m i a l k o e f f)} (\begin{matrix} n + 1 \\ k \end{matrix})

Fall

3 : k = n + 1

Es gilt:

\frac{(n + 1)!}{k! \cdot ((n + 1) - k)!}

= \frac{(n + 1)!}{(n + 1)! \cdot ((n + 1) - (n + 1))!}

= \frac{(n + 1)!}{(n + 1)! \cdot 0!}

=_{(D e f f u e r F a k u l t a e t)} \frac{(n + 1)!}{(n + 1)! \cdot 1}

= \frac{(n + 1)!}{(n + 1)!}

= 1

Das entspricht dem Wert aus der Definition des Binomialkoeffizienten:

(\begin{matrix} n + 1 \\ n + 1 \end{matrix}) = 1

für alle

n

.

PS @ledum

"führe den Beweis zuerst für festes

k

und damit Induktion über n"

ist nicht wirklich zielführend. Man führt den Beweis für ein BELIEBIGES

k

mit

0 < k \leq n

. Für ein solches

k

kann man auf die Induktionsvoraussetzung zurückgreifen, da dort bereits für alle

k

mit

0 \leq k \leq n

gilt, dass

(\begin{matrix} n \\ k \end{matrix}) = \frac{n!}{k! \cdot (n - k)!}

. Durch die Festlegung, dass in dem eigentlich interessanten Fall

0 < k \leq n

gilt, ist

0 \leq k - 1 < n

und deshalb auch

(\begin{matrix} n \\ k - 1 \end{matrix}) = \frac{n!}{(k - 1)! \cdot (n - (k - 1))!}

bereits erfüllt. Man kann damit nach dem Rückgriff auf die Induktionsvoraussetzung auf die Definition zurückgreifen und so zeigen, dass für

0 < k \leq n

auch die zu beweisende Formel gilt. Der Hinweis auf die Ränder wird in den Fällen 1 und 3 berücksichtigt, denn dort kann nur der erste Teil der Definition greifen.

Frizzem aktiv_icon

17:51 Uhr, 16.11.2015

Vielen Dank!

Sehr hilfreich, und jetzt steig ich da auch komplett durch!

Sehr nett und nochmals danke ! :-)

1268632

1268550

	Status: nicht eingeloggt	Noch nicht registriert?