.
Lösung
Bekannt ist: Die Binomialkoeffizienten erfüllen für alle n und k die folgende Rekusionsformel:
.
Die zu beweisende Formel gilt für n=0 und alle zulässigen k.
Sie gilt weiter für k=0 und alle N, wie man sofort direkt prüft. Ebenso sieht man, dass sie für k>N gilt. Sei daher von jetzt ab 0<k. (Das wird in der Rechnung bei (*) benötigt.)
Wir starten wir mit der rechten Seite der zu beweisenden Gleichung und rechnen wie folgt. Dabei werden einige elementare Eigenschaften des Symbold [n]k benutzt:
Damit ist die behauptete Gleichung auch für N+1 bewiesen. Der Induktionsschluss ist zulässig. Die Formel ist für alle n und k bewiesen.