Getting an improved upper bound for a finite geometric series

Question

The title says it all.

For an infinite geometric series, we know that if $|x| < 1$, then

$$\sum_{i=0}^{\infty}{x^i} = \frac{1}{1 - x}.$$

On the other hand, if $|x| \geq 1$, then the the infinite geometric series

$$\sum_{i=0}^{\infty}{x^i} = 1 + x + x^2 + x^3 + \cdots$$

diverges, so that we consider the case of a finite geometric series.

We know that the equation

$$Y = \sum_{j=0}^{k}{y^j} = 1 + y + \cdots + y^k = \frac{y^{k + 1} - 1}{y - 1}$$

holds.

Traditionally, an upper bound for $Y$ is obtained via

$$Y = \frac{y^{k + 1} - 1}{y - 1} < \frac{y^{k + 1}}{y - 1}$$

so that we get

$$Z = \sum_{j=0}^{k}{y^{-j}} = 1 + \frac{1}{y} + \cdots + \frac{1}{y^k} = \frac{Y}{y^k} < \frac{y}{y - 1}.$$

My question is this: Is it possible to improve on the upper bound $$\frac{y}{y - 1}$$ for $$Z = \sum_{j=0}^{k}{y^{-j}}?$$ Or is this already the least upper bound for $Z$?

Of course, I would have to qualify that I am interested in upper bounds for $Z$ that do not depend on $k$.

Answer 1

If $y>1$,

$$\sum_{j=0}^{\infty}{y^{-j}}=\sum_{j=0}^{\infty}{\left(\frac 1y\right)^j}=\frac 1{1-1/y}=\frac{y}{y-1}$$

Since the terms are all positive, $\frac{y}{y-1}$ is not just the limit, it is the least upper bound to the sequence $\sum_{j=0}^{k}{y^{-j}}$. Therefore, for all limits that do not depend on $k$, that is the very best upper bound. No better bound is possible.

If $y<-1$, the series is an alternating series, and it alternates above and below your expression, therefore your expression is no longer an upper bound. The only upper bound that works for all $k$ is $1$, since that is the value of the sum for $k=0$ and all later sums are smaller. A bound that works for $k>0$ is $1+\frac 1y+\frac 1{y^2}$, and so on.

If $y=-1$, the series alternates between $1$ for even $k$ and $0$ for odd $k$. The least upper bound is $1$.

If $-1<y<0$ or $0<y\le 1$, your sequence diverges, and an upper bound that does not depend on $k$ is impossible.

If $y=0$, the sum is undefined.

Answer 2

(This is not really an answer to the original question that I had, just some thoughts that recently occurred to me while pondering a closely related problem.)

It is known that, for $q$ prime and $k$ a positive integer, $$I(q^k) = \frac{\sigma(q^k)}{q^k} = \frac{1 + q + \ldots + q^k}{q^k} = \frac{q^{k+1} - 1}{q^k (q - 1)},$$ where $\sigma(x)=\sigma_1(x)$ is the classical sum of divisors of the positive integer $x$.

This then gives the (trivial) upper bound $$I(q^k) < \frac{q^{k+1}}{q^k (q - 1)} = \frac{q}{q - 1}.$$

We prove the following theorem in this "answer".

THEOREM If $q$ is a prime number and $k$ is a positive integer, then $$I(q^k) < \bigg(\frac{q}{q - 1}\bigg)\bigg(\frac{q^{k+1}}{q^{k+1} + 1}\bigg).$$ Moreover, we have $$\bigg(\frac{q}{q - 1}\bigg)\bigg(\frac{q^{k+1}}{q^{k+1} + 1}\bigg) < \frac{q}{q - 1}.$$

PROOF

Let $q$ be a prime number, and let $k$ be a positive integer.

First, we want to show that $$I(q^k) < \bigg(\frac{q}{q - 1}\bigg)\bigg(\frac{q^{k+1}}{q^{k+1} + 1}\bigg).$$ Assume to the contrary that $$\frac{q^{k+1} - 1}{q^k (q - 1)} = I(q^k) \geq \bigg(\frac{q}{q - 1}\bigg)\bigg(\frac{q^{k+1}}{q^{k+1} + 1}\bigg).$$ This implies that $$q^{2k+2} - 1 = (q^{k+1} - 1)(q^{k+1} + 1) \geq {q^k}\cdot{q}\cdot{q^{k+1}} = q^{2k+2},$$ which is a contradiction. This proves the first part of the proposition.

Next, we have to prove that $$\bigg(\frac{q}{q - 1}\bigg)\bigg(\frac{q^{k+1}}{q^{k+1} + 1}\bigg) < \frac{q}{q - 1}.$$ Suppose to the contrary that $$\bigg(\frac{q}{q - 1}\bigg)\bigg(\frac{q^{k+1}}{q^{k+1} + 1}\bigg) \geq \frac{q}{q - 1}.$$ It follows that $$q^{k+1} \geq q^{k+1} + 1,$$ which is a contradiction. This proves the second part of the proposition, and we are done.