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

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) ?

-
I'm pretty sure there's no closed form result like that for the geometric series, but I would love to be proved wrong about that. – Ron Gordon Jan 13 '13 at 12:32
At least and according to W|A the integral exists: $\displaystyle \int r^{2^x} dx =\frac{\text{Ei}(2^x \ln r)}{\ln 2}+ \color{grey}{\rm constant}$... – draks ... Jan 13 '13 at 13:15
For $r=1/2$, oeis.org/A007404 gives a reference which may be of help. No closed formula though. – Eckhard Jan 13 '13 at 13:18
For $r=1/10$ this is the Fredholm-Rueppel sequence... – draks ... Jan 13 '13 at 13:22
@Eckhard Here's a ref, where they say that $M=\sum_{n\ge 0}\frac1{2^{2^n}}$ is the transcendental Kempner-Mahler number... – draks ... Jan 13 '13 at 13:29

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.

-
I trust that the people downvoting this answer can provide better ones. – Gerry Myerson Jan 16 '13 at 23:29
I wouldn't put money on that one ... +1. – Old John Jan 16 '13 at 23:51
For $r << 1$ this should converge very rapidly, for $r >> 1$ just divide by $r^{2^k}$ and you are almost back at the start. For intermediate values, perhaps Euler-Maclaurin is of help (but the exponent will be a hassle...). – vonbrand Jan 22 '13 at 19:48

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)$$

-
Isn't Blackburn's series just a geometric series? – vonbrand Jan 21 '13 at 20:51
@vonbrand: Yes, I realized this later that evening and wanted to reword my comments about Blackburn's paper, but I haven't had internet access until today. I'll reword it now so as to be more appropriate for this thread. – Dave L. Renfro Jan 22 '13 at 19:17
In case anyone is curious as to how the heck I knew about Blackburn's paper, I have a huge stack of photocopies of papers on sequences and series (mostly from the 1800s, for historical purposes). When I saw Hitein's series I vaguely recalled seeing something like it, so I spent (at least) an hour the following morning quickly flipping through these papers and found Blackburn's paper. Regarding the photocopied papers themselves (an insanely time-consuming hobby of mine), google the following words/phrases in google's archive of usenet groups: Renfro journal "every volume" – Dave L. Renfro Jan 22 '13 at 19:43
I suppose this is the closest we can get to a closed form, and I award you the bounty. – George V. Williams Jan 24 '13 at 0:05

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}$$

-

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.

-

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.

-