Binomialkoeffizienten - Vollständige Induktion

26.10.2008, 12:20

Thomas124

Binomialkoeffizienten - Vollständige Induktion

Hallo,

ich hab einfach keine Idee wie ich diese Aufgabe lösen soll:

Zeigen Sie, dass für alle natürlichen Zahlen n und k gilt:

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

Ich denke mal, das soll mit vollständiger Induktion gemacht werden. Hab dann den linken Therm erstmal als Summe geschrieben:

$\begin{eqnarray*} \sum_{k=0}^n~ \begin{pmatrix} n+k \\ k \end{pmatrix} = \begin{pmatrix} n+k+1 \\ k \end{pmatrix} \end{eqnarray*}$

Dann für n = 1 gezeigt, passt, dann für n+1:

$\begin{eqnarray*} \sum_{k=0}^n~ \begin{pmatrix} n+k \\ k \end{pmatrix} + \begin{pmatrix} 2n+1 \\ n+1 \end{pmatrix} = \begin{pmatrix} 2n+2 \\ n+1 \end{pmatrix} \end{eqnarray*}$

Dann den vorderen Teil ersetzt durch die Forderung:

$\begin{eqnarray*} \begin{pmatrix} 2n+1 \\ n \end{pmatrix} + \begin{pmatrix} 2n+1 \\ n+1 \end{pmatrix} = \begin{pmatrix} 2n+2 \\ n+1 \end{pmatrix} \end{eqnarray*}$

Stimmt das bis hierhin?!? Hat jemand eine Idee wie ich jetzt weiter umformen kann??

Vielen Dank!

26.10.2008, 13:52

Thomas124

Auf diesen Beitrag antworten »

Hallo,

ich glaube ich hab es hinbekommen!!

Und zwar mit diesem Additionssatz. Müsste doch so stimmen, oder??

Vielen Dank fürs nachsehen!! :-)

26.10.2008, 14:01

klarsoweit

Auf diesen Beitrag antworten »

RE: Binomialkoeffizienten - Vollständige Induktion

Zitat:

Original von Thomas124
Ich denke mal, das soll mit vollständiger Induktion gemacht werden. Hab dann den linken Therm erstmal als Summe geschrieben:

$\begin{eqnarray*} \sum_{k=0}^n~ \begin{pmatrix} n+k \\ k \end{pmatrix} = \begin{pmatrix} n+k+1 \\ k \end{pmatrix} \end{eqnarray*}$

Das hast du leider falsch gemacht. Richtig wäre:

$\begin{eqnarray*} \sum_{j=0}^k~ \begin{pmatrix} n+j \\ j \end{pmatrix} = \begin{pmatrix} n+k+1 \\ k \end{pmatrix} \end{eqnarray*}$

Und die Induktion geht dann über k.

26.10.2008, 14:09

Thomas124

Auf diesen Beitrag antworten »

hmmm, ok...

Aber das ändert doch an der eigentlichen Lösung nichts, oder?

26.10.2008, 14:11

Mathewolf

Auf diesen Beitrag antworten »

Nein, das ist leider nicht so ganz richtig, denn
$\begin{eqnarray*} \begin{pmatrix} n \\ 0 \end{pmatrix} + \begin{pmatrix} n+1 \\ 1 \end{pmatrix} + ... + \begin{pmatrix} n+k \\ k \end{pmatrix} = \begin{pmatrix} n+k+1 \\ k \end{pmatrix} = \sum_{i=0}^k{n+i\choose i} \end{eqnarray*}$
Somit lautet die Gleichung
$\begin{eqnarray*} \sum_{i=0}^k{n+i\choose i} = {n+k+1\choose k} \end{eqnarray*}$

Induktionsanfang (k=0):
$\begin{eqnarray*} \sum_{i=0}^0{n+i\choose i} = {n+0+1\choose 0} \end{eqnarray*}$
$\begin{eqnarray*} \Rightarrow\ {n\choose 0}=1={n+1\choose 0}. \end{eqnarray*}$

Und jetzt mach an dieser Stelle weiter mit dem Induktionsschritt ...

26.10.2008, 14:29

Thomas124

Auf diesen Beitrag antworten »

jop, ok... Aber wenn ich jetzt nicht völig auf dem Schlauch stehe ändert das doch an der eigentlichen Rechnung nichts, oder?? Ich hab es mal neu gemacht (siehe Anhang)

26.10.2008, 14:31

klarsoweit

Auf diesen Beitrag antworten »

Die Rechnung ist ok. Am eigentlichen Prinzip hat sich nichts geändert, aber eine andere Rechnung ist das schon. smile

26.10.2008, 14:33

Thomas124

Auf diesen Beitrag antworten »

hehe, stimmt schon ;-)

Vielen vielen Dank!! :-)

Neue Frage »

Antworten »

Binomialkoeffizienten - Vollständige Induktion

Verwandte Themen