Bei
besteht die Summe links aus dem einzigen Summanden
,
die Summe ist also
. Da
ungerade ist, steht rechts
,
der Induktionsanfang ist also gesichert.
Es sei die Aussage nun für
bewiesen, und es ist die Gültigkeit der Aussage für
zu zeigen. Die Summe links ist
-

Bei
gerade
(also
ungerade)
ist dies nach Induktionsvoraussetzung gleich
-

was mit der rechten Seite übereinstimmt. Bei
ungerade
(also
gerade)
ist die Summe nach Induktionsvoraussetzung gleich
-

was ebenfalls mit der rechten Seite übereinstimmt.