Die beiden Zahlen seien
-
wobei wir eventuell auch vordere Nullen erlauben. Wir beweisen die Aussage durch Induktion über . Bei
handelt es sich um einstellige Zahlen und der Algorithmus ist korrekt. Hierzu macht man eine Fallunterscheidung abhängig davon, ob
ist oder nicht. Es sei die Aussage nun für beliebige Zahlen, die beide maximal Ziffern haben, bewiesen, und seien zwei maximal -stellige Zahlen gegeben. Es ist
Es seien die durch den für
und
in
Fakt
beschriebenen Algorithmus festgelegten Zahlen. Die entsprechenden Zahlen für
und
stimmen damit bis auf eventuell überein, da diese nur von den Ziffern bis einschließlich und abhängen. Für bezeichnen wir mit die entsprechende Ziffer, und zwar ist
.
Nach Induktionsvoraussetzung ist die Summe der beiden hinteren Summanden gleich
-
Die Gesamtsumme ist somit gleich