Wir beweisen die Aussage für ein beliebiges n {\displaystyle {}n} durch Induktion über k {\displaystyle {}k} . Bei k = 0 {\displaystyle {}k=0} steht beidseitig n ′ {\displaystyle {}n^{\prime }} . Es sei die Aussage nun für k {\displaystyle {}k} schon bewiesen und betrachten wir k ′ {\displaystyle {}k^{\prime }} . Dann ist
