Vollständige Induktion mit Binomialkoeffizient und zwei Variablen

07.11.2017, 13:44

ahlers

Vollständige Induktion mit Binomialkoeffizient und zwei Variablen

Meine Frage:
Man Zeige für n,m $\begin{eqnarray*} \in \mathbb N_0 \end{eqnarray*}$

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

Meine Ideen:
Induktionsannahme
$\begin{eqnarray*} \sum\limits_{k=0}^{0} \begin{pmatrix} m \\ 0 \end{pmatrix} = \begin{pmatrix} m+1 \\ 0 \end{pmatrix} \end{eqnarray*}$

Ist also richtig ????

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

$\begin{eqnarray*} \sum\limits_{k=0}^{n+1} \begin{pmatrix} m+n+1 \\ n+1 \end{pmatrix} = \begin{pmatrix} m+n+2 \\ n+1 \end{pmatrix} \end{eqnarray*}$

Muss ich das jetzt nur noch mit dem binomialkoeffizient gleichsetzen und bin fertig oder habe ich voher schon einen Fehler gemacht ?

Bin mir vor allem nicht sicher weil ich ja oben zwei variablen habe, aber so wie ich das verstanden habe muss ich bei der vollständigen induktion nur für eine den Induktionsanfang bestimmen oder kann ich auch einfach m bestimmen und wenn ja wie würde ich das machen ?

07.11.2017, 14:27

klarsoweit

Auf diesen Beitrag antworten »

RE: Vollständige Induktion mit Binomialkoeffizient und zwei Variablen

Zitat:

Original von ahlers
Induktionsannahme
$\begin{eqnarray*} \sum\limits_{k=0}^{0} \begin{pmatrix} m \\ 0 \end{pmatrix} = \begin{pmatrix} m+1 \\ 0 \end{pmatrix} \end{eqnarray*}$

Ist also richtig ????

Das heißt nicht "Induktionsannahme", sondern "Induktionsanfang". Und korrekt wäre es so:

$\begin{eqnarray*} \sum\limits_{k=0}^{0} \binom{k+m}{k} = \binom m 0 = 1 = \binom{m+1}{0} \end{eqnarray*}$

Zitat:

Original von ahlers
Induktionsschnitt n $\begin{eqnarray*} \Rightarrow \end{eqnarray*}$ n+1

$\begin{eqnarray*} \sum\limits_{k=0}^{n+1} \begin{pmatrix} m+n+1 \\ n+1 \end{pmatrix} = \begin{pmatrix} m+n+2 \\ n+1 \end{pmatrix} \end{eqnarray*}$

Das heißt "Induktionsschritt" und zu zeigen ist dies:

$\begin{eqnarray*} \sum\limits_{k=0}^{n+1} \begin{pmatrix} k+m \\ k \end{pmatrix} = \begin{pmatrix} m+n+2 \\ n+1 \end{pmatrix} \end{eqnarray*}$

08.11.2017, 02:49

ahlerss

Auf diesen Beitrag antworten »

Vollständige Induktion mit Binomialkoeffizient und zwei Variablen
Ah ok danke, so weit so gut. Für meinen Beweis muss ich jetzt also das ganze nach

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

umformen und dann zeigen das es das gleiche ist oder nicht ?
Das habe ich versucht indem ich das ganze so lange aufgelöst habe bis ich nichts mehr gefuden habe hab aber nichts sinvolles raus bekommen:

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

Bin mir aber auch bei der rechten seite über dem Burchstrick nicht wirklich sicher was aus dem $\begin{eqnarray*} (m+k+2)! \end{eqnarray*}$ wird, bei $\begin{eqnarray*} (m+2)! \end{eqnarray*}$ wäre es ja ganz klar $\begin{eqnarray*} m!*(m+1)*(m+2) \end{eqnarray*}$ aber wie ist das da mit dem k drin wird das so gemacht wie ich das gemacht habe oder wird das : $\begin{eqnarray*} m!*(m+1)*(m+2)*(k+1)*(k+2) \end{eqnarray*}$ oder was ganz anderes ?

08.11.2017, 08:37

klarsoweit

Auf diesen Beitrag antworten »

RE: Vollständige Induktion mit Binomialkoeffizient und zwei Variablen

Zitat:

Original von ahlerss
Für meinen Beweis muss ich jetzt also das ganze nach

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

umformen und dann zeigen das es das gleiche ist oder nicht ?

Ich weiß jetzt nicht, wie du auf diese Gleichung gekommen bist. verwirrt

Beim Beweis der Gleichung $\begin{eqnarray*} \sum\limits_{k=0}^{n+1} \binom{k+m}{k} = \binom{m+n+2}{n+1} \end{eqnarray*}$ fängst du am besten mit der linken Seite an und ziehst den letzten Summanden aus der Summe. Dann kannst du die Induktionsvoraussetzung nutzen.

Neue Frage »

Antworten »

Vollständige Induktion mit Binomialkoeffizient und zwei Variablen

Verwandte Themen