Beweis mit vollständiger Induktion mit Binomialkoeffizient

Question

Zu zeigen ist

\(\sum \limits_{r=1}^{v} \binom{u+v-r}{u} = \binom{u+v}{u+1} \)

Mein Ansatz:
Induktionsanfang: v = 1
\( \binom{u}{u} = \binom{u+v}{u+1} \)
\(1 = 1 \)

Induktionsvoraussetzung
\(\sum \limits_{r=1}^{v} \binom{u+v-r}{u} = \binom{u+v}{u+1} \) gilt für ein \(v \in \mathbb{N} \)

Induktionsbehauptung
\(\sum \limits_{r=1}^{v+1} \binom{u+v-r}{u} = \binom{u+v+1}{u+1} \) gilt

Induktionsschritt
\(\sum \limits_{r=1}^{v+1} \binom{u+v-r}{u} = \sum \limits_{r=1}^{v} \binom{u+v-r}{u} + \binom{u+v-(v+1)}{u}  \)

mit IV folgt: = \( \binom{u+v}{u+1} +  \binom{u+v-(v+1)}{u} \) = \( \binom{u+v}{u+1} +  \binom{u-1}{u} \)

Weiter komme ich nicht. Vielleicht kann mir jemand weiterhelfen?

Comments

Deine Induktionsbehauptung ist nicht korrekt.
es müsste

\(\sum_{r=1}^{v+1}{{u+(v+1)-r}\choose {u}}=...\)

heißen.

---

Danke für den Hinweis. Der Rest stimmt aber soweit oder?

---

Habe eine korrekte Fassung als Antwort durchgerechnet.

Answer 1

Aloha :)

Die Induktionsvoraussetzung hast du ja bereits geprüft. Der Induktionsschritt ist nun:

$$\phantom{=}\sum\limits_{r=1}^{v+1}\binom{u+(v+1)-r}{u}=\binom{u+(v+1)-1}{u}+\sum\limits_{r=2}^{v+1}\binom{u+(v+1)-r}{u}$$$$=\binom{u+v}{u}+\sum\limits_{r=1}^{v}\binom{u+(v+1)-(r+1)}{u}=\binom{u+v}{u}+\sum\limits_{r=1}^{v}\binom{u+v-r}{u}$$$$\stackrel{(\text{I.V.})}{=}\binom{u+v}{u}+\binom{u+v}{u+1}=\binom{u+v+1}{u+1}\quad\checkmark$$

Das letzte Gleichheitszeichen folgt mit \(n=u+v\) und \(k=u+1\) aus:$$\binom{n+1}{k}=\binom{n}{k-1}+\binom{n}{k}$$

Answer 2

Du bist doch fast fertig. Warum stimmt deine letzte Gleichung. Subtrahiere erstmal die identischen Summanden.

Comments

Genau diesen Schritt verstehe ich nicht so ganz. Stehe gerade etwas auf dem Schlauch :D

---

Kannst du mir das etwas genauer erklären?

---

Was ist denn u+v-(v+1) ?

---

Soweit war ich ja schon, das ist  \( u+v-(v+1) = u-1 \)

---

Natürlich kommt man nicht weiter, wenn man versucht
eine falsche Behauptung zu beweisen ;-)

Answer 3

Wenn ich mich nicht täusche, ist der Induktionsschritt-Beweis komplizierter:

\(\sum_{r=1}^{v+1}{{u+(v+1)-r}\choose{u}}=\sum_{r=1}^{v}{{u+v-(r-1)}\choose{u}}+{{u}\choose{u}}\) (s=r-1 setzen:)

\(=\sum_{s=0}^{v-1}{{u+v-s}\choose{u}}+{{u}\choose{u}}=\sum_{s=0}^{v-1}{{u+v-s}\choose{u}}+{{u+v-v}\choose{u}}\)

\(=\sum_{s=0}^{v}{{u+v-s}\choose{u}}={{u+v}\choose{u}}+\sum_{s=1}^{v}{{u+v-s}\choose{u}}\)

Nun IV anwenden:

\(={{u+v}\choose{u}}+{{u+v}\choose{u+1}}={{u+v+1}\choose{u+1}}\) gemäß Additionssatz für Binomialkoeff
(Pascalsches Dreieck).

Answer 4

Du kannst es nicht so einfach rechnen: