1

I understand the idea intuitively that because the number of options for each digit is more "granular" for base $2$, we need more digits to represent the same number as opposed to base $10$.

How can I express this idea (or another proof) in mathematical terms?

Neel Sandell
  • 306
  • 1
  • 10

1 Answers1

0

Take an integer $n$, for some $p\in \mathbb{Z}$ it is true that $2^p < n\leq 2^{p+1}$. It is clear that $p+1=\lceil \log_{2}(n)\rceil$. Similarly, for some $q\in \mathbb{Z}$ it is true that $10^q< n\leq 10^{q+1}$ and therefore $q+1=\lceil \log_{10}(n)\rceil$. You can see that the first quantity is always at least as large as the second quantity which is what we want to show (The first quantity is the length of the binary representation and the second the length of the decimal representation).

atul ganju
  • 964
  • You argue that $p + 1 = \lceil log_2{(n)} \rceil$, but let's consider a number at a boundary at the power of $2$ like $16$. It is the case that $2^{4} \leq 16 \leq 2^{5}$. Note that the quantity $\lceil log_2{(16)} \rceil$ is $4$ not $5$. – Neel Sandell Apr 02 '22 at 20:27
  • Also, how would you prove that the first quantity is at least as large as the second quantity? – Neel Sandell Apr 02 '22 at 20:28
  • @NeelSandell The first equality was meant to be strict. Also, the latter is just from the definition of the logarithm. The ceiling of $a$ is at least as big as the ceiling of $b$ if $a$ is at least as big as $b$. and you can show $\log_2$ is at least as big as $\log_{10}$ using the monotonicity of logs and their respective derivatives if you like. – atul ganju Apr 02 '22 at 20:32
  • 1
    I'm not sure what "monotonicity of logs" means, but could we just use change of base formula, and show that $log_{10} {2}$ in the denominator is less than $1$ and thus an "amplifying factor"? – Neel Sandell Apr 02 '22 at 20:36
  • That works! Since $\log_{10}(n)=\log_{2}(n)/\log_{2}(10)$ which since the denominator bigger than $1$ shows what you want to show :). – atul ganju Apr 02 '22 at 20:41