Vollständige Induktion

13.11.2006, 16:18

SilverBullet

Vollständige Induktion

Hallo,

habe ein riesen Problem mit folgender Aufgabe :

Zeigen sie mittels Induktion :

$\begin{eqnarray*} \binom {m+n} {k} = \sum_{i=0}^k~\binom m i \binom {n} {k-i} \end{eqnarray*}$

Können sie diese Gleichung auch kombinatorisch verdeutlichen ?

So also mein Versucht mit der Induktion ist kläglich gescheitert unglücklich

Erst große Frage : Was muss ich null setzen ?

Mein Versucht sieht so aus :

Habe erstmal so umgeformt

$\begin{eqnarray*} \frac {m+n!}{k!((m+n)-k)!)} = \sum_{i=0}^k~\left(\frac {m!}{i!(m-i)!}\right) \left(\frac {n!}{(k-i)!(n-(k-i))!}\right) \end{eqnarray*}$

Mein Induktionsanfang : k =0

Dann folgt $\begin{eqnarray*} \frac {(m+n)!} {(m+n)!} = \sum_{i=0}^0~\frac {m!} {m!} \frac {n!} {n!} \end{eqnarray*}$

Also 1 = 1 Und das stimmt dann so hoffe ich...

Nun weiß ich aber nicht wie ich den Induktionsschritt machen soll unglücklich

13.11.2006, 18:28

tigerbine

Auf diesen Beitrag antworten »

RE: Vollständige Induktion
Eine Klammer vergessen bei, (m+n)!.

Wie, was Null setzten??? Induktion über k, oder?

Induktionsanfang, k=0

$\begin{eqnarray*} \frac {(m+n)!} {0!(m+n)!} = \sum_{i=0}^0~\left(\frac {m!} {0!m!}\cdot \frac {n!} {0!n!}\right) \end{eqnarray*}$

$\begin{eqnarray*} 1 =1 \end{eqnarray*}$

Induktionsbehauptung, sei

$\begin{eqnarray*} \binom {m+n} {k} = \sum_{i=0}^k~\binom m i \binom {n} {k-i} \end{eqnarray*}$

Induktionsschluss für k+1

Dabei müssen die Binomialkoeffizienten auch noch definiert sein, also

$\begin{eqnarray*} k+1 \leq \min{(m,n)} \end{eqnarray*}$ , oder???

Zu zeigen:

$\begin{eqnarray*} \binom {m+n} {k+1} = \sum_{i=0}^{k+1}~\binom m i \binom {n} {(k+1)-i} \end{eqnarray*}$

Gruß,
tigerbine Wink

13.11.2006, 19:36

SilverBullet

Auf diesen Beitrag antworten »

re
Genau da hab ich mein Problem..

Zitat:

Zu zeigen:

$\begin{eqnarray*} \binom {m+n} {k+1} = \sum_{i=0}^{k+1}~\binom m i \binom {n} {(k+1)-i} \end{eqnarray*}$

$\begin{eqnarray*} \frac {m+n!}{(k+1)!((m+n)-(k+1))!} = \sum_{i=0}^{k+1}~\left(\frac {m!}{i!(m-i)!}\right) \left(\frac {n!}{((k+1)-i)!(n-((k+1)-i)!}\right) \end{eqnarray*}$

Ja und nun muss ich doch auf der rechten Seite ein k rausziehen, sodass die Summe nur noch bis k geht oder ?
Weiß da jemand wie ?

mfg
silver

13.11.2006, 21:53

SilverBullet

Auf diesen Beitrag antworten »

re
Habs aufgegeben und über den Beweis den Binomialkoeffizienten gemacht....Falls es doch jemand schafft würd ich mich freunen wenn er mir zeigt wie.

Neue Frage »

Antworten »

Vollständige Induktion

Verwandte Themen