Vollständige Induktion mit Binomialkoeffizienten

29.07.2012, 20:14

McDolan

Auf diesen Beitrag antworten »

Vollständige Induktion mit Binomialkoeffizienten

Hallo zusammen!
Ich habe da ein Problem mit einer Übungsaufgabe.
Ich soll folgendes mit der vollständigen Induktion beweisen:
$\begin{eqnarray*} \sum\limits_{i=0}^n \begin{pmatrix} i+k-1 \\ k-1 \end{pmatrix} = \begin{pmatrix} n+k \\ k \end{pmatrix} (n, k \in \mathbb N ) \end{eqnarray*}$

Schon der Induktionsanfang ist mir da zuviel... habe folgendermaßen angefangen:
$\begin{eqnarray*} n = 0, k = 1 \end{eqnarray*}$
$\begin{eqnarray*} \sum\limits_{i=0}^0 \begin{pmatrix} i+k-1 \\ k-1 \end{pmatrix} = \begin{pmatrix} n+k \\ k \end{pmatrix} \end{eqnarray*}$

Dadurch erhalte ich dann bei beiden Seiten später 1, links ist dann:
$\begin{eqnarray*} \begin{pmatrix} 0 \\ 0 \end{pmatrix} \end{eqnarray*}$ und rechts $\begin{eqnarray*} \begin{pmatrix} 1 \\ 1 \end{pmatrix} \end{eqnarray*}$ , was doch beides 1 ergibt, wenn ich mich nicht vollkommen täusche?
Ist das bereits falsch? Ich geb zu, die anderen Aufgaben waren mit nur einer Variable versehen, da war mir direkt klar, wie ich da angehen soll, hier bin ich mir da eher unsicher.

Habe dennoch mal weiter gemacht;
Induktionsvorraussetzung: Die Behauptung gelte für n=0, k=1.

Und beim Induktionsschritt bin ich gescheitert:
$\begin{eqnarray*} k \Rightarrow k+1, n \Rightarrow n+1 \end{eqnarray*}$
$\begin{eqnarray*} \sum\limits_{i=0}^n \begin{pmatrix} i+(k+1)-1 \\ (k+1)-1 \end{pmatrix} = \begin{pmatrix} (n+1)+(k+1) \\ (k+1) \end{pmatrix} \end{eqnarray*}$

$\begin{eqnarray*} \sum\limits_{i=0}^n \begin{pmatrix} i+(k+1)-1 \\ (k+1)-1 \end{pmatrix} + \begin{pmatrix} (n+1)+(k+1)-1 \\ (k+1)-1 \end{pmatrix} = \begin{pmatrix} (n+1)+(k+1) \\ (k+1) \end{pmatrix} \end{eqnarray*}$

Und ab hier ist Schluss... ich kann ja nicht auf die Induktionsvorraussetzung zurückgreifen, da das (k+1) stört. Ich glaub ich hab den Anfang schon direkt falsch, kann das?

Wär auf einen Denkanstoß echt froh, häng hier schon seit Stunden an der Aufgabe...

29.07.2012, 22:41

Stratokrat

Auf diesen Beitrag antworten »

Hallo McDolan,

bist du sicher, dass du nicht irgend etwas falsch abgeschrieben oder eine Bedingung vergessen hast?
Wenn ich mir die zu beweisende Gleichung anschaue, so sieht sich für mich einfach falsch und damit nicht zu beweisen aus.

Gruß,
Stratokrat

29.07.2012, 23:11

carm561

Auf diesen Beitrag antworten »

Reicht nicht die Induktion nach n? Zeige als Induktionsvoraussetzung die Beh für n=0 (oder n=1, je nachdem, wie die natürlichen Zahlen definiert wurden und alle k). Dann gilt nach Inuktionsvorausssetzung die Beh für n und alle k und du musst nur den Übergang n->n+1 machen.

30.07.2012, 08:53

Alive-and-well

Auf diesen Beitrag antworten »

Hallo,

zunächst mal die Aussage ist korrekt!

Dann: ich kenne das nur so, dass man die Induktion entweder über n oder k macht!
Du willst ja zeigen, dass die "Formel" für alle n bei beliebigen k gültig ist!

