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.
