\( \sum \limits_{k=0}^{m}\left(\begin{array}{c}n+k \\ n\end{array}\right)=\left(\begin{array}{c}n+m+1 \\ n+1\end{array}\right) \).
Induktion ist schon die richtige Idee, allerdings über m.
Denn das n ist ja einfach nur eine fest vorgegebene nat. Zahl.
Für m=0 hast du dann \( \left(\begin{array}{c}n \\ n\end{array}\right)=\left(\begin{array}{c}n+1 \\ n+1\end{array}\right) \).
Das passt ja schon mal.
Wenn es nun für ein m gilt, dann hat man:
\( \sum \limits_{k=0}^{m+1}\left(\begin{array}{c}n+k \\ n\end{array}\right) \)
\( =\sum \limits_{k=0}^{m}\left(\begin{array}{c}n+k \\ n\end{array}\right) +\left(\begin{array}{c}n+m+1 \\ n\end{array}\right) \)
Mit der Induktionsannahme also
\( = \left(\begin{array}{c}n+m+1 \\ n+1\end{array}\right) +\left(\begin{array}{c}n+m+1 \\ n\end{array}\right) \)
und das ist ja nach der gängigen Rekursionsformel
\( = \left(\begin{array}{c}n+m+1+1 \\ n+1\end{array}\right) \)
Also passt es !
