10
$\begingroup$

I'm looking for an asymptotic equivalent of

$$\sum_{0 < k \le n} \frac{2^k}{k}$$

as $n \to \infty$. A plausible candidate seems to be $\frac{2^{n+1}}{n+1}$ (WolframAlpha plot, and the intuitive similarity with $\sum_{k \le n} 2^k = 2^{n+1}$ is also appealing), but my usual tricks seem powerless here.

I've tried:

  • Interpreting $x^k/k$ as the primitive of $x^{k-1}$ and setting $x=2$
  • Replacing $2^k/k$ with $\int_{x=0}^2 x^{k-1}$
  • Reordering the sum's terms to expose log-resembling sub-sums like $\sum_k 1/k$
  • Finding lower and upper bounds asymptotically equivalent to $\frac{2^{n+1}}{n+1}$ -- the lower bound is easy ($\sum\limits_{k \le n} \frac{2^k}{k} \ge \sum\limits_{k \le n} \frac{2^k}{n+1} \ge \frac{\sum\limits_{k \le n} 2^k}{n+1} \ge \frac{2^{n+1}}{n+1}$), but the upper bound seems trickier (I couldn't think of a sequence $\varepsilon_k \in o(2^k/k)$ that would make it easy to estimate $\sum_{0 < k \le n} 2^k/k - \varepsilon_k$)
  • ... and a few others, to no avail

Any hints?

$\endgroup$
3
  • $\begingroup$ I'd think interpreting this as a certain evaluation of a logarithm to be the soundest approach, since one can bring some tools from complex analysis to bear on such. $\endgroup$ – Semiclassical Aug 5 '14 at 17:54
  • $\begingroup$ Call your sum $S_n$. Let $T_n = S_n/2^n$; then it's not hard to show that $T_1 = 1$, $T_n = T_{n-1}/2 + 1/n$. You want to show $T_n \sim 2/(n+1)$. Not sure this helps. $\endgroup$ – Michael Lugo Aug 5 '14 at 18:51
  • 1
    $\begingroup$ You mean $1\leq k \leq n$. $\endgroup$ – Mhenni Benghorbal Aug 5 '14 at 19:08
11
$\begingroup$

For every $n$, $$S_n=\sum_{k=1}^n\frac1k2^k\geqslant\sum_{k=1}^n\frac1n2^k=\frac1n(2^{n+1}-1).$$ On the other hand, for every $u$ in $(0,1)$, $$S_n=\sum_{k\lt un}\frac1k2^k+\sum_{un\leqslant k\leqslant n}\frac1k2^k\leqslant\sum_{k\lt un}2^k+\sum_{un\leqslant k\leqslant n}\frac1{un}2^k\leqslant2^{un+1}+\frac1{un}2^{n+1}.$$ Thus, $$ 2-\frac1{2^n}\leqslant\frac{n}{2^n}S_n\leqslant\frac2u+\frac{2n}{2^{(1-u)n}} $$ which implies $$2\leqslant\liminf_{n\to\infty}\frac{n}{2^n}S_n\leqslant\limsup_{n\to\infty}\frac{n}{2^n}S_n\leqslant\frac2u$$ This holds for every $u\lt1$ hence

$$\lim_{n\to\infty}\frac{n}{2^n}S_n=2.$$

(Which confirms your intuition.)

Likewise, for every real number $\alpha$, $$\lim_{n\to\infty}\frac{n^\alpha}{2^n}\sum_{k=1}^n\frac{2^k}{k^\alpha}=2.$$ Likewise (bis), for every real number $x\gt1$ and every real number $\alpha$,

$$\lim_{n\to\infty}\frac{n^\alpha}{x^n}\sum_{k=1}^n\frac{x^k}{k^\alpha}=\frac{x}{x-1}.$$

$\endgroup$
3
  • 1
    $\begingroup$ Thanks! I find the "This holds for every ... hence" line a bit confusing though :/ Once you multiply both sides by $n/2^n$ and look at $u \to 1$, doesn't the upper bound reduce to $2n+2$ instead of just $2+\varepsilon_n$? Or did I miss something? $\endgroup$ – Clément Aug 5 '14 at 23:01
  • $\begingroup$ Once one multiplies both sides by $n/2^n$ and one considers the limit $n\to\infty$, one sees that the limsup is at most $2/u$. This holds for every $u\lt1$ (no limit here) hence the limsup us $\leqslant2$, QED. $\endgroup$ – Did Aug 6 '14 at 8:23
  • $\begingroup$ Alright, this makes a lot of sense. Very nice solution! $\endgroup$ – Clément Aug 7 '14 at 22:17
6
$\begingroup$

The Euler-Maclaurin summation formula is useful for approximating sums and often reveals the asymptotic behavior with only a few terms. This problem is an interesting application because the precise asymptotic behavior requires summing an infinite number of terms with Bernoulli numbers as coefficients - the terms that are typically neglected.

Using the Euler-Maclaurin summation formula with $f(x) = 2^x/x$

$$\sum_{k=1}^{n}\frac{2^k}{k} = C+\int_{1}^{n}f(x)\,dx + \frac1{2}f(n)+\frac{B_2}{2!}f'(n) + \frac{B_4}{4!}f'''(n)+ \ldots.$$

The integral is the exponential integral which behaves asymptotically as $Ei(x) \sim e^x/x$ as $x \rightarrow \infty:$

$$\int_{1}^{n}f(x)\,dx=\int_{1}^{n}\frac{2^x}{x}\,dx= Ei(n\log2)-Ei(\log2) \sim \frac{e^{n\log 2}}{n\log 2}.$$

Taking the odd-order derivatives we find a pattern

$$f'(x) = \frac{2^x}{x}\left(\log2-\frac1{x}\right)\sim\frac{2^x}{x}\log2\\ f'''(x) = \frac{2^x}{x}\left[\left(\log2-\frac1{x}\right)^3+O(x^{-2})\right]\sim\frac{2^x}{x}(\log 2)^3\\ \ldots$$

Hence,

$$\sum_{k=1}^{n}\frac{2^k}{k} \sim \frac{2^n}{n}\left[\frac1{\log 2}+\frac1{2}+\frac1{\log 2}\left(\frac{B_2}{2!}(\log 2)^2 + \frac{B_4}{4!}(\log 2)^4+ \ldots\right)\right]\,\,(*)$$

The trailing terms can be summed exactly. The generating function for the Bernoulli numbers is $x/(e^x-1)$ where

$$\frac{x}{e^x-1} = \sum_{k=0}^{\infty}\frac{B_kx^k}{k!}.$$

The first two Bernoulli numbers are $B_0 = 1$ and $B_1 = -1/2$. They are zero for odd $n \geq 3$.

Hence,

$$\sum_{k=2}^{\infty}\frac{B_k(\log 2)^k}{k!} = \frac{\log 2}{e^{\log 2}-1}-1 + \frac{\log 2}{2}= \log 2-1 + \frac{\log 2}{2}.$$

Substituting into $(*)$ we get

$$\sum_{k=1}^{n}\frac{2^k}{k} \sim \frac{2^n}{n}\left[\frac1{\log 2}+\frac1{2}+\frac1{\log 2}\left(\log 2-1 + \frac{\log 2}{2}\right)\right]=\frac{2^n}{n}2,$$

and

$$\sum_{k=1}^{n}\frac{2^k}{k} \sim \frac{2^{n+1}}{n}$$

$\endgroup$
1
  • $\begingroup$ Very interesting calculation. I'm accepting the simpler answer, but this is indeed an interesting case where the small trends add up. Nice one! $\endgroup$ – Clément Aug 7 '14 at 22:19
3
$\begingroup$

If $u_n=\dfrac{2^n}n$, we have $u_{n+1}-u_n\sim\dfrac{2^n}n=u_n$.

As the serie $\sum u_n$ is nonnegative and diverges, we obtain by Stolz-Cesàro: $$S_n=\displaystyle\sum_{k=1}^n u_k\sim \displaystyle\sum_{k=1}^n (u_{k+1}-u_k)=u_{n+1}-u_1\sim\frac{2^{n+1}}n.$$

$\endgroup$
2
$\begingroup$

Your intuition is correct, we have

$$\frac{a_n}{b_n}=\frac{\sum_{k=1}^n \frac{2^k}{k}}{\frac{2^{n+1}}{n+1}} \to 1$$

indeed by Stolz-Cesaro

$$\frac{a_{n+1}-a_n}{b_{n+1}-b_n}=\frac{\frac{2^{n+1}}{n+1}}{\frac{2^{n+2}}{n+2}-\frac{2^{n+1}}{n+1}}=\frac{1}{2\frac{n+1}{n+2}-1}\to 1$$

$\endgroup$
0
$\begingroup$

We note that the average value of

$$\frac{2^k}{k}$$

is given by

$$ \frac{1}{n-1} \int_1^n{\frac{2^n}{n} dn} = \frac{1}{n-1} \left[Ei(n\log(2)) - some constant \right] \approx \frac{1}{n-1} Ei(n \log(2))$$

We note that $$e^{x\log(2)}$$ is asymptotically greater than $$Ei(x\log(2))$$ but it appears that I cannot find a constant $c$ between 0 and 1 such that

$$e^{cx\log(2)}$$ is also asymptotically greater suggesting these two asymptotic classes may have a more intricate relationship than is apparent

For all intents and purposes $\frac{2^n}{n}$ is asymptotically equivalent. To find something that matches the difference of terms more closely will require heavier machinery

$\endgroup$
3
  • 1
    $\begingroup$ Side note: You seem to be using $n$ as both a bound variable under the integral, and unbound outside; that's somewhat confusing. $\endgroup$ – Clément Aug 5 '14 at 20:19
  • $\begingroup$ @Clément I understand intuitively that doing doesn't have any geometric interpretation, but I've never found a time when such a symbolic calculation has ever given me issues. Why is there so much opposition to doing so? It seems like a natural way to incorporate indefinite integration into the frame work of definite integrals $\endgroup$ – frogeyedpeas Aug 5 '14 at 21:26
  • $\begingroup$ Well, you have a definite integral here. It looks a bit like writing $\forall x, \forall x, x-x=0$, which might be formally valid, but is still confusing. $\endgroup$ – Clément Aug 5 '14 at 22:44

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.