Induktion mit Binominalkoeffizienten

Question

Aufgabe:

Beweisen Sie die folgende Aussage durch vollständige Induktion über \( m \) :
Für \( n, m \in \mathbb{N}_{0} \) gilt \( \sum \limits_{k=0}^{m}\left(\begin{array}{c}n+k \\ k\end{array}\right)=\left(\begin{array}{c}n+m+1 \\ n+1\end{array}\right) \).

Problem/Ansatz:

I.Anfang mit n,m =0 --> \( \begin{pmatrix} 0\\0 \end{pmatrix} \)=\( \begin{pmatrix} 1\\1 \end{pmatrix} \)

--> 1=1 Aussage wahr.

I.Behauptung:

Habe alle m und n in der Gleichung jeweils mit einem +1 versehen

I.Schritt

Ich bin mir unsicher wie ich die Induktionsannahme aufstelle. Also die Grundgleichung für den Induktionsschritt

\( \sum\limits_{k=0}^{m+1} \) \( \begin{pmatrix} n+1+k\\k \end{pmatrix} \) = \( \sum\limits_{k=0}^{m} \) \( \begin{pmatrix} n+k\\k \end{pmatrix} \) + \( \begin{pmatrix} n\\k-1 \end{pmatrix} \)

-->+ \( \begin{pmatrix} n\\k-1 \end{pmatrix} \)  ist das fehlende Glied.

mein Idee von da: Allgemein gilt: \( \begin{pmatrix} n\\k \end{pmatrix} \) + \( \begin{pmatrix} n\\k+1 \end{pmatrix} \) = \( \begin{pmatrix} n+1\\k+1 \end{pmatrix} \)

Stimmt das?Ist mein Gedankengang richtig?

Answer 1

Aloha :)

Wir zeigen die Behauptung:$$\sum\limits_{k=0}^m\binom{n+k}{k}=\binom{n+m+1}{n+1}\quad;\quad n,m\in\mathbb N_0$$durch vollständige Induktion über \(m\).

Verankerung bei \(m=0\):

$$\sum\limits_{k=0}^m\binom{n+k}{k}=\sum\limits_{k=0}^0\binom{n+k}{k}=\binom{n+0}{0}=1=\binom{n+0+1}{n+1}=\binom{n+m+1}{n+1}\quad\checkmark$$

Induktionsschritt von \(m\) auf \(m+1\):

$$\sum\limits_{k=0}^{m+1}\binom{n+k}{k}=\sum\limits_{k=0}^{m}\binom{n+k}{k}+\binom{n+(m+1)}{(m+1)}\stackrel{\text{(Ind.Vor.)}}{=}\binom{n+m+1}{n+1}+\binom{n+m+1}{m+1}$$Wegen \(\binom{n}{k}=\binom{n}{n-k}\) können wir das zweite Binom umformen:$$\phantom{\sum\limits_{k=0}^{m+1}\binom{n+k}{k}}=\binom{n+m+1}{n+1}+\binom{n+m+1}{n}$$und mit dem Additionstheorem \(\binom{n+1}{k}=\binom{n}{k}+\binom{n}{k-1}\) sind wir fertig:$$\phantom{\sum\limits_{k=0}^{m+1}\binom{n+k}{k}}=\binom{n+m+1+1}{n+1}=\binom{n+(m+1)+1}{n+1}\quad\checkmark$$