Sum of the form $r+r^2+r^4+\dots+r^{2^k} = \sum_{i=1}^k r^{2^i}$

Question

I am wondering if there exists any formula for the following power series :

$$S = r + r^2 + r^4 + r^8 + r^{16} + r^{32} + ...... + r^{2^k}$$

Is there any way to calculate the sum of above series (if $k$ is given) ?

Answer 1

A formula for $$r+r^2+r^4+\cdots+r^{2^k}$$ is $$r+r^2+r^4+\cdots+r^{2^k}$$ You can calculate the sum of the series, if $k$ and $r$ are given, by calculating the sum of the series, that is, by computing the individual terms and adding them together.

Presumably, what is desired is a closed form formula for the sum, in terms of familiar functions such as logarithms and exponentials and sines and cosines and powers and roots, and a more efficient way to calculate it. As indicated in the comments, no such formula is known. I don't know whether it is possible to prove that no such formula exists, but considering how elementary the question is, I am confident that if there were a nice formula for it, Euler would have found it 250 years ago, and we'd all know about it now.

Answer 2

Although I cannot actually give an answer, I have explored many of the avenues for approximation of the sum, which I have illustrated below.

Integral Approximation of the Sum

$$ \int_{0}^{\infty} r^{2^x} \mathrm dx \le \sum_{i=0}^\infty r^{2^i}\le \int_{-1}^{\infty} r^{2^x} \mathrm dx $$

We have: $$ \int r^{2^x} \mathrm dx = \frac{\text{Ei}\left(2^x \log (r)\right)}{\log (2)} $$

For $r < 1$, this converges to $0$ as $x\to\infty$. Therefore, we have the following bounds: $$ -\frac{\text{Ei}\left(\log (r)\right)}{\log (2)} \le \sum_{i=0}^\infty r^{2^i} \le -\frac{\text{Ei}\left(\frac{\log (r)}{2}\right)}{\log (2)} $$

As an example, consider $r = 1/2$. Evaluating the bounds, we have: $ 0.546307 \le 0.816422 \le 1.15583 $. It is clear that this bound may not be entirely the best. However, as $r\to 1$, the bounds are asymptotically equal.

If we do not let $x \to \infty$ and instead consider the general case, we have the following bounds (if we stop at $c$):

$$ \frac{\text{Ei}\left(2^{c+1} \log (r)\right)-\text{Ei}(\log (r))}{\log (2)} \le \Sigma \le \frac{\text{Ei}\left(2^c \log (r)\right)-\text{Ei}\left(\frac{\log (r)}{2}\right)}{\log (2)} $$

Here is a graph of these bounds.

Error Approximation of the Sum

For the partial sum, we have:

$$ (n-m) r^{2^n} \le \sum _{k=m+1}^n r^{2^k} \le \frac{r^{2^{m+1} (n-m+1)}-r^{2^{m+1}}}{r^{2^{m+1}}-1} $$

For $m = -1$, we have:

$$ (n + 1) r^{2^n} \le \sum_{k=0}^n r^{2^k} \le \frac{r^{n+2}-r}{r-1} $$

The partial sum is necessary if you want an approximation anything near the real thing.

We can use this partial sum to truncate the error of the function. For example, let's say we want to find:

$$ \sum_{k=0}^{n} r^{2^k} $$

With an error no more than $\epsilon$. We split this into a partial sum:

$$ \sum_{k=0}^{m} r^{2^k} + \sum_{k=m+1}^{n} r^{2^k} = \sum_{k=0}^{n} r^{2^k} $$

We want to find $m$ such that the partial sum is less than $\epsilon$.

$$ \sum_{k=m+1}^{n} r^{2^k} \le \epsilon $$

Apply our bounds to get:

$$ \frac{r^{2^{m+1} (n-m+1)}-r^{2^{m+1}}}{r^{2^{m+1}}-1} \le \epsilon $$

Which, given $n, r,\text{and}, \epsilon$ reduces our problem to a 1D search.

Answer 3

I haven’t been able to obtain a closed form expression for the sum, but maybe you or someone else can do something with what follows.

In Blackburn's paper (reference below) there are some manipulations involving the geometric series

$$1 \; + \; r^{2^n} \; + \; r^{2 \cdot 2^n} \; + \; r^{3 \cdot 2^n} \; + \; \ldots \; + \; r^{(m-1) \cdot 2^n}$$

