2

From my understanding the standard algorithm for adding two numbers in base $b$ is the normal pencil-on-paper addition.

For example, let's say with have two base $b$ numbers with digits $i$, $j$, $k$, $l$, $m$, $o$:

$$ \begin{array}{rccccc} ( & i & j & k &)_{b} \\ + \; ( & l & m & o &)_{b} \\ \end{array} $$

The result would be:

$$ \Bigl( \; \bigl(i+l+c_{j+m+c_{k+o}}\bigr) \quad \bigl(j+m+c_{k+o}\bigr) \quad \bigl(k+o\bigr) \; \Bigr)_{b} $$

Where $+$ is an overflowing addition1, and where $c_{x+y}$ is the carry of the addition of $x + y$.

Because I'm a programmer by trade, I tried find a case where the carry would be over 1, but I couldn't.

Is there any formal proof of my theory?

1. $x + y$ is always below $b$.
Antoine Catton
  • 123
  • 5

1 Answers1

2

We prove by induction that the maximum carry is $1$ in any base $b$. This is clearly true when carrying over units to the $b^1$ place, because the maximum is $(b-1)+(b-1)=1(b-2)_b$. Suppose by induction that we are adding the digits in the $b^k$ place, say $x$ and $y$ with $x,y<b$, and let $c$ be the carry from $b^{k-1}$, which by the inductive hypothesis is at most $1$. Then the result is $x+y+c\leq (b-1)+(b-1)+1=1(b-1)_b$, so the maximum carry to the $b^{k+1}$ place is a $1$, and the result follows by induction.

Looking at the base $10$ case, that means the largest digit sum you can get is $19$, which is what happens when you carry over a $1$ and have a $9$ for each digit. The max in general is $2b-1$, which has a $1$ in the $b^1$ place.

Matt Samuel
  • 58,164