# Proving a statement by contradiction

Not sure if many of you speak binary, but the question is to prove that 2n bits are sufficient to store the product of two unsigned n-bit numbers (i.e., there will be no overflow).

I've thought of a simple method by contradiction, but its way too simple and I feel theres something wrong with it. So here it is:

Suppose not, that is, suppose that 2n bits are not sufficient to store the product of two unsigned n-bit numbers.

Then consider the product of two binary numbers 1111 x 1111. The result is 11100001, which is 8 bits=2n where n=4. So 2n was indeed sufficient to hold the product.

Have we proved anything here? Is this legit. If not, what are some ways I could prove this?

-
I think a direct proof would be more suitable. But then again, that would be in contradiction with your title. – Myself Mar 9 '11 at 17:14
You proved one thing, that the assumption (2n bits are not sufficient) was false in this one case – user1708 Mar 9 '11 at 17:15

Your mistake is negating (for every $n$ bit numbers $a,b$ the product $ab$ is a $2n$ bit number or less) to (for every $n$ bit numbers $a,b$ the product $ab$ takes more than $2n$ bits) (which you did contradict with your example) but the actual negation is (for some $n$ bit numbers $a,b$ the product $ab$ takes more than $2n$ bits). You can't contradict a "for some" just by giving an example though.

As for proving the theorem, you could prove the lemma if $x \le y$ then $x$ takes less than or equal to the number of bits that $y$ takes. Then 1111x1111 = 11100001 does prove the theorem in the case of n=4, but you will have to do this multiplication in a general way to prove it for every n.

Another useful thing to make proving this easier is that 2^n-1 = 1111111...111 for n 1's.

-
So how that that change for $(2n-1)^2$, how many 1's would that be? – maq Mar 9 '11 at 17:33
did you mean $(2^n-1)^2$? That is $2^{2n}-2^n+1$ which is less than or equal to $2^{2n}-1$ and by the lemma this takes at most $2n$ bits. – quanta Mar 9 '11 at 18:43

Your proof isn't valid - maybe there are some other numbers that do require more than $2n$ digits? You only provide a specific example which doesn't. This way you can prove that the product requires only $1$ digit - consider $0 \times 0$.

Your idea actually works, but there's no need for proof by contradiction. For the case $n=4$, each of the $n$-bit numbers is at most $15$, and so the product is at most $225$, which requires only $2n=8$ bits. This generalizes.

-
So how would I use this general fact? I mean I could keep providing examples, but how could I generalize this in terms of n? – maq Mar 9 '11 at 17:18
To generalize the example, the largest product you can get from $n$-digit numbers is from $(2^{n+1} - 1)^2$. How many bits does that take? – Mitch Mar 9 '11 at 17:22
Actually I got up to that part, but I couldnt figure out how many bits could represent that number. – maq Mar 9 '11 at 17:23
@mohabitar: If you expand $(2^{n+1}-1)^2$ you get $2^{\rm something} - {\rm something else}$ which is less than...quanta spells it out for you. (I think the lemma is unnecessary but that's debatable) – Mitch Mar 9 '11 at 18:56