I am interested in learning about proofs for discrete mathematics. One recurring fact I find in the literature is that
the number of digits $d$ required to represent integer $N$ in base $B$ is $\log_B{n}$
I am unhappy with this on two fronts. The first is that no source I have come across actually proves this claim. The second, I do not think the claim is true, and I am trying to prove this in a few ways but am finding slightly different results.
If we have a $d$ digit string in base $B$, this is an element of the set $\{0,1,\dots,B-1\}^{d}$ which has $B^d$ elements. This means we can represent exactly $0,1,\dots,B^{d}-1$ using $d$ digits; solving for $N$ gives $d=\lceil \log_B{(N+1)}\rceil$.
An alternative way to see this is that the largest integer we can represent is $\sum_{i=0}^{d-1}(B-1)*B^i$, which is also $B^d-1$ and gives the same result.
Why then, do sources describe this as $\log_B(n)$? An alternative representation that is equally confusing is $\lfloor\log_BN\rfloor+1$; this requires a proof that $$\lfloor\log_BN\rfloor+1 = \lceil \log_B{(N+1)}\rceil$$
which I cannot seem to resolve; unless I am on the wrong track entirely.
Best Answer
Since $\log_bn$ is an integer if and only if $n$ is a power of $b$, it’s clear that the number of digits is generally not exactly $\log_bn$; it is, however, closely approximated by $\log_bn$ and grows (with $n$) like $\log_bn$, which is what is generally meant by that assertion.
To get the exact number of digits of the base $b$ representation of $n$, where $n$ is a positive integer, observe that $n$ has $k$ digits if and only if $b^{k-1}\le n<b^k$, since $b^k$ is the smallest integer to have $k+1$ digits. This is equivalent to the inequality $k-1\le\log_bn<k$, i.e., to $\lfloor\log_bn\rfloor=k-1$, or $k=\lfloor\log_bn\rfloor+1$.
To use the ceiling function instead, add $1$ to each term of the inequality $b^{k-1}\le n<b^k$ to get $b^{k-1}<n+1\le b^k$; this is possible because we’re dealing here only with integers, so that $b^{k-1}\le n$ is precisely equivalent to $b^{k-1}<n+1$, and similarly for the other inequality. But $b^{k-1}<n+1\le b^k$ says exactly that $k-1<\log_b(n+1)\le k$ and hence that $\lceil\log_b(n+1)\rceil=k$.