+1 Daumen
6,4k Aufrufe

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)

von

1 Antwort

+1 Daumen
 
Beste Antwort

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.

von 10 k

Ein anderes Problem?

Stell deine Frage

Willkommen bei der Mathelounge! Stell deine Frage einfach und kostenlos

x
Made by a lovely community