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?