Frage zur Induktion bei Binomialkoeffizienten

20.11.2010, 15:47

_-Alex-_

Auf diesen Beitrag antworten »

Frage zur Induktion bei Binomialkoeffizienten

Hi,

ich habe mal eine Frage zu folgender Aufgabe:
Zeigen sie mit Hilfe von Induktion, dass:
$\begin{eqnarray*} \binom{n}{k} = \binom {n}{n-k} \end{eqnarray*}$

Der Induktionsanfang ist ja n=0, da stimmt das ja, weil 0!=1 also kommt beide Male 1 heraus.
Bei der Induktionsannahme, nehme ich ja an das die Formel für n stimmt.
Jetzt muss ich ja beim Induktionsschritt zeigen, dass:
$\begin{eqnarray*} \binom{n+1}{k} = \binom{n+1}{n+1-k} \end{eqnarray*}$

Ich habe jetzt erstmal gerechnet:
$\begin{eqnarray*} \binom {n+1}{k} = \frac {(n+1)!}{k! \cdot (n+1-k)!} \end{eqnarray*}$
Wenn ich jetzt einfach im Nenner die beiden Faktoren vertauschen würde, was ich ja machen kann und dann sagen würde das ist ja mein gewolltes Ergebnis, wäre das nicht richtig oder? Weil ich würde ja dann keine Induktion machen. Ich müsste also doch weiter rechnen und irgendwann erstmal meine Induktionsannahme reinbringen. Also:
$\begin{eqnarray*} = \frac {(n+1)\cdot n!}{k! \cdot (n+1-k)\cdot (n-k)!}= \frac{n+1}{n+1-k} \cdot \binom {n}{k} = \frac{n+1}{n+1-k} \cdot \binom{n}{n-k} = \frac {(n+1)\cdot n!}{(n+1-k)\cdot (n-k)! \cdot (n-n+k)!}= \frac {(n+1)!}{(n+1-k)\cdot(n-k)!\cdot k!} = \frac {(n+1)!}{(n+1-k)! \cdot k!} = \binom{n+1}{n+1-k} \end{eqnarray*}$

Oder?

MfG

20.11.2010, 17:34

klarsoweit

Auf diesen Beitrag antworten »

RE: Frage zur Induktion bei Binomialkoeffizienten
Im Prinzip ist das richtig. Allerdings entspricht die Rechnung im Induktionsschritt im wesentlichem dem direkten Beweis, so daß man auch auf die Induktion verzichten könnte.

20.11.2010, 17:40

_-Alex-_

Auf diesen Beitrag antworten »

Darum finde ich es ja auch unsinnig, wenn man die Gleichungen einfach schon ohne Induktion und Einsetzen beweisen kann, dass man dann die Induktion anwenden soll, bei den anderen Aufgaben, wird das ganze noch be**********.

21.11.2010, 22:44

_-Alex-_

Auf diesen Beitrag antworten »

1)
Ich hätte noch eine Frage zum Beweis von:
$\begin{eqnarray*} (a+b)^n = \sum_{k=0}^n \binom{n}{k} a^k b^{n-k} \end{eqnarray*}$

Ich habe hier im Internet einen Beweis gefunden, jedoch fand ich $\begin{eqnarray*} \binom {n}{k-1} \end{eqnarray*}$ nicht gut, da für den Fall k=0 ich ja $\begin{eqnarray*} \binom {n}{-1} \end{eqnarray*}$ hätte.

Ich habe es jetzt etwas anders mal versucht, weiß aber nicht ob man das so machen kann, darum wollte ich euch mal fragen:
$\begin{eqnarray*} (a+b)^{n+1} = (a+b)(a+b)^n = (a+b) \cdot \sum_{k=0}^n \binom {n}{k} a^k b^{n-k}= \sum_{k=0}^n (\binom{n}{k} a^{k+1}b^{n-k} + \binom{n}{k} a^k b^{n+1-k} )=b^{n+1} \binom{n}{0} + a^{n+1} \binom{n}{n} + \sum_{k=0}^{n-1} \lbrace \binom{n}{k} + \binom{n}{k+1} \rbrace a^{k+1}b^{n-k} = \end{eqnarray*}$

$\begin{eqnarray*} = b^{n+1} + a^{n+1} + \sum_{k=0}^{n-1} \binom {n+1}{k+1} a^{k+1}b^{n-k} = b^{n+1} + \sum_{k=0}^n \binom{n+1}{k+1} a^{k+1}b^{n-k}= \sum_{k=0}^{n+1} \binom{n+1}{k} a^k b^{n+1-k} \end{eqnarray*}$

Kann ich das so machen?