that might give some useful ideas to someone. However, thus far I haven't found the identities or the manipulations in Blackburn's paper to be of any help.

Charles Blackburn, Analytical theorems relating to geometrical series, Philosophical Magazine (3) 6 #33 (March 1835), 196-201.

As for your series, I tried exploiting the factorization of $r^m – 1$ as the product of $r-1$ and $1 + r + r^2 + \ldots + r^{m-1}:$

First, replace each of the terms $r^m$ with $\left(r^{m} - 1 \right) + 1.$

$$S \;\; = \;\; \left(r – 1 \right) + 1 + \left(r^2 – 1 \right) + 1 + \left(r^4 – 1 \right) + 1 + \left(r^8 – 1 \right) + 1 + \ldots + \left(r^{2^k} – 1 \right) + 1$$

Next, replace the $(k+1)$-many additions of $1$ with a single addition of $k+1.$

$$S \;\; = \;\; (k+1) + \left(r – 1 \right) + \left(r^2 – 1 \right) + \left(r^4 – 1 \right) + \left(r^8 – 1 \right) + \ldots + \left(r^{2^k} – 1 \right)$$

Now use the fact that for each $m$ we have $r^m - 1 \; = \; \left(r-1\right) \left(1 + r + r^2 + \ldots + r^{m-1}\right).$

$$S \;\; = \;\; (k+1) + \left(r – 1 \right)\left[1 + \left(1 + r \right) + \left(1 + r + r^2 + r^3 \right) + \ldots + \left(1 + r + \ldots + r^{2^{k} - 1} \right) \right]$$

At this point, let's focus on the expression in square brackets. This expression is equal to

$$\left(k+1\right) \cdot 1 + kr + \left(k-1\right)r^2 + \left(k-1\right)r^3 + \left(k-2\right)r^4 + \ldots + \left(k-2\right)r^7 + \left(k-3\right)r^8 + \ldots + \left(k-3\right)r^{15} + \ldots + \left(k-n\right)r^{2^n} + \dots + \left(k-n\right)r^{2^{n+1}-1} + \ldots + \left(1\right) r^{2^{k-1}} + \ldots + \left(1\right) r^{2^{k} - 1}$$

I'm now at a loss. We can slightly compress this by factoring out common factors for groups of terms such as $(k-2)r^4 + \ldots + (k-2)r^7$ to get $(k-2)r^4\left(1 + r + r^2 + r^3\right).$ Doing this gives the following for the expression in square brackets.

$$\left(k+1\right) + \left(k\right)r + \left(k-1\right)r^2 \left(1+r\right) + \left(k-2\right)r^4\left(1+r+r^2+r^3\right) + \ldots + \;\; \left(1\right)r^{2^{k-1}} \left(1 + r + \ldots + r^{2^{k-1} -1} \right)$$

Answer 4

I have not seen a closed form formula for the sum you talk about, and sense everyone else has already remarked on this fact, I thought I might mention that I have seen several other interesting results involving double exponentials and powers of two if your interested: $$\sum_{k=0}^{n-1}\frac{2^k}{x^{2^k}+1}=\frac{1}{x-1}-\frac{2^n}{x^{2^n}-1}$$ $$\prod_{k=0}^{n-1}(x^{2^k}+1)=\frac{x^{2^n}-1}{x-1}$$ $$\sum_{k=1}^{2^n}\binom{2^n}{k}=2^{2^n}-1$$ $$\prod_{n=0}^\infty(1+x^{2^n})=\frac{1}{1-x}$$

$$\sum_{n=0}^\infty \frac{2^n}{x^{2^n}+1}=\frac{1}{x-1}$$ $$\sum_{n=0}^\infty\frac{4^nx^{2^n}}{(x^{2^n}+1)^2}=\frac{x}{(x-1)^2}$$

