Vollständige Induktion mit Binomialkoeffizienten

Neue Frage »

26.10.2011, 11:54	fermat106	Auf diesen Beitrag antworten »
Vollständige Induktion mit Binomialkoeffizienten Meine Frage: Hallo Leute, ich wäre euch für eure Hilfe dankbar. Beweise: $\begin{eqnarray} <br /> \sum\limits_{k=0}^n \begin{pmatrix} m+k\\ m \end{pmatrix} = \begin{pmatrix} m+n+1 \\ m+1 \end{pmatrix}<br /> <br /> \end{eqnarray}$ Meine Ideen: Die Induktionsvoraussetzung ist klar. Der Induktionsschluss ist mir nicht mehr klar. $\begin{eqnarray} <br /> \sum\limits_{k=1}^{n+1} \begin{pmatrix} m+k\\ m \end{pmatrix} =\begin{pmatrix} m+n+2 \\ m+1 \end{pmatrix} <br /> <br /> \end{eqnarray}$ Nun weiß ich nicht wie ich das Umformunen soll. Mir fehlt jegliche Basis mit Binomialkoeffizienten. Vielen Dank fermat106
26.10.2011, 12:02	Gast11022013	Auf diesen Beitrag antworten »
RE: Vollständige Induktion mit Binomialkoeffizienten Ich schreib das erstmal lesbar hin. $\begin{eqnarray} \sum_{k=0}^{n}\binom{m+k}{m}=\binom{m+n+1}{m+1} \end{eqnarray}$ Du sollst zeigen. daß $\begin{eqnarray} \sum_{k=0}^{n+1}\binom{m+k}{m}=\binom{m+(n+1)+1}{m+1}=\binom{m+n+2}{m+1} \end{eqnarray}$ Nutze dazu die Induktionsvoraussetzung, indem Du schreibst: $\begin{eqnarray} \sum_{k=0}^{n+1}\binom{m+k}{m}=\sum_{k=0}^{n}\binom{m+k}{m}+\binom{m+(n+1)}{m}=\hdots \end{eqnarray}$
26.10.2011, 12:08	fermat106	Auf diesen Beitrag antworten »
RE: Vollständige Induktion mit Binomialkoeffizienten Danke Dennis fürs umschreiben, habe es nun auch rausgefungen. Vielen Dank trotzdem!
26.10.2011, 12:11	Gast11022013	Auf diesen Beitrag antworten »
RE: Vollständige Induktion mit Binomialkoeffizienten Du musst, wie ich im Edit hinzugefügt habe, die Induktionsvoraussetzung nutzen.
26.10.2011, 13:04	fermat106	Auf diesen Beitrag antworten »
RE: Vollständige Induktion mit Binomialkoeffizienten Danke Dennis! Wenn ich die Induktionsvoraussetzung nutze bekomme ich folgende heraus: $\begin{eqnarray} <br /> <br /> \sum\limits_{k=1}^{n+1} \begin{pmatrix} m+k\\ m \end{pmatrix} =\sum\limits_{k=1}^{n} \begin{pmatrix} m+k\\ m \end{pmatrix} + \begin{pmatrix} m+(n+1)+1 \\ m+1 \end{pmatrix} = \begin{pmatrix} m+n+1 \\ m+1 \end{pmatrix} + \begin{pmatrix} m+(n+1)+1 \\ m+1 \end{pmatrix}<br /> <br /> <br /> \end{eqnarray}$ Wie ich die nun zusammenfasse weiß ich aber nicht?
26.10.2011, 13:08	Gast11022013	Auf diesen Beitrag antworten »
RE: Vollständige Induktion mit Binomialkoeffizienten Das ist so nicht korrekt! Der allerletzte Summand stimmt nämlich nicht. Dieser stammt ja aus der Summe auf der linken Gleichungsseite und muss daher $\begin{eqnarray} \binom{m+(n+1)}{m}=\binom{m+n+1}{m} \end{eqnarray}$ heißen.
Anzeige