EDIT:
2)
Ich hab noch eine Aufgabe, bei der ich mir nicht sicher bin, dass man das so machen kann:
Also zu Zeigen ist folgendes:
$\begin{eqnarray*} \binom{n}{k} + \binom{n+1}{k} +...+ \binom {n+l}{k} = \binom {n+l+1}{k+1} - \binom{n}{k+1} \end{eqnarray*}$

Bei der Aufgabe wäre ich jetzt von Hinten sozusagen herangegangen. Also ich hätte nicht gezeigt, dass für n+1 aus der linken Seite die Rechte wird, sondern ich hätte mit der Rechten angefangen. Kann ich das machen?
Meine Rechnung ist folgende:
$\begin{eqnarray*} \binom {n+1+l+1}{k+1} - \binom{n+1}{k+1} = \frac {(n+2+l)!}{(k+1)!(n+1+l-k)!} - \frac {(n+1)!}{(k+1)!(n-k)!}= \frac{(n+2+l)(n+1+l)!}{(k+1)!(n+1+l-k)(n+l-k)!} - \frac {(n+1)n!}{(k+1)!(n-k)(n-k-1)!}= \end{eqnarray*}$

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

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

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

Kann man das auch so machen?

MfG

21.11.2010, 23:44

Manni Feinbein

Auf diesen Beitrag antworten »

Ich hab mir das jetzt nicht genau angeguckt, denn eigentlich bedarf es hier nur der klassischen Rechenregel für Binomialkoeffizienten:

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

Diese kannst Du mal auf Deine Summe auf der linken Seite anwenden:

$\begin{eqnarray*} \sum_{i=0}^l{n+i\choose k}=\sum_{i=0}^l\left[{n+i+1\choose k+1}-{n+i\choose k+1}\right]=\ldots \end{eqnarray*}$

Jetzt einfach mal hingegucken, um die Teleskopsumme zu erkennen und dann steht's doch schon da.

21.11.2010, 23:53

_-Alex-_

Auf diesen Beitrag antworten »

Man soll in der Aufgabe ausdrücklich mit Induktion beweisen, hätte ich vllt noch erwähnen sollen ^^

Anzeige

21.11.2010, 23:58

Manni Feinbein

Auf diesen Beitrag antworten »

Zitat:

Original von _-Alex-_
Man soll in der Aufgabe ausdrücklich mit Induktion beweisen, hätte ich vllt noch erwähnen sollen ^^

Ja und - wo ist das Problem?

22.11.2010, 00:11

_-Alex-_

Auf diesen Beitrag antworten »

Ja dann kann ich doch nicht einfach mal mit den Rechenregeln rumrechnen, sondern muss doch irgendwo meine Induktionsannahme unterbringen

22.11.2010, 00:28

Manni Feinbein

Auf diesen Beitrag antworten »

Zitat:

Original von _-Alex-_
Ja dann kann ich doch nicht einfach mal mit den Rechenregeln rumrechnen

ROFL

Wär Dir das 'Rumrechnen' ohne Rechenregeln lieber?

Jetzt mal im Ernst: Der sogenannte Teleskopsummentrick ist doch im Wesen nichts anderes als Induktion - nur eben ohne den ganzen Klimbim mit IA, IV, etc.

22.11.2010, 00:32

_-Alex-_

Auf diesen Beitrag antworten »

Ich meinte ja nicht ganz ohne Rechenregeln..
Ich hab nur gemeint, dass ich eben wenn die Induktion verlangt ist, auch meine Annahme irgendwo einsetzte. Bei meinem ersten Post hätte ich ja auch einfach im Nenner die Faktoren vertauschen können, aber dann entspricht es ja nicht ganz der Aufgabe.
Was diese Teleskopsumme ist weiß ich nicht.
Aber ich möchte eigentlich nach der Arbeit auch meinen Weg am liebsten angeben, darum ja die Frage ob man das so beweisen kann, wie ich es getan habe.

22.11.2010, 08:52

klarsoweit

Auf diesen Beitrag antworten »

Zitat:

Original von _-Alex-_
Ich habe es jetzt etwas anders mal versucht, weiß aber nicht ob man das so machen kann, darum wollte ich euch mal fragen:
$\begin{eqnarray*} ... = \sum_{k=0}^n (\binom{n}{k} a^{k+1}b^{n-k} + \binom{n}{k} a^k b^{n+1-k} ) = b^{n+1} \binom{n}{0} + a^{n+1} \binom{n}{n} + \sum_{k=0}^{n-1} \lbrace \binom{n}{k} + \binom{n}{k+1} \rbrace a^{k+1}b^{n-k} = \end{eqnarray*}$

Die Umformung ist verdachtsweise falsch oder zumindest so nicht nachvollziehbar. Da mußt du etwas mehr erläutern, was du gemacht hast. Besser wäre es, die linke Summe in 2 Summen aufzuteilen.