Also musst du im Ind.-Anfang mit n= 0 prüfen und mit k rechnen (also dem Buchstaben).

Und im Ind-Schluss von n-> n+1 gehen!

Glück Auf!

30.07.2012, 18:47

McDolan

Auf diesen Beitrag antworten »

Erstmals danke an euch alle für eure Hilfsbereitschaft. smile

smile

@Stratokrat:
Wie Alive-and-well schon sagte, die Aussage ist wahr. Hätte ich eventuell noch erwähnen sollen, habs irgendwie total vergessen. Hab allerdings nochmal die Aufgabe angeschaut und verglichen, allerdings keinen Fehler gemacht, als ich sie hier reingeschrieben hab. Bedienungenhab ich auch nicht vergessen, die Aufgabenstellung war legendlich "Beweisen Sie:" mit der oben genannten Aufgabe.

@carm561 und Alive-and-well:
Ah! Tatsächlich, das könnte echt gehen. Dann wäre ja:
$\begin{eqnarray*} n = 0 \end{eqnarray*}$

$\begin{eqnarray*} \sum\limits_{i=0}^0 \begin{pmatrix} i+k-1 \\ k-1 \end{pmatrix} = \begin{pmatrix} 0+k \\ k \end{pmatrix} \end{eqnarray*}$

$\begin{eqnarray*} \begin{pmatrix} 0+k-1 \\ k-1 \end{pmatrix} = \begin{pmatrix} k \\ k \end{pmatrix} \end{eqnarray*}$

$\begin{eqnarray*} \begin{pmatrix} k-1 \\ k-1 \end{pmatrix} = \begin{pmatrix} k \\ k \end{pmatrix} \end{eqnarray*}$
Das war am Anfang ein bisschen verwirrend, dachte zuerst das wäre falsch, durch die alternative Schreibweise und einpaar Testwerte hat sich das ganze jedoch als gleich herausgestellt. Dadurch wäre dann ja der Induktionsanfang bewiesen!

Induktionsvorraussetzung:
Die Behauptung gelte für $\begin{eqnarray*} n = 0, k \in \mathbb N \end{eqnarray*}$

Induktionsschritt:
$\begin{eqnarray*} n \Rightarrow n+1 \end{eqnarray*}$

$\begin{eqnarray*} \sum\limits_{i=0}^n \begin{pmatrix} i+k-1 \\ k-1 \end{pmatrix} = \begin{pmatrix} (n+1)+k \\ k \end{pmatrix} \end{eqnarray*}$

$\begin{eqnarray*} \sum\limits_{i=0}^n \begin{pmatrix} i+k-1 \\ k-1 \end{pmatrix} + \begin{pmatrix} (n+1)+k-1 \\ k-1 \end{pmatrix} = \begin{pmatrix} (n+1)+k \\ k \end{pmatrix} \end{eqnarray*}$

Laut Ind.-Vorraussetzung gilt dann:
$\begin{eqnarray*} \begin{pmatrix} n+k \\ k \end{pmatrix} + \begin{pmatrix} (n+1)+k-1 \\ k-1 \end{pmatrix} = \begin{pmatrix} (n+1)+k \\ k \end{pmatrix} \end{eqnarray*}$

Soweit sogut... ab hier wirds hässlich. Weiter wüsste ich nicht, wie mans rechnet, ich kann den Binomialkoeffizienten ja auch anders schreiben, was ich dann gemacht hab.
$\begin{eqnarray*} \frac{(n+k)!}{k!} + \frac{(n+1+k)!}{(k-1)!*(n+1+k-(k-1))!} = \frac{(n+1+k)!}{k!*(n+1+k-k)!} \end{eqnarray*}$

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

So einpaar Faktoren sind ja richtig, aber da stört noch verdammt viel... was mach ich denn da? Wollt den ersten Bruch mit den Nenner des zweiten erweitern, nur kommt da nichts hilfreiches raus...

30.07.2012, 18:56

Alive-and-well

Auf diesen Beitrag antworten »

Zitat:

Original von McDolan

