Wir führen für ein beliebiges \(n\) die Induktion über \(m\).

Induktionsanfang \(m=n\): Es gilt

\( \sum_{k=n}^n \begin{pmatrix} k \\ n \end{pmatrix} = \begin{pmatrix} n \\ n \end{pmatrix} = 1 = \begin{pmatrix} n+1 \\ n+1 \end{pmatrix} \)

Induktionsschritt: Angenommen es gilt \( \sum_{k=n}^m \begin{pmatrix} k \\ n \end{pmatrix} = \begin{pmatrix} m+1 \\ n+1 \end{pmatrix} \). Dann folgt

\( \sum_{k=n}^{m+1} \begin{pmatrix} k \\ n \end{pmatrix} = \begin{pmatrix} m+1 \\ n \end{pmatrix} + \sum_{k=n}^m \begin{pmatrix} k \\ n \end{pmatrix} = \begin{pmatrix} m+1 \\ n \end{pmatrix} + \begin{pmatrix} m+1 \\ n+1 \end{pmatrix} = \begin{pmatrix} (m+1)+1 \\ n+1 \end{pmatrix} \)