Zitat:

Original von _-Alex-_
Ich hab noch eine Aufgabe, bei der ich mir nicht sicher bin, dass man das so machen kann:
Also zu Zeigen ist folgendes:
$\begin{eqnarray*} \binom{n}{k} + \binom{n+1}{k} +...+ \binom {n+l}{k} = \binom {n+l+1}{k+1} - \binom{n}{k+1} \end{eqnarray*}$

Du machst den Induktoinsschritt komplizierter als nötig. Du brauchst doch nur die von Manni Feinbein erwähnte Rechenregel für Binomialkoeffizienten anwenden. Ich fange da mit der linken Seite an:

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

Jetzt kannst du schön die Induktionsvoraussetzung anwenden.

22.11.2010, 11:24

_-Alex-_

Auf diesen Beitrag antworten »

Zitat:

Original von klarsoweit

Zitat:

Original von _-Alex-_
Ich habe es jetzt etwas anders mal versucht, weiß aber nicht ob man das so machen kann, darum wollte ich euch mal fragen:
$\begin{eqnarray*} ... = \sum_{k=0}^n (\binom{n}{k} a^{k+1}b^{n-k} + \binom{n}{k} a^k b^{n+1-k} ) = b^{n+1} \binom{n}{0} + a^{n+1} \binom{n}{n} + \sum_{k=0}^{n-1} \lbrace \binom{n}{k} + \binom{n}{k+1} \rbrace a^{k+1}b^{n-k} = \end{eqnarray*}$

Die Umformung ist verdachtsweise falsch oder zumindest so nicht nachvollziehbar. Da mußt du etwas mehr erläutern, was du gemacht hast. Besser wäre es, die linke Summe in 2 Summen aufzuteilen.

