The maximum number of digits in binary multiplication Given 2 binary numbers of n digits. (n can be from 1 to something large) What is the maximum number of digits of their product?
I think it's 1 in 1-digit*1-digit, and 2n otherwise. But I want some more proof.
For example, n=3. So I want to know the maximum number of digits in their product. If I used the largest number in 3 digits, 111*111=110001, which is 6 digits. But I want some sort of function that gets the number of digits without actually calculating this.
 A: The largest number with $n$ binary digits is $2^n-1$. So the largest possible product is $(2^n-1)^2 = 2^{2n}-2^{n+1}+1$.
If $n=1$, this number is equal to $1$, as you say. Otherwise, it lies strictly between $2^{2n-1}$ and $2^{2n}$, so it has $2n$ digits. (It is greater than $2^{2n-1}$ because $2^{n+1} \le \frac12\cdot 2^{2n}$ if $n \ge 2$.)
A: When you square an $n$-digit number you get either $2n-1$ or $2n$ digits in the product: this is true for binary, decimal or any other base. Which one you get depends on whether or not there is a "carry" into the $2n$ column when you make the calculation.
Let your number, $k$, have $n$ binary digits. We want to find how large $k$ must be so that $k^2$ has $2n$ rather than $2n-1$ digits, that is we want to solve
$$2n = \lfloor 2\log_2k+1 \rfloor.$$
$\displaystyle k = \big \lfloor \frac{2^n}{\sqrt 2}\big\rfloor + 1$ is the smallest value that does the job.
For your example, $n=3$ gives $k=6$ and we can check that $6^2 = 36 = 100100_2$ has six binary digits whereas $5^2=25=11001_2$ has only five.
For a larger example, $n=10$ gives $k=725$ and we find that $725^2 = 525625 = 10000000010100111001_2$ has twenty binary digits, whereas $724^2 = 524176 = 1111111111110010000_2$ has a mere nineteen.
