Der Induktionsanfang für
ist klar.
Induktionsschluss:
Da für k>n
ist, ändert sich an der 1. Summe nichts, wenn der Laufindex k bis n+1 läuft.
Die 2. Summe ist nach Indexverschiebung
.
Und da für k<0
ist, ändert sich an der 2. Summe nichts, wenn der Laufindex k bei 0 beginnt.
Also ist
.
Und diese Summe ist nach der Rekursionsformel
für Stirlingzahlen 2. Art gleich
.