Laut Ind.-Vorraussetzung gilt dann:
$\begin{eqnarray*} \begin{pmatrix} n+k \\ k \end{pmatrix} + \begin{pmatrix} (n+1)+k-1 \\ k-1 \end{pmatrix} = \begin{pmatrix} (n+1)+k \\ k \end{pmatrix} \end{eqnarray*}$

Soweit sogut... ab hier wirds hässlich. Weiter wüsste ich nicht, wie mans rechnet, ich kann den Binomialkoeffizienten ja auch anders schreiben, was ich dann gemacht hab.
$\begin{eqnarray*} \frac{(n+k)!}{k!} + \frac{(n+1+k)!}{(k-1)!*(n+1+k-(k-1))!} = \frac{(n+1+k)!}{k!*(n+1+k-k)!} \end{eqnarray*}$

Nicht nur hässlich auch falsch Augenzwinkern

Augenzwinkern

$\begin{eqnarray*} \begin{pmatrix} n+k \\ k \end{pmatrix} = \frac{(n+k)!}{k!n!} \neq \frac{(n+k)!}{k!} \end{eqnarray*}$
und
$\begin{eqnarray*} \begin{pmatrix} n+1+k-1 \\ k-1 \end{pmatrix} = \begin{pmatrix} n+k \\ k-1 \end{pmatrix} = \frac{(n+k)!}{(k-1)!(n+1)!} \end{eqnarray*}$

Du musst also noch zeigen,
$\begin{eqnarray*} \frac{(n+k)!}{k!} + \frac{(n+k)!}{(k-1)!(n+1)!} = \frac{(n+k+1)!}{k! (n+1)!} \end{eqnarray*}$

Anzeige

30.07.2012, 20:20

carm561

Auf diesen Beitrag antworten »

@Alive-and-well: Sollte der erste Summand in der letzten Zeile nicht $\begin{eqnarray*} \frac{(n+k)!}{k!n!} \end{eqnarray*}$ sein? verwirrt

verwirrt

30.07.2012, 20:49

Valdas

Auf diesen Beitrag antworten »

Zitat:

Original von McDolan

Induktionsschritt:
$\begin{eqnarray*} n \Rightarrow n+1 \end{eqnarray*}$

$\begin{eqnarray*} \sum\limits_{i=0}^n \begin{pmatrix} i+k-1 \\ k-1 \end{pmatrix} = \begin{pmatrix} (n+1)+k \\ k \end{pmatrix} \end{eqnarray*}$

Das ist falsch!

Und im folgenden geht's ziemlich drunter und drüber.
Vor allem wird überhaupt nicht klar was Du mit der ganzen Rechnerei überhaupt zeigen willst.

Unter der Voraussetzung, dass die zu zeigende Aussage für $\begin{eqnarray*} n\in\mathbb N \end{eqnarray*}$ gilt willst Du doch folgern, dass sie auch für $\begin{eqnarray*} n+1 \end{eqnarray*}$ gilt. Also setzt Du im IS sinnvollerweise wie folgt an:

$\begin{eqnarray*} \sum_{i=0}^{n+1}{i+k-1\choose k-1}=\underbrace{\sum_{i=0}^n{i+k-1\choose k-1}}_{={n+k \choose k}\text{lt. IV}}+{n+k \choose k-1}={n+k \choose k}+{n+k \choose k-1}=\ldots \end{eqnarray*}$

30.07.2012, 23:21

McDolan

Auf diesen Beitrag antworten »

@Alive-and-well
Uoh, das meinte ich mit hässlich Big Laugh

Big Laugh

Diese Schreibweise hat mich echt nerven gekostet, hätte hier jedoch nie im Leben den Fehler gefunden. Danke, hast natürlich vollkommen recht und seh jetzt auch meine Fehler.

@Valdas
Wieso ist der 2. Summand $\begin{eqnarray*} \begin{pmatrix} n+k \\ k-1 \end{pmatrix} \end{eqnarray*}$ und nicht $\begin{eqnarray*} \begin{pmatrix} n+1+k \\ k-1 \end{pmatrix} \end{eqnarray*}$ ? Wenn ich zeigen will, dass sie für $\begin{eqnarray*} n+1 \end{eqnarray*}$ gilt, müsste ich doch alle $\begin{eqnarray*} n \end{eqnarray*}$ zu $\begin{eqnarray*} n+1 \end{eqnarray*}$ werden?

