Wir beweisen die Aussage durch Induktion über . Für ist die Aussage klar. Der Fall , der im Induktionsschritt verwendet wird, bedeutet
-
und folgt aus der disjunkten Zerlegung
-
mittels
Zum Induktionsschritt sei die Aussage für ein bestimmtes bewiesen, und wir zeigen sie für .
Unter Verwendung des Falles mit zwei Mengen und der Induktionsvoraussetzung
(für und )
ist