Beweis
Wir machen eine Doppelinduktion nach und nach . D.h. wir beweisen die Aussage für jedes feste durch Induktion nach
(innere Induktion)
und erhöhen dann in einem eigenen Induktionsdurchgang
(äußere Induktion).
Bei
ist nichts zu zeigen, da dann die Summen links und rechts leer sind, also gleich . Es sei also
,
sodass der linke Faktor einfach eine fixierte Zahl
ist. Wir wollen die Aussage in dieser Situation für beliebiges zeigen. Bei
ist die Aussage klar. Es sei die Aussage nun für ein
-
schon bewiesen. Dann ist
nach dem Distributivgesetz und der Induktionsvoraussetzung.
Es sei die Aussage nun für ein festes und jedes bewiesen. Dann ist wieder mit dem Distributivgesetz und der Induktionsvoraussetzung