Hab das mal versucht weiterzuführen, allerdings ohne Erfolg...
$\begin{eqnarray*} \frac{(n+k)!}{k!n!} + \frac{(n+k)!}{(k-1)!(n+1)!} = \frac{(n+k+1)!}{k! (n+1)!} \end{eqnarray*}$

$\begin{eqnarray*} \frac{(n+k)!}{k!n!} + \frac{(n+k)!*k!}{(k-1)!*n!*(n+1)*k!} = \frac{(n+k+1)!}{k! (n+1)!} \end{eqnarray*}$
Den 2. Summanden mit k! erweitert und das (n+1) aus der Fakultät herausgezogen

$\begin{eqnarray*} \frac{(n+k)!*(n+1)*(k-1)!}{k!n!*(k-1)!*(n+1)} + \frac{(n+k)!*k!}{(k-1)!*n!*(n+1)*k!} = \frac{(n+k+1)!}{k! (n+1)!} \end{eqnarray*}$
Den 1. Summanden mit (k-1)! und (n+1) erweitert

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

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

$\begin{eqnarray*} \frac{(n+1+k)!*(k-1)!+(n+k)!*k!}{k!(n+1)!*(k-1)!}= \frac{(n+k+1)!}{k! (n+1)!} \end{eqnarray*}$
Und hier ist Schluss..
Ich mach bestimmt wieder irgendwas total verkehrt, nich? (Nagut, muss ja, sonst würd ja das richtige rauskommen) Bin mittlerweile am verzweifeln...

30.07.2012, 23:47

carm561

Auf diesen Beitrag antworten »

Der zweite Summand ergibt sich, wenn du dir den letzten Term der Summe
$\begin{eqnarray*} \sum_{i=0}^{n+1}{i+k-1\choose k-1} \end{eqnarray*}$ anschaust, also i=n+1 setzt.

Bist bei deinen Umformungen tatsächlich ein wenig ins Unterholz gekommen Augenzwinkern

Augenzwinkern

Überleg dir zunächst mal, was der Hauptnenner bei
$\begin{eqnarray*} \frac{(n+k)!}{k!n!} + \frac{(n+k)!}{(k-1)!(n+1)!} \end{eqnarray*}$ ist; du hast ein bisschen großzügig erweitert (Tipp k!=(k-1)!*k, analog für (n+1)!)

Das war nicht falsch, macht es aber ein wenig unhandlich. Der Fehler passiert beim Übergang zur vorletzten Zeile: $\begin{eqnarray*} (n+k)!(n+1)\neq (n+1+k)! \end{eqnarray*}$

31.07.2012, 00:00

Valdas

Auf diesen Beitrag antworten »

Zitat:

Original von McDolan
@Valdas
Wieso ist der 2. Summand $\begin{eqnarray*} \begin{pmatrix} n+k \\ k-1 \end{pmatrix} \end{eqnarray*}$ und nicht $\begin{eqnarray*} \begin{pmatrix} n+1+k \\ k-1 \end{pmatrix} \end{eqnarray*}$ ?

Der letzte Summand der Ausgangssumme (also für i=n+1) lautet

$\begin{eqnarray*} {n+1+k-1\choose k-1}={n+k\choose k-1}. \end{eqnarray*}$

Jetzt klar?

Ich finde es wenig suggestiv und zudem unnötig aufwändig, zum Zwecke eines Beweises, die Behauptung per Äquivalenzumformungen auf eine wahre Aussage zurückzuführen.
Das gewünschte Resultat lässt sich hier doch durch elementare Bruchrechnung direkt berechnen.

31.07.2012, 08:58

Alive-and-well

Auf diesen Beitrag antworten »

Zitat:

Original von carm561
@Alive-and-well: Sollte der erste Summand in der letzten Zeile nicht $\begin{eqnarray*} \frac{(n+k)!}{k!n!} \end{eqnarray*}$ sein? verwirrt

verwirrt

ja! Copy+Paste fehler Augenzwinkern

