Jtdylktuy

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 ($sumlimits_{k le n} frac{2^k}{k} ge sumlimits_{k le n} frac{2^k}{n+1} ge frac{sumlimits_{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?

For every $n$, $$S_n=sum_{k=1}^nfrac1k2^kgeqslantsum_{k=1}^nfrac1n2^k=frac1n(2^{n+1}-1).$$
On the other hand, for every $u$ in $(0,1)$, $$S_n=sum_{klt un}frac1k2^k+sum_{unleqslant kleqslant n}frac1k2^kleqslantsum_{klt un}2^k+sum_{unleqslant kleqslant n}frac1{un}2^kleqslant2^{un+1}+frac1{un}2^{n+1}.$$ Thus,
$$
2-frac1{2^n}leqslantfrac{n}{2^n}S_nleqslantfrac2u+frac{2n}{2^{(1-u)n}}
$$ which implies $$2leqslantliminf_{ntoinfty}frac{n}{2^n}S_nleqslantlimsup_{ntoinfty}frac{n}{2^n}S_nleqslantfrac2u$$
This holds for every $ult1$ hence

$$lim_{ntoinfty}frac{n}{2^n}S_n=2.$$

(Which confirms your intuition.)

Likewise, for every real number $alpha$, $$lim_{ntoinfty}frac{n^alpha}{2^n}sum_{k=1}^nfrac{2^k}{k^alpha}=2.$$
Likewise (bis), for every real number $xgt1$ and every real number $alpha$,

$$lim_{ntoinfty}frac{n^alpha}{x^n}sum_{k=1}^nfrac{x^k}{k^alpha}=frac{x}{x-1}.$$

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(nlog2)-Ei(log2) sim frac{e^{nlog 2}}{nlog 2}.$$

Taking the odd-order derivatives we find a pattern

$$f'(x) = frac{2^x}{x}left(log2-frac1{x}right)simfrac{2^x}{x}log2\
f'''(x) = frac{2^x}{x}left[left(log2-frac1{x}right)^3+O(x^{-2})right]simfrac{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+ ldotsright)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}$$

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

As the serie $sum u_n$ is nonnegative and diverges, we obtain by Stolz-Cesàro:
$$S_n=displaystylesum_{k=1}^n u_ksim displaystylesum_{k=1}^n (u_{k+1}-u_k)=u_{n+1}-u_1simfrac{2^{n+1}}n.$$

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(nlog(2)) - some constant right] approx frac{1}{n-1} Ei(n log(2))$$

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

$$e^{cxlog(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

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}{2frac{n+1}{n+2}-1}to 1$$