$$\text{Also for |x| < 1}$$ $$\sum_{n=0}^\infty \frac{(-1)^n2^nx^{2^n}}{x^{2^{n+1}}-x^{2^n}+1}=\frac{-2x^2}{x^4+x^2+1} $$ $$\text{Let $f(n)$ count how many factors of 2 n has, then we have} $$ $$\frac{1}{x-1}-\sum_{n=1}^\infty \frac{f(n)}{x^n}=\sum_{n=0}^\infty \frac{1}{x^{2^n}+1}$$ $$\sum_{n=1}^\infty \frac{f(n)}{n^2}=\frac{\pi^2}{18}$$ $$\sum_{k=1}^{2^n} f(k)=2^n-1$$ $$\text{It was also proved by Erdős that both the constants bellow are irrational}$$ $$\sum_{n=1}^\infty \frac{1}{2^n-1}=C_1$$ $$\sum_{n=1}^\infty \frac{1}{2^{2^n}+1}=C_2$$ $$\text{The constant $C_1$ is known as the Erdős-Borwein Constant}$$ $$\text{The constant $C_2$ is less known and is talked about here:}$$ $$\text{http://journal.ms.u-tokyo.ac.jp/pdf/jms080206.pdf}$$

Answer 5

Consider the the sequence $a_n$ defined as: If $n=1$ then $a_n=1$, else if $n>1$ then $a_n=-1$.

This is the sequence $a_n = 1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,...$

The Dirichlet inverse (call it $b_n$) of $a_n$ is the oeis sequence called "Number of ordered factorizations of n" http://oeis.org/A074206 , starting: $b_n = 0, 1, 1, 1, 2, 1, 3, 1, 4, 2, 3, 1, 8,...$, which is also a Dirichlet series. Notice that the first term: $b_0 = 0$.

For reasons I can not explain clearly, $b_n$ has the ordinary generating function:

$$\sum\limits_ {n = 1}^{\infty} b_n r^n = r + \sum\limits_ {a = 2}^{\infty} r^{a} + \sum\limits_ {a = 2}^{\infty}\sum\limits_ {b = 2}^{\infty} r^{ab} + \sum\limits_ {a = 2}^{\infty}\sum\limits_ {b = 2}^{\infty}\sum\limits_ {c = 2}^{\infty} r^{abc} + \sum\limits_ {a = 2}^{\infty}\sum\limits_ {b = 2}^{\infty}\sum\limits_ {c = 2}^{\infty}\sum\limits_ {d = 2}^{\infty} r^{abcd} + ... $$

Evaluate each sum partially to the summation index equal to $2$:

$$r + \sum\limits_ {a = 2}^{2} r^{a} + \sum\limits_ {a = 2}^{2}\sum\limits_ {b = 2}^{2} r^{ab} + \sum\limits_ {a = 2}^{2}\sum\limits_ {b = 2}^{2}\sum\limits_ {c = 2}^{2} r^{abc} + \sum\limits_ {a = 2}^{2}\sum\limits_ {b = 2}^{2}\sum\limits_ {c = 2}^{2}\sum\limits_ {d = 2}^{2} r^{abcd} + ... $$

Simplify:

$$r + r^{2} + r^{2*2} + r^{2*2*2} + r^{2*2*2*2} + r^{2*2*2*2*2} + ...... + r^{2^k}$$

multiply out:

$$r + r^{2} + r^{4} + r^{8} + r^{16} + r^{32} + ...... + r^{2^k}$$

call it $S$ and you are done.

The sum:

$$\sum\limits_ {n = 1}^{\infty} b_n r^n$$

above, probably does not have a closed form other than the multiple sums, and therefore $S$ probably does not have a closed form either. But it points out what the scope of generating functions is.

Answer 6

This series has a plethora of interesting re-statements.

A lambert series is given by

$$ \sum_{n=0}^{q} x^{2^n} = \frac{x}{1-x} - \sum_{k=1}^{q-1} \left[ \frac{x^{2^k} + x^{2^{k-1}}}{1-x^{2^k}}\right] - \frac{x^{2^{q}}+x^{2^{q-1}}}{1-x^{2^{q-1}}} $$

This for example reveals that

$$ x+x^2+x^4 +x^8 = \frac{x}{1-x} - \frac{x^3}{1-x^2} - \frac{x^6}{1-x^4} - \frac{x^{12}}{1-x^4} $$

As $q \rightarrow \infty$ if you believe in the divergent regularization $x^{\infty} = 0$ then this also correctly gives an alternative resummation for $\sum_{n=0}^{\infty} x^{2^n}$.

The book generalized analytic continuation by Ross and Shapiro is a good place to start for those interested in learning more.