Eine Summenformel für Binomialkoeffizienten über Induktion zeigen

Question

Aufgabe:

Induktion und Rekursion

a) Beweisen Sie die folgende Identität mit vollständiger Induktion über n:

$\sum \limits_{k=0}^{n}\left(\begin{array}{c}{m+k} \\ {k}\end{array}\right)=\left(\begin{array}{c}{m+n+1} \\ {n}\end{array}\right) \quad$ für alle $n, m \geq 0$

Ansatz:

Ich hab hier den Anfang gezeigt mit:

IA für n=0,k=0

(m über 0) = (m+1 über 0)

Answer 1

Der Anfang ist richtig, da jeder Binomialkoeffizient in dem unten eine 0 steht per Definition gleich 1 ist.

Der Schritt funktioniert nun folgendermaßen:

Setze Voraus, dass die Aussage für n gilt, also dass gilt:

$$\sum _ { k = 0 } ^ { n } \left( \begin{array} { c } { m + k } \\ { k } \end{array} \right) = \left( \begin{array} { c } { m + n + 1 } \\ { n } \end{array} \right) = \frac { ( m + n + 1 ) ! } { ( m + 1 ) ! \cdot n ! }$$

Jetzt soll gezeigt werden, dass die Aussage auch für n+1 gilt, die Behauptung lautet also:

$$\sum _ { k = 0 } ^ { n + 1 } \left( \begin{array} { c } { m + k } \\ { k } \end{array} \right) = \left( \begin{array} { c } { m + n + 2 } \\ { n + 1 } \end{array} \right) = \frac { ( m + n + 2 ) ! } { ( m + 1 ) ! ( n + 1 ) ! }$$

Beweis:

$$\sum _ { k = 0 } ^ { n + 1 } \left( \begin{array} { c } { m + k } \\ { k } \end{array} \right) = \sum _ { k = 0 } ^ { n } \left( \begin{array} { c } { m + k } \\ { k } \end{array} \right) + \left( \begin{array} { c } { m + n + 1 } \\ { n + 1 } \end{array} \right)$$

$$= \sum _ { k = 0 } ^ { n } \left( \begin{array} { c } { m + k } \\ { k } \end{array} \right) + \frac { ( m + n + 1 ) ! } { m ! \cdot ( n + 1 ) ! }$$

setze Voraussetzung ein

$$\begin{array} { l } { = \frac { ( m + n + 1 ) ! } { ( m + 1 ) ! \cdot n ! } + \frac { ( m + n + 1 ) ! } { m ! ( n + 1 ) ! } = ( m + n + 1 ) ! \left( \frac { 1 } { ( m + 1 ) ! \cdot n ! } + \frac { 1 } { m ! · ( n + 1 ) ! } \right) } \\ { = ( m + n + 1 ) ! \left( \frac { ( n + 1 ) + ( m + 1 ) } { ( m + 1 ) ! · ( n + 1 ) ! } \right) = \frac { ( m + n + 2 ) ! } { ( m + 1 ) ! · ( n + 1 ) ! } } \end{array}$$

Was zu zeigen war.