26.10.2011, 14:41	fermat106	Auf diesen Beitrag antworten »
RE: Vollständige Induktion mit Binomialkoeffizienten Verstehe ich nicht. Wenn ich mir die Gleichung anschaue, dann habe ich im mittleren Teil die Summe n über k (1. Summand), die ich durch die Induktionsvoraussetzung ersetze, wie das getan habe. Der 2. Summand im mittleren Teil bleibt doch einfach nur erhalten. Wo sit mein Denkfehler? Ich verstehe nicht wie du darauf kommst. Ich soll sicherlich das hinschreiben $\begin{eqnarray} <br /> <br /> <br /> <br /> \sum\limits_{k=1}^{n+1} \begin{pmatrix} m+k\\ m \end{pmatrix} =\sum\limits_{k=1}^{n} \begin{pmatrix} m+k\\ m \end{pmatrix} + \begin{pmatrix} m+(n+1)+1 \\ m+1 \end{pmatrix} = \begin{pmatrix} m+n+1 \\ m+1 \end{pmatrix} + \begin{pmatrix} m+n+1 \\ m+1 \end{pmatrix}<br /> <br /> <br /> \end{eqnarray}$ oder so: $\begin{eqnarray} <br /> <br /> <br /> <br /> \sum\limits_{k=1}^{n+1} \begin{pmatrix} m+k\\ m \end{pmatrix} =\sum\limits_{k=1}^{n} \begin{pmatrix} m+k\\ m \end{pmatrix} + \begin{pmatrix} m+n+1 \\ m+1 \end{pmatrix} = \begin{pmatrix} m+n+1 \\ m+1 \end{pmatrix} + \begin{pmatrix} m+n+1 \\ m+1 \end{pmatrix}<br /> <br /> <br /> \end{eqnarray}$ Der zweite würde mehr Sinn machen, allerdings weiß ich trotzdem nicht weiter....
26.10.2011, 14:47	Gast11022013	Auf diesen Beitrag antworten »
$\begin{eqnarray} \sum_{k=0}^{n+1}\binom{m+k}{m}=\sum_{k=0}^{n}\binom{m+k}{m}+\binom{m+n+1}{m} \end{eqnarray}$ Und dies ist nach der Induktionsvoraussetzung $\begin{eqnarray} \binom{m+n+1}{m+1}+\binom{m+n+1}{m} \end{eqnarray}$ , was es nun aufzulösen bzw. auszurechnen gilt. Zu zeigen ist ist, daß dies identisch ist mit $\begin{eqnarray} \binom{m+n+2}{m+1} \end{eqnarray}$ .
26.10.2011, 15:10	fermat106	Auf diesen Beitrag antworten »
Genau, der Schritt ist mir jetzt klar. Allerdings weiß ich nicht wie ich dieses: $\begin{eqnarray} \binom{m+n+1}{m+1}+\binom{m+n+1}{m} \end{eqnarray}$ auflöse bzw. ausrechne? Nutze ich dafür: $\begin{eqnarray} <br /> <br /> <br /> \begin{pmatrix} n \\ k \end{pmatrix} = \frac{n!}{k!(n-k)!} <br /> <br /> \end{eqnarray}$ was dann bedeuten würde: $\begin{eqnarray} <br /> \begin{pmatrix} m+n+1 \\ m+1 \end{pmatrix} = \frac{(m+n+1)!}{(m+1)!((m+n+1)-(m+1))!}<br /> <br /> <br /> <br /> \begin{pmatrix} m+n+1 \\ m \end{pmatrix} = \frac{(m+n+1)!}{(m)!((m+n+1)-(m))!}<br /> <br /> \end{eqnarray*}$ oder liege ich ganz falsch???Ein paar kleinere Auflösungen wären möglich, aber nichts großes. Ich wüßte nicht, wie ich die dann zusammenfasse....
26.10.2011, 15:17	Gast11022013	Auf diesen Beitrag antworten »
Ja, das ist schon gut so. Du musst das einfach mal ausrechnen, was da herauskommt. Ist zugegebenermaßen ein bisschen Plackerei...
26.10.2011, 15:22	fermat106	Auf diesen Beitrag antworten »
Zusammengefasst: $\begin{eqnarray} <br /> <br /> \frac{(m+n+1)!}{(m+1)!(n)!} + \frac{(m+n+1)!}{(m)!(n+1)!}<br /> <br /> <br /> \end{eqnarray}$ wie fasst man so etwas weiter zusammen? Gemeinsamer Nenner??? Wie löse ich so einem Fall die Fakultät auf?
26.10.2011, 15:25	Gast11022013	Auf diesen Beitrag antworten »
Exakt! Hauptnenner finden...
26.10.2011, 23:54	fermat106	Auf diesen Beitrag antworten »
Hallo Dennis! Nochmals danke für deinen unermüdlichen Einsatz!!!!!!!!!!!!!!!!!!
27.10.2011, 10:38	Gast11022013	Auf diesen Beitrag antworten »
You're welcome! PS. Hast Du die Aufgabe jetzt hinbekommen bzw. das Rechnen am Ende?

Neue Frage »

Antworten »

Vollständige Induktion mit Binomialkoeffizienten

Verwandte Themen