Proving a statement by contradiction

Question

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?

Answer 1

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.

Answer 2

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.