Für
gibt es nur den einen Summanden
, sodass der Induktionsanfang gesichert ist. Es sei die Aussage für ein
bewiesen. Wir unterteilen die zu berechnende Summe je nachdem, ob die beteiligten Summanden kleiner oder gleich
sind. Dann ist unter Verwendung der Induktionsvoraussetzung und der Formel für die Summe der ersten
Zahlen
