Zehnersystem/Schriftliches Addieren/Korrekt/Fakt/Beweis2

Beweis

Die beiden Zahlen seien

$m=a_{0}+a_{1}10+a_{2}10^{2}+\cdots +a_{k}10^{k}\,\,{\text{ und }}\,\,n=b_{0}+b_{1}10+b_{2}10^{2}+\cdots +b_{k}10^{k},$

wobei wir eventuell auch vordere Nullen erlauben. Wir beweisen ein schrittweises Invarianzprinzip des schriftlichen Addierens, nämlich, dass nach dem ${}i$-ten Schritt (${}i=-1,0,1,2,\ldots$), wenn die hinteren Ziffern ${}c_{i},c_{i-1},\ldots ,c_{0}$ und die Übertragsziffern ${}d_{i+1}$ schon berechnet sind, dass dann die jeweilige Summe

$S_{i}={\left(a_{k}10^{k}+\cdots +a_{i+1}10^{i+1}\right)}+{\left(b_{k}10^{k}+\cdots +b_{i+1}10^{i+1}\right)}+d_{i+1}10^{i+1}+{\left(c_{i}10^{i}+\cdots +c_{1}10+c_{0}\right)}\,$

konstant ist (also nicht von ${}i$ abhängt), und zwar gleich ${}m+n$. Diese Summen beschreiben eine Momentaufnahme des Algorithmus zu einem bestimmten Zeitpunkt. Dabei bedeutet der Schritt ${}-1$, dass noch keine Rechnung durchgeführt wurde. Am Anfang, bei ${}i=-1$, sind die beiden hinteren Summanden nicht vorhanden und vorne stehen ${}m$ und ${}n$ komplett, die Summe ist also ${}m+n$. Die Konstanz der Summen beweisen wir durch Induktion nach ${}i$, wobei wir den Fall

${}i=-1\,$

soeben behandelt haben. Sei nun die Konstanz

${}m+n=S_{-1}=S_{0}=S_{1}=\ldots =S_{i}\,$

bereits bewiesen, und wir verarbeiten die ${}10^{i+1}$-Stelle. Gemäß dem Algorithmus addiert man

$a_{i+1}+b_{i+1}+d_{i+1}$

und schreibt dies als

$d_{i+2}10+c_{i+1}$

mit ${}0\leq c_{i+1}\leq 9$ Somit ist

${}{\begin{aligned}a_{i+1}10^{i+1}+b_{i+1}10^{i+1}+d_{i+1}10^{i+1}&={\left(a_{i+1}+b_{i+1}+d_{i+1}\right)}10^{i+1}\\&={\left(d_{i+2}10+c_{i+1}\right)}10^{i+1}\\&=d_{i+2}10^{i+2}+c_{i+1}10^{i+1}.\end{aligned}}$

Wenn man in der Summe ${}S_{i}$ die linke Seite der vorstehenden Gleichung durch die rechte Seite ersetzt, so erhält man gerade ${}S_{i+1}$, was die Gleichheit zeigt. Wenn man ${}i$ hinreichend groß nimmt, hat man ${}m$ und ${}n$ verbraucht und die Summe ${}S_{i}$ besteht dann allein aus der durch die Ziffern ${}c_{i}$ gebildeten Zahl. Dies stimmt also mit der Summe ${}m+n$ überein.

Zur bewiesenen Aussage