# My proof that an n digit number, times an n digit number can be expressed as a 2n digit number

I am very proud to say this is the first time I've actually used maths to endeavour to prove something without it being related to a question from my course!

Statement
In a base $B$, an $n$ digit number multiplied by another $n$ digit number can be expressed as a $2n$ digit number without overflowing (This works for $B\ge 2$)

I rephrased this as "the largest $n$ digit number $\times$ the largest $n$ digit number can be written as a $2n$ digit number"

I did it for $n=1$ then decided "I may as well use induction"

n=1

$ab\le (B-1)(B-1)=B^2-2B+1=B(B-2)+1$ - notice for $B=10$ this gives $81$, $9\times 9$

Assume it is true for n=k
I can now assume $(\sum^{k-1}_{i=0}B^ia_{i+1})(\sum^{k-1}_{i=0}B^ib_{i+1})=(\sum^{2k-1}_{i=0}B^ic_{i+1})$ for some $c_i$

Show it is true for n=k+1
Let $x,y$ be $k+1$-digit numbers.

Let $a$ and $b$ be $k$-digit numbers (the first $k$ digits of $x$ and $y$), and $a_{k+1}$, $b_{k+1}$ the $(k+1)^\text{th}$ digits, then:

$xy=(B^ka_{k+1}+a)(B^kb_{k+1}+b)$

By considering the maximal values of $x$ and $y$ (all digits are $=B-1$) we get the result:

$$xy\le B^{2k+1}(B-1)+B^{2k}(B-1)+\sum^{2k-1}_{i=0}B^ic_{i+1}-2B^k(B-1)$$ $$\le B^{2k+1}(B-1)+B^{2k}(B-1)+\sum^{2k-1}_{i=0}B^ic_{i+1}$$

Which is a $2k+2$ digit number.

This completes my proof.

Is this correct? I also feel like I am missing some lemmas, like "how do I know that 9x9 is the largest of the 1x1 digit values in base 10?"

Where can I find out more? Either way I'm quite happy with my proof.

Final note
The $B^ka_{k+1}b$ and like terms in the initial expansion can be thought of as $B^k[a_{k+1}\sum^{k-1}_{i=0}B^{i}b_{i+1}]$, the left hand side can be thought of as a $k$-digit number which is all zeros except for the final digit, having value $a_{k+1}$ and the right hand side (the sum) can be thought of as a $k$ digit number. By the induction hypothesis this is a 2k digit number

So we get the term $B^k(B(a+b)-(b+a))\le 2(B^{2k}(B-1)-B^k(B-1))$

I would write all the "expand the brackets" steps but this is really really laggy as is, I've written all the bits that are not simply "expand the brackets"

• "In a base $B$, an $n$ digit number multiplied by another $n$ digit number is a $2n$ digit number"... Counterexample: $10\cdot10=100$. – barak manos May 23 '15 at 10:02
• @barakmanos 2 digits x 2 digits fits in 4 digits by hypothesis, 100 is just "0 thousands, 1 hundreds, 0 tens, 0 units" – Alec Teal May 23 '15 at 10:04
• Well then you can just as easily claim that $100$ is "$0$ millions, $0$ hundred-thousands, $0$ ten-thousands, $0$ thousands, $1$ hundreds, $0$ tens, $0$ unit"... And there you go, an $n$ digit number multiplied by another $n$ digit number is a $3.5n$ digit number – barak manos May 23 '15 at 10:07
• @barakmanos there's a missing "at most", I'll give you that, and make the edit. But indeed 100x100 fits inside a 14 digit number (7 digits being millions) – Alec Teal May 23 '15 at 10:08
• Definitely missing at most!!! – barak manos May 23 '15 at 10:08

Let $b\ge 2$ be an integer.

In base $b$, the smallest number which is a product of two numbers with $m$ and $n$ digits, is

$$b^{m-1}b^{n-1}=b^{m+n-2}$$

having $m+n-1$ digits and the largest is

$$(b^m-1)(b^n-1)=b^{m+n}-b^m-b^n+1<b^{m+n}$$

having at most $m+n$ digits.

So, the product of numbers with $m$ and $n$ digits has either $m+n-1$ or $m+n$ digits.

Your statement is not generally true; consider $3\cdot 3=9$ or $19\cdot 49=931$. If you rephrase it as: an $n$ digit number times an $m$ digit number has at most $n+m$ digits, it would be true, but then it is quite obvious:

Consider the n-digit number $x$ and the m-digit number $y$. Therefore we have $x<B^n$ and $y<B^m$ which yields $xy<B^n\cdot B^m=B^{n+m}$. Thus, $xy$ cannot have more than $n+m$ digits, because otherwise $xy≥B^{n+m}$.

This yields the desired result.

• $\text{See comments}$ – Alec Teal May 23 '15 at 10:08
• This question really was about my proof. Also you now have a $<$ statement, I was looking for $\le$. Nice trick though. – Alec Teal May 23 '15 at 10:14
• E.G yours with $n=m=3$ yields 7 digits for $xy$ I required to know it would take no more than $6$ to specify $xy$ for any 3 digit numbers – Alec Teal May 23 '15 at 10:18
• I'm sorry I couldn't give a satisfying answer. No it yields $6$ digits; it proves that $xy<1000000$; because it is smaller than the smallest 7 digit number it has at most 6 digits. – Redundant Aunt May 23 '15 at 14:03