Wie geht eine vollständige Induktion nach n?

Question

Wie geht bei dieser Formel eine vollständige Induktion nach n?

∀k,n∈ℕ:

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

Ich bekomme hier leider nicht mal den Induktionsanfang hin.

Answer 1

Setze für den Induktionsanfang n = 0. Von der Summe bleibt also nur der erste Summand mit m = 0 übrig.

$$ \begin{array} { l } { \sum \limits _ { m = 0 } ^ { 0 } \left( \begin{array} { c } { k + m } \\ { k } \end{array} \right) = \frac { k ! } { ( k - k ) ! k ! } = \frac { k ! } { k ! } } \\ { = \frac { k ! · ( k + 1 ) } { k ! · ( k + 1 ) } = \frac { ( k + 1 ) ! } { ( k + 1 ) ! } = \left( \begin{array} { l } { k + 1 } \\ { k + 1 } \end{array} \right) = \left( \begin{array} { c } { 0 + k + 1 } \\ { k + 1 } \end{array} \right) } \end{array} $$

Also stimmt die Formel für n = 0.

Nun sei die Formel für ein n richtig, das heißt es gelte:

Voraussetzung:

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

Behauptung:

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

Beweis:

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

Setze in den Beweis die Voraussetzung ein:

$$ = \left( \begin{array} { c } { n + k + 1 } \\ { k + 1 } \end{array} \right) + \left( \begin{array} { c } { k + n + 1 } \\ { k } \end{array} \right) = \frac { ( n + k + 1 ) ! } { n ! \cdot ( k + 1 ) ! } + \frac { ( n + k + 1 ) ! } { ( n + 1 ) ! \cdot k ! } \\ = ( n + k + 1 ) ! \left( \frac { 1 } { n ! ( k + 1 ) ! } + \frac { 1 } { ( n + 1 ) ! \cdot k ! } \right) \\ = ( n + k + 1 ) ! \left( \frac { n + 1 + k + 1 } { ( n + 1 ) ! \cdot ( k + 1 ) ! } \right) = \frac { ( n + k + 2 ) \cdot ( n + k + 1 ) ! } { ( n + 1 ) ! \cdot ( k + 1 ) ! } = \frac { ( n + k + 2 ) ! } { ( n + 1 ) ! \cdot ( k + 1 ) ! } $$