Let $q$ be a rational number satisfying $1/2<q<1,$ so that $\left\{q^n\right\}_{n=0}^\infty$ is a decreasing infinite geometric progression with rational terms. Consider absolute values of generalized partial sums of this progression: $$\left|1\pm q\pm q^2\pm q^3\pm\,...\pm\, q^n\right|,$$ where $n$ is some fixed natural number, and each $\pm$ can independently be either a plus or minus sign. There are multiple possible choices of those signs, and I refer to all those expressions as generalized partial sums.
A natural and interesting question to ask is:
- What is the smallest absolute value of a generalized partial sum that can be attained for given parameters $(q,n)?$
In other words, if we want to balance positive and negative terms as perfectly as possible, what is the best result we can get?
Obviously, this question in each particular case can be solved by brute force, by computing values for all possible $2^n$ choices of signs.
I decided to do some experiments, expecting to discover a simple pattern. Curiously, the results were quite unexpected and irregular. Let's consider a simple case when $q=2/3$, and compute the sequence of smallest absolute values for $n=1,\,2,\,3,\,...$
It is clear that the denominators will be powers of $3$, so we will multiply all terms of the sequence by the same factor $3^n$ to reduce everything to integers. In other words, we are looking for the smallest value of:
$$\left|3^n\pm 3^n \left(\tfrac23\right)\pm 3^n \left(\tfrac23\right)^2\pm \,...\pm\, 3^n \left(\tfrac23\right)^{n-1}\pm 3^n \left(\tfrac23\right)^n\right|,$$
or, equivalently,
$$\left|3^n\pm 2\cdot3^{n-1}\pm 2^2\cdot3^{n-2} \pm\,...\pm\, 2^{n-1}\cdot3 \pm 2^n\right|.$$
Here is the result:
$$1,\,1,\,5,\,1,\,19,\,7,\,5,\,65,\,61,\,73,\,227,\,257,\,5,\,439,\,1253,\,2425,\,2035,\,833,\,2677,\,\dots$$
Here is a log plot of it:
As you can see, the sequence is not monotone and seems to have no obvious pattern. It appears that the overall growth rate is—very roughly—exponential.
- Can we find asymptotic lower and upper bounds for this sequence?
- Can we find a way to compute its terms for given parameters $(q,n)$ more efficiently, without the use of brute force? Can we compute more terms?
- Is there a general formula?