Summe von Binomialkoeffizienten

04.11.2009, 23:18

Airblader

Summe von Binomialkoeffizienten

Hi,

ich sitze nun eine Weile vor der letzten Teilaufgabe des neuen Übungsblattes, stehe aber etwas auf dem Schlauch und wäre daher über einen Tipp sehr dankbar!

Folgendes ist mit Vollst. Induktion zu beweisen:

$\begin{eqnarray*} \sum_{m=1}^n \binom{n+k-m}{k} = \binom{n+k}{k+1}\qquad k\leq n \end{eqnarray*}$

Induktionsanfang ist klar, beim Induktionsschritt dagegen hänge ich, weil ich einfach auf keine sinnvolle Form komme, in welcher ich die Annahme anwenden kann.
Die einzige Möglichkeit, zu der ich gefunden habe:

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

Aber hier gehts dann auch nicht weiter.
Kann mir jemand vielleicht einen kleinen Tipp geben (aber nicht zuviel - ich will nur in die richtige Richtung geschubst werden! Augenzwinkern

).

Danke schonmal,
air

04.11.2009, 23:48

Auf diesen Beitrag antworten »

Mit Umindizierung $\begin{eqnarray*} j=n-m \end{eqnarray*}$ kann man die Summe links in deiner Behauptung als

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

schreiben, was die Sache dann wohl etwas vereinfachen sollte - dann ist es nämlich ein "normaler" Summen-Induktionsbeweis. Augenzwinkern

05.11.2009, 00:24

Airblader

Auf diesen Beitrag antworten »

Hi,

Danke erstmal für den Tipp!
Werde mir das gleich mal noch näher anschauen. Ist natürlich schon ein gewisser Kniff, was mich wiederum ärgert, denn das macht es gewissermaßen zu einem Kernpunkt, auf den ich nicht selbst gekommen bin*.

Nun, was solls. Die anderen Aufgaben des neuen Blattes gingen dafür ja alle auch ohne Hilfe Big Laugh

Werds dann jetzt erstmal damit probieren. smile

air

*) Obwohl er mir nichtmal neu wäre *seufz*

Edit: Oh. Damit ist es ja sogar ein Vierzeiler. Klasse. Wie einfach das Leben sein kann. Nur des Interesses halber: Ginge es auch ohne einen solchen Kniff - auch wenn man in Kauf nimmt, dass es komplizierter wird?

05.11.2009, 05:46

Auf diesen Beitrag antworten »

hallo,

folgender gedanke.

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

grüße

_t

ps: wenns blödsinn ist ignorieren. Augenzwinkern

05.11.2009, 07:32

Auf diesen Beitrag antworten »

Zitat:

Original von Airblader
Ginge es auch ohne einen solchen Kniff - auch wenn man in Kauf nimmt, dass es komplizierter wird?

Ein einfacher Weg ganz ohne jede Indexverschiebung fällt mir nicht ein - will mir vielleicht auch nicht einfallen, da ich die einfachen Wege im Hinterkopf habe. Augenzwinkern

Basierend auf den Gedanken von _t kannst du über die Indexverschiebung $\begin{eqnarray*} i=m-1 \end{eqnarray*}$

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

umformen und dann rechts die Induktionsvoraussetzung für $\begin{eqnarray*} (n-1) \end{eqnarray*}$ einsetzen. Ist allerdings inhaltlich genau derselbe Weg, den ich oben vorgeschlagen habe, nur schreibtechnisch etwas anders arrangiert.

05.11.2009, 10:47

Airblader

Auf diesen Beitrag antworten »

Okay, Danke. Dann belasse ich es einfach mal bei deiner anfänglich vorgeschlagenen Verschiebung.

Danke!

air

Neue Frage »

Antworten »

Summe von Binomialkoeffizienten

Verwandte Themen