Achja, ich hab da einen Schritt noch vergessen hinzuschreiben. Auseinander gezogen hatte ich sie nämlich.
$\begin{eqnarray*} ...= \sum_{k=0}^n ( \binom{n}{k} a^{k+1}b^{n-k} + \binom{n}{k} a^k b^{n+1-k}) = \sum_{k=0}^n (\binom{n}{k} a^{k+1}b^{n-k} ) + \sum_{k=0}^n ( \binom{n}{k} a^k b^{n+1-k} = b^{n+1} \binom{n}{0} + a^{n+1} \binom{n}{n} + \sum_{k=0}^{n-1} \lbrace (\binom{n}{k} + \binom{n}{k+1} ) a^{k+1}b^{n-k} \rbrace = ... \end{eqnarray*}$

Zu den letzten Schritt bin ich gekommen, indem ich geschaut habe, welche Terme ich zusammenfassen kann, z.B. kommt ja $\begin{eqnarray*} ab^n \end{eqnarray*}$ in beiden Summen vor. Die fasse ich zusammen, klammer sie aus und mach mir eine neue Summe. Die beiden Terme vorne bleiben über. In den weiteren Schritten versuche ich dann diese Terme auch noch in die Summe zu bekommen, ohne dass ein Summand verloren geht.

Zu dem 2. Teil:
Stimmt, das ist wesentlich kürzer und übersichtlicher. Kann ich jetzt dennoch meinen Beweis anbringen ( ist sonst schade um die Arbeitszeit ).

MfG

22.11.2010, 11:42

klarsoweit

Auf diesen Beitrag antworten »

Zitat:

Original von _-Alex-_
In den weiteren Schritten versuche ich dann diese Terme auch noch in die Summe zu bekommen, ohne dass ein Summand verloren geht.

Da ist dann aber auch was schief gegangen. Besser du machst in
$\begin{eqnarray*} b^{n+1} \binom{n}{0} + a^{n+1} \binom{n}{n} + \sum_{k=0}^{n-1} \lbrace (\binom{n}{k} + \binom{n}{k+1} ) a^{k+1}b^{n-k} \rbrace = ... \end{eqnarray*}$
eine Indexverschiebung, so daß die Summe von k=1 bis n geht.

Zitat:

Original von _-Alex-_
Zu dem 2. Teil:
Stimmt, das ist wesentlich kürzer und übersichtlicher. Kann ich jetzt dennoch meinen Beweis anbringen ( ist sonst schade um die Arbeitszeit ).

Tut mir leid, dafür habe ich keine Zeit.

22.11.2010, 16:06

_-Alex-_

Auf diesen Beitrag antworten »

Was genau ist da schief gelaufen, hab das jetzt noch 2 mal durchgeschaut und finde den Wurm nicht.
$\begin{eqnarray*} A= \sum_{k=0}^n \lbrace \binom{n}{k} a^{k+1} b^{n-k} \rbrace= \binom {n}{0} ab^n + \binom{n}{1} a^2 b^{n-1} + \binom{n}{2} a^3 b^{n-2} + ... + \binom{n}{n-2} a^{n-1}b^2 + \binom{n}{n-1}a^nb + \binom{n}{n}a^{n+1} \end{eqnarray*}$

$\begin{eqnarray*} B= \sum_{k=0}^n \lbrace \binom{n}{k} a^{k} b^{n+1-k} \rbrace= \binom{n}{0} b^{n+1} + \binom {n}{1} ab^n + \binom{n}{2} a^2 b^{n-1} + \binom{n}{3} a^3 b^{n-2} + ... + \binom{n}{n-2} a^{n-2}b^3 + \binom{n}{n-1}a^{n-1}b^2 + \binom{n}{n}a^nb \end{eqnarray*}$

Jetzt kann ich doch A+B schreiben als:
$\begin{eqnarray*} \binom {n}{n} a^{n+1} + \binom{n}{0} b^{n+1} + (\binom{n}{0} + \binom{n}{1} ) \cdot ab^n + (\binom{n}{1} + \binom{n}{2} ) \cdot a^2b^{n-k} + (\binom{n}{2} + \binom{n}{3} ) \cdot a^3 b^{n-2} + ... + (\binom{n}{n-2} + \binom{n}{n-1}) \cdot a^{n-1}b^2 + (\binom{n}{n-1} + \binom{n}{n} ) \cdot a^n b \end{eqnarray*}$

Und das müsste doch eigentlich meine Summe sein.

Bei der anderen Aufgabe müsste ich eigentlich nur wissen, ob ich bei der Induktion auch von rechts anfangen kann und die linke Seite zeige, das müsste doch eigentlich egal sein oder?

22.11.2010, 16:39

Manni Feinbein

Auf diesen Beitrag antworten »

Du solltest versuchen Dir diese 'Pünktchen-Schreibweise' abzugewöhnen.

$\begin{eqnarray*} A=\sum_{k=0}^n{n\choose k}a^{k+1}b^{n-k}=\sum_{k=1}^{n+1}{n\choose k-1}a^kb^{n+1-k}=a^{n+1}+\sum_{k=1}^n{n\choose k-1}a^kb^{n+1-k} \end{eqnarray*}$

$\begin{eqnarray*} B=\sum_{k=0}^n{n\choose k}a^kb^{n+1-k}=\sum_{k=1}^n{n\choose k}a^kb^{n+1-k}+b^{n+1} \end{eqnarray*}$

Jetzt kannst Du die Summen zusammenfassen und die bekannte Additionsformel für die Binomialkoeffizienten einbringen und dann steht's schon da.

22.11.2010, 18:25

_-Alex-_

Auf diesen Beitrag antworten »

Aber ist das im Endeffekt nicht das Gleiche, was ich gemacht habe? Ich habe die Summen ja nur ausgeschrieben, weil ich nicht wusste, wo der Fehler sein sollte.

Ich habe noch eine Frage zu der Aufgabe:

Zitat:

Original von _-Alex-_

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

Wie wähle ich hier meinen Induktionsanfang? das k+1 am Ende macht mir zu schaffen, weil wenn ich n=0 wähle, hätte ich ja im Nennern eine Fakultät von einer negativen Zahl stehen. Kann ich dann nicht bei n=0 anfangen oder wie wird das dann gemacht?

22.11.2010, 18:47

klarsoweit

Auf diesen Beitrag antworten »

Man kann auch sehr schön eine Induktion über l (also l wie lachen) machen.

22.11.2010, 19:37

_-Alex-_

Auf diesen Beitrag antworten »

Aber mag nicht nochmal anfangen Big Laugh

Big Laugh

muss morgen abgeben...

Ich hätte jetzt k=0, l=0 und n=1 genommen. Dann würde es zumindest hinhauen, aber weiß ja nicht ob das richtig ist.

23.11.2010, 09:07

klarsoweit

Auf diesen Beitrag antworten »

Zitat:

Original von _-Alex-_
Aber mag nicht nochmal anfangen Big Laugh

Big Laugh

muss morgen abgeben...

Soviel Aufwand ist das nicht. Der ganze beweis ist in 3 Zeilen hingeschrieben. Wer mehr braucht, ist ein Umstandskrämer.

Zitat:

Original von _-Alex-_
Ich hätte jetzt k=0, l=0 und n=1 genommen. Dann würde es zumindest hinhauen, aber weiß ja nicht ob das richtig ist.

So geht es nicht. Du kannst nur für eine Variable einen Anfang nehmen (0 oder 1). Alle anderen Variablen können und dürfen nicht festgelegt werden.

1

Verwandte Themen

Die Beliebtesten »

Die Größten »

Die Neuesten »