Upper bound on partial sum of a geometric series

Question

For a geometric series $1,r,r^2,\dots$ with integer $r \ge 2$, denote the $k^{th}$ partial sum by $\Sigma_k = \sum_{i=1}^k r^{i-1} = (r^k - 1)/(r-1)$. Is it true that $\Sigma_k < 2^{\lfloor \log_2 r^k \rfloor}$ for any $k$ ?

How does one prove this upper bound on the partial sum? It seems to be true based on some preliminary computations, but my first attempt at proving this using superadditivity of $\lfloor \cdot \rfloor$ and induction did not work.

Answer 1

First, we observe that $$ \frac{r^k-1}{r-1}<2^{\lfloor k\log_2r\rfloor} $$ if and only if $$ r^k-1<(r-1)2^{\lfloor k\log_2r\rfloor}. $$ Moreover, since $k\log_2r-1<\lfloor k\log_2r\rfloor\leq k\log_2r$ there exists an $0\leq x<1$ so that $$ 2^{\lfloor k\log_2r\rfloor}=2^{k\log_2r-x}. $$ Therefore, we consider $$ r^k-1<(r-1)2^{-x}2^{k\log_2r}=(r-1)2^{-x}r^k. $$ If $(r-1)2^{-x}$ can be smaller than $1-\varepsilon$ for infinitely many $k$'s, then the inequality will fail for $k$ sufficiently large.

• The inequality holds when $r\geq 3$. In this case, $r-1\geq 2$ and since $x<1$, $2^{-x}>\frac{1}{2}$, so the coefficient on the RHS is at least $1$ and we have $$ r^k-1<r^k<(r-1)2^{-x}r^k. $$

• The inequality holds when $r=2$. In this case, the argument of the floor function is always an integer, so $x=0$ and the RHS is $r^k$, which is greater than $r^k-1$.

• The inequality can fail when $2<r<3$. For example, when $r=2^{4/3}$, $k\log_2r=\frac{4k}{3}$ and we see that since $4$ and $3$ are relatively prime, there are infinitely many $k$'s so that $4k\equiv 2\pmod 3$. This case corresponds to $x=\frac{2}{3}$, which is as large as possible in this case. A quick check allows us to see that in this case $$ (r-1)2^{-x}=(2^{4/3}-1)(2^{-2/3})\approx0.957<1. $$ Then, for $k$ sufficiently large, the inequality fails. In this case, it happens when $k=5$. In this case, $$ \frac{2^{4k/3}-1}{2^{4/3}-1}\approx66.187. $$ On the other hand, $\lfloor k\log_2(r)\rfloor=6$ and $2^6=64$.

• It should be possible to extend this argument to any case where $\log_2r$ is between $2$ and $3$ and irrational via ergodic theory ($k\log_2r$ should be arbitrarily close to the next integer infinitely often).

• It is likely that the inequality can fail for most numbers between $2$ and $3$ where $\log_2r$ is rational, but I do not have a complete classification. Perhaps the argument above will shed some light on this.