Augenzwinkern

31.07.2012, 09:41

HAL 9000

Auf diesen Beitrag antworten »

Zitat:

Original von Valdas
Das gewünschte Resultat lässt sich hier doch durch elementare Bruchrechnung direkt berechnen.

Wobei anzumerken ist, dass das hier im Induktionsschritt noch nachzuweisende

$\begin{eqnarray*} \binom{n+k}{k} + \binom{n+k}{k-1} = \binom{n+1+k}{k} \end{eqnarray*}$

eh nur das eigentlich wohlbekannte Bildungsgesetz des Pascalschen Dreiecks ist. Sollte jeder schon irgendwann einmal nachweisen, aber man muss es nicht notwendig zigmal tun. Augenzwinkern

Augenzwinkern

31.07.2012, 16:18

McDolan

Auf diesen Beitrag antworten »

Erstmals wieder danke für eure Geduld und Hilfsbereitschaft. smile

smile

@HAL 9000
Oha interessante Info! Habs nicht realisiert, obwohl mir das Pascalsche Dreieck bekannt ist. Dann haben die Aufgaben ja doch etwas mehr Tiefe als ich dachte.

@Valdas und carm561
Ah alles klar, habt natürlich recht, danke an euch beiden. War da wohl irgendwie wieder total geblendet. Kommt wohl vom zuvielen Aufregen (oder einfach wegen meiner Dummheit, eventuell auch beides).
carm561 dein Tipp hat mir doch geholfen, dadurch müsste ich ja wesentlich weniger erweitern:

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

$\begin{eqnarray*} \frac{(n+k)!*(n+1)}{(k-1)!*k*n!*(n+1)} + \frac{(n+k)!*k}{(k-1)!*k*n!*(n+1)} = \frac{(n+k+1)!}{k!(n+1)! } \end{eqnarray*}$
Durch deinen Tipp ist k!=(k-1)!*k, (n+1)!=n!*(n+1), daher muss ich ja nur beim 1. Summanden mit (n+1) erweitern und beim zweiten mit k

$\begin{eqnarray*} \frac{(n+k)!*(n+1)+(n+k)!*k}{(k-1)!*k*n!*(n+1)} = \frac{(n+k+1)!}{k!(n+1)! } \end{eqnarray*}$
Nenner sind gleich, ich kann beides auf einen Bruch schreiben

$\begin{eqnarray*} \frac{(n+k)!*(n+1)+(n+k)!*k}{k!(n+1)!} = \frac{(n+k+1)!}{k!(n+1)! } \end{eqnarray*}$
k!=(k-1)!*k kann ich nun zusammenfassen, genau wie (n+1)!=*n!*(n+1)

$\begin{eqnarray*} \frac{(n+k)!*(n+k+1)}{k!(n+1)!} = \frac{(n+k+1)!}{k!(n+1)! } \end{eqnarray*}$
(n+1) und k kann ich nun zusammenfassen, da beides mit (n+k)! multipliziert wird

$\begin{eqnarray*} \frac{(n+k+1)!}{k!(n+1)!} = \frac{(n+k+1)!}{k!(n+1)! } \end{eqnarray*}$
Müsste nun gehen.

Sofern ich nun alles richtig angewendet hab, hab ichs endlich?

31.07.2012, 16:33

Alive-and-well

Auf diesen Beitrag antworten »

ja, dass passt so
GLückwunsch Augenzwinkern

Augenzwinkern

31.07.2012, 17:00

McDolan

Auf diesen Beitrag antworten »

Zitat:

Original von Alive-and-well
ja, dass passt so
GLückwunsch Augenzwinkern

Augenzwinkern

Ahh ich kann mich echt nicht genug bedanken. Big Laugh

Big Laugh

Danke an euch alle für eure Hilfe!
War echt ne schwere Geburt...

31.07.2012, 19:52

carm561

Auf diesen Beitrag antworten »

Zitat:

Original von McDolan
War echt ne schwere Geburt...

Es ein gesunder Binomialkoeffizient Big Laugh

Big Laugh

1

Verwandte Themen

Die Beliebtesten »

Die Größten »

Die Neuesten »