Zehnersystem/Schriftliches Addieren/Korrekt/Fakt/Beweis

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 die Aussage durch Induktion über ${}k$. Bei ${}k=0$ handelt es sich um einstellige Zahlen und der Algorithmus ist korrekt. Hierzu macht man eine Fallunterscheidung abhängig davon, ob ${}a_{0}+b_{0}<10$ ist oder nicht. Es sei die Aussage nun für beliebige Zahlen, die beide maximal ${}k+1$ Ziffern haben, bewiesen, und seien zwei maximal ${}k+2$-stellige Zahlen gegeben. Es ist

${}{\begin{aligned}m+n&=\sum _{i=0}^{k+1}a_{i}10^{i}+\sum _{i=0}^{k+1}b_{i}10^{i}\\&=a_{k+1}10^{k+1}+\sum _{i=0}^{k}a_{i}10^{i}+b_{k+1}10^{k+1}+\sum _{i=0}^{k}b_{i}10^{i}\\&={\left(a_{k+1}+b_{k+1}\right)}10^{k+1}+\underbrace {\sum _{i=0}^{k}a_{i}10^{i}} _{=m'}+\underbrace {\sum _{i=0}^{k}b_{i}10^{i}} _{=n'}.\end{aligned}}$

Es seien ${}c_{i},d_{i}$ die durch den für ${}m$ und ${}n$ in Fakt beschriebenen Algorithmus festgelegten Zahlen. Die entsprechenden Zahlen für ${}m'$ und ${}n'$ stimmen damit bis auf eventuell ${}c_{k+1},c_{k+2},d_{k+2}$ überein, da diese nur von den Ziffern bis einschließlich ${}a_{k}$ und ${}b_{k}$ abhängen. Für ${}m'+n'$ bezeichnen wir mit ${}c_{k+1}'$ die entsprechende Ziffer, und zwar ist ${}c_{k+1}'=d_{k+1}$. Nach Induktionsvoraussetzung ist die Summe der beiden hinteren Summanden gleich

$\sum _{i=0}^{k}c_{i}10^{i}+c_{k+1}'10^{k+1}.$

Die Gesamtsumme ist somit gleich

${}{\begin{aligned}m+n&={\left(a_{k+1}+b_{k+1}\right)}10^{k+1}+c_{k+1}'10^{k+1}+\sum _{i=0}^{k}c_{i}10^{i}\\&={\left(a_{k+1}+b_{k+1}+c_{k+1}'\right)}10^{k+1}+\sum _{i=0}^{k}c_{i}10^{i}\\&={\left(a_{k+1}+b_{k+1}+d_{k+1}\right)}10^{k+1}+\sum _{i=0}^{k}c_{i}10^{i}\\&=c_{k+2}10^{k+2}+c_{k+1}10^{k+1}+\sum _{i=0}^{k}c_{i}10^{i}\\&=\sum _{i=0}^{k+2}c_{i}10^{i}.\end{aligned}}$

Zur bewiesenen Aussage