Vollständige Induktion + Binomialkoeffizient

09.11.2015, 23:54

Rbn

Vollständige Induktion + Binomialkoeffizient

Guten Abend ihr Lieben!
Hier kommt von mir aus eine reine Verständnisfrage, nachdem ich grade nach vielen Versuchen doch einen Erfolg beim Beweis hatte.

Zum Kontext:

Es galt den Beweis von

$\begin{align*} \binom{n+1}{k}=\binom{n}{k-1}+\binom{n}{k} \end{align*}$
$\begin{align*} \forall n\in \mathbb{N} \end{align*}$ zu führen.

Mein Vorgehen (Absichtlich so kleinschrittig, nur für den Fall, dass ihr doch noch einen Fehler in meiner Logik entdeckt) Augenzwinkern

:
Induktionsanfang:
$\begin{align*} \binom{2}{k}\stackrel{!}{=} \binom{1}{k-1}+\binom{1}{k} \\<br /> <=> \ \frac{2}{k!(-k)!(2-k)(1-k)}=\frac{2}{k!(2-k)!}\stackrel{!}{=}\frac{1}{(k-1)!(2-k)!}+\frac{1}{k!(1-k)!} \\= \frac{1}{\frac{k!}{k}(2-k)(1-k)(-k)!} + \frac{1}{k!/(-k)!(1-k)} = \frac{k}{k!(2-k)(1-k)(-k)!}+\frac{2-k}{k!(-k)!(1-k)(2-k)}\\ =\frac{2}{k!(-k)!(2-k)(1-k)}<br /> \end{align*}$

Als ich den abgefeiert habe, habe ich behautet, dass wenn $\begin{align*} \frac{(n+1)!}{k!(n+1)-k)!}=\frac{n!}{(k-1)!(n-k+1)!+\frac{n!}{k!(n-k)!}} \end{align*}$ für n gilt, dass die Aussage auch für n+1 gelten muss. Ab hier bin ich unsicher. Ich habe (diesmal) die letzte Gleichung mit $\begin{align*} \frac{n+2}{n+2-k} \end{align*}$ multipliziert, da ich ja auf $\begin{align*} \frac{(n+2)!}{k!((n+2)-k)!} \end{align*}$ kommen will. Da kam mir der folgende Gedanke: Wäre es nun wichtig, ob ich von der Behauptung, dass es für n+1 gilt auf die Gleichung für die Gültigkeit von n komme (also quasi rückwärts) oder ist es ausschließlich möglich von n aus umzuformen, sodass man auf die Behauptung mit n+1 kommt. Ich frage, weil es mir ,,rückwärts" manchmal leichter fällt. (Beispielsweise bei dem Beweis von $\begin{align*} \sum \limits ^n _{k=1} (k \cdot k!)\stackrel{!}{=}(n+1)!-1 \end{align*}$ )

Wenn jemand eher an dem ,,Beispiel" interessiert ist, als an der Frage: Hier der Rest des Beweises:

$\begin{align*} \frac{(n+1)!}{k!(n+1)-k)!}\stackrel{!}{=}\frac{n!}{(k-1)!(n-k+1)!}+\frac{n!}{k!(n-k)!} \ | \cdot \frac{n+2}{n+2-k} \\<br /> \frac{(n+2)!}{k!(n+2-k)!}\stackrel{!}{=} \frac{\frac{(n+2)!}{n+1}}{(k-1)!(n-k+2)!}+\frac{\frac{(n+2)!}{n+1}}{\frac{k!(n-k+2)!}{n+1-k}}\\ =\frac{(n+2)!}{(n+1)(k-1)!(n-k+2)!}+\frac{(n+2)!(n-k+1)}{(n+1)k!(n-k+2)!}=\frac{(n+2)!(k+n-k+1)}{(n+1)k!(n-k+2)!}=\frac{(n+2)!}{k!(n-k+2)!} \end{align*}$

Euch schonmal noch einen schönen Abend!

10.11.2015, 08:49

klarsoweit

Auf diesen Beitrag antworten »

RE: Vollständige Induktion + Binomialkoeffizient

Zitat:

Original von Rbn
Es galt den Beweis von

$\begin{align*} \binom{n+1}{k}=\binom{n}{k-1}+\binom{n}{k} \end{align*}$
$\begin{align*} \forall n\in \mathbb{N} \end{align*}$ zu führen.

Und warum machst du das mit vollständiger Induktion und nicht direkt mit einem Einzeiler?

$\begin{eqnarray*} \binom{n}{k-1} + \binom n k = \frac{n!}{(k-1)! \cdot (n - k+1)!} + \frac{n!}{k! \cdot (n-k)!} = \frac{k \cdot n!}{k! \cdot (n+1 - k)!} + \frac{(n+1-k) \cdot n!}{k! \cdot (n+1-k)!} = \frac{k \cdot n! + (n+1-k) \cdot n!}{k! \cdot (n+1 - k)!} = \frac{(n+1)!}{k! \cdot (n+1 - k)!} = \binom{n+1}{k} \end{eqnarray*}$

10.11.2015, 08:57

Rbn

Auf diesen Beitrag antworten »

Guten Morgen Klarsoweit!

Ich mache es mit der VI, weil die Aufgabenstellung wörtlich lautet: ,,Zeigen sie mit der Vollständigen Induktion, dass die Aussage gilt."

Da komme ich um diese, doch recht üppige Rechnung kaum herum :/

Liegt vermutlich daran, dass wir die VI erst letzte Vorlesung eingeführt haben. Ich vermute, dass der Prof. uns das so lange machen lässt, bis wir solche beweise Nachts beten können.

10.11.2015, 09:18

klarsoweit

Auf diesen Beitrag antworten »

RE: Vollständige Induktion + Binomialkoeffizient
So ein Blödsinn. Nun denn, wenn es der Prof unbedingt haben will. unglücklich

Irgendwie verstehe ich nicht, wie du hier beim Induktionsanfang:

Zitat:

Original von Rbn
$\begin{align*} <=> \frac{2}{k!(-k)!(2-k)(1-k)}=\frac{2}{k!(2-k)!}\stackrel{!}{=}\frac{1}{(k-1)!(2-k)!}+\frac{1}{k!(1-k)!} \end{align*}$

auf den ersten Bruch kommst?

10.11.2015, 09:33

Rbn

Auf diesen Beitrag antworten »

Du sprichst mir aus der Seele Ups

Der eigentliche Induktionsanfang ist der zweite Bruch. Den ersten habe ich daneben geschrieben, weil mir der Bruch in der Form einfacher und ,,verständlicher" erschien, da ich $\begin{align*} (2-k)! \end{align*}$ nicht so praktisch (oder besser gesagt, ich kann mir unter dem ersten Term irgendwie nicht so richtig was vorstellen) finde wie $\begin{align*} (2-k)(1-k)(-k)! \end{align*}$ . Auf den zweiten Bruch kam ich, weil ich als Induktionsanfang n=1 gewählt habe und in der gegebenen Gleichung (n+1) stand. Demzufolge kann ich hier die zwei für n einsetzen.

Aber nochmal zu der anderen Frage:
Ist es relevant ob ich von der Behauptung, dass eine Aussage für n+1 gilt auf n schließe oder es umgekehrt mache? Solange der Schluss richtig ist, müsste es doch nicht von allzugroßer Bedeutung sein oder?

10.11.2015, 09:49

klarsoweit

Auf diesen Beitrag antworten »

Zitat:

Original von Rbn
Den ersten habe ich daneben geschrieben, weil mir der Bruch in der Form einfacher und ,,verständlicher" erschien, da ich $\begin{align*} (2-k)! \end{align*}$ nicht so praktisch (oder besser gesagt, ich kann mir unter dem ersten Term irgendwie nicht so richtig was vorstellen) finde wie $\begin{align*} (2-k)(1-k)(-k)! \end{align*}$ .

Also ich finde das unpraktisch. Was soll man sich unter (-k)! vorstellen, wenn z.B. k=1 ist?

Erweitere in
$\begin{align*} \frac{2}{k!(2-k)!}\stackrel{!}{=}\frac{1}{(k-1)!(2-k)!}+\frac{1}{k!(1-k)!} \end{align*}$
den 1. Bruch der rechten Seite mit k und den 2. Bruch mit (2-k) und schon kommt die linke Seite raus.

Zitat:

Original von Rbn
Ist es relevant ob ich von der Behauptung, dass eine Aussage für n+1 gilt auf n schließe oder es umgekehrt mache? Solange der Schluss richtig ist, müsste es doch nicht von allzugroßer Bedeutung sein oder?

Solange du Äquivalenzumformungen machst, ist das ok. Allerdings muß man dann auch peinlich darauf achten. smile

10.11.2015, 10:06

Rbn

Auf diesen Beitrag antworten »

Da ist nunmal jeder anders Augenzwinkern

Okay, ich gebe zu: Dein Ansatz mit dem Erweitern ist deutlich einfacher, als meiner Freude

$\begin{align*} \frac{1}{(k-1)!(2-k)!}+\frac{1}{k!(1-k)!}=\frac{k}{k!(2-k)!}+\frac{2-k}{k!(2-k)!}=\frac{k-k+2}{k!(2-k)!}=\frac{2}{k!(2-k)!} \end{align*}$

So stimmt das, würde ich sagen. Ist der Rest des Beweises denn soweit ,,gut"? Oder hab ich es mir da zu kompliziert gemacht?

10.11.2015, 10:16

klarsoweit

Auf diesen Beitrag antworten »

In deinem Induktionsschritt hast du an keiner Stelle die Induktionsvoraussetzung verwendet, sondern die Behauptung letztlich direkt gezeigt (wie ich in meinem Einzeiler). Der Sinn eines Induktionsbeweises wäre aber schon, daß man da auch die Induktionsvoraussetzung irgendwie einbaut. Augenzwinkern

Neue Frage »

Antworten »

Vollständige Induktion + Binomialkoeffizient

Verwandte Themen