3
$\begingroup$

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"

$\endgroup$
  • $\begingroup$ "In a base $B$, an $n$ digit number multiplied by another $n$ digit number is a $2n$ digit number"... Counterexample: $10\cdot10=100$. $\endgroup$ – barak manos May 23 '15 at 10:02
  • $\begingroup$ @barakmanos 2 digits x 2 digits fits in 4 digits by hypothesis, 100 is just "0 thousands, 1 hundreds, 0 tens, 0 units" $\endgroup$ – Alec Teal May 23 '15 at 10:04
  • $\begingroup$ 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 $\endgroup$ – barak manos May 23 '15 at 10:07
  • $\begingroup$ @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) $\endgroup$ – Alec Teal May 23 '15 at 10:08
  • $\begingroup$ Definitely missing at most!!! $\endgroup$ – barak manos May 23 '15 at 10:08
1
$\begingroup$

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.

$\endgroup$
2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ $\text{See comments}$ $\endgroup$ – Alec Teal May 23 '15 at 10:08
  • $\begingroup$ This question really was about my proof. Also you now have a $<$ statement, I was looking for $\le$. Nice trick though. $\endgroup$ – Alec Teal May 23 '15 at 10:14
  • $\begingroup$ 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 $\endgroup$ – Alec Teal May 23 '15 at 10:18
  • 1
    $\begingroup$ 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. $\endgroup$ – Redundant Aunt May 23 '15 at 14:03

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.