2

I encountered a problem when I was doing my homework where I had to find this$$\lim_{n\to\infty}\left(\frac{1}{n}+\frac{1}{2^n-1}\sum_{k=1}^{n} \frac{n \choose k}{k}\right)$$ I guess it may be about $0.1$ but till now I have no idea about it after I tried all the methods I've learned. (I'm just a freshman so I know little in this area)

an4s
  • 3,716
jacker73
  • 21
  • 2

2 Answers2

2

The limit can be split as $$\lim_{n \to \infty} \frac{1}{n} + \lim_{n \to \infty} \left(\frac{1}{2^n-1} \sum_{k=1}^n \frac{\binom{n}{k}}{k}\right)$$

The first limit is $0$, which is easy to see. Using that $\frac{1}{k} = \int_0^1 x^{k-1} dx$, the sum in the second limit is $$\sum_{k=1}^n \binom{n}{k} \int_0^1 x^{k-1} dx = \int_0^1 \sum_{k=1}^n \binom{n}{k} x^{k-1} dx = \int_0^1 \frac{(x+1)^n-1}{x} dx$$

Then the second limit is $$\lim_{n \to \infty}\frac{\int_0^1 \frac{(x+1)^n-1}{x}dx}{2^n-1} \le \lim_{n \to \infty} \frac{\int_0^1 \frac{(x+1)^n-1}{x}dx}{2^n} = \lim_{n \to \infty} \int_0^1 \frac{\left(\frac{x+1}{2}\right)^n-\frac{1}{2^n}}{x}dx$$

Since the integrand converges uniformly to $0$ for $x \in [0, 1)$ and the integral limits are finite, the integral is then $0$. Therefore, the second limit would be less than or equal to $0$. However, the limit must be nonnegative because it is a sum of nonnegative terms, so the limit must be $0$.

Therefore $$\lim_{n\to\infty}\left(\frac{1}{n}+\frac{1}{2^n-1}\sum_{k=1}^n \frac{\binom{n}{k}}{k}\right) = 0$$

Edit: As pointed out by metamorphy in the comments, this does not completely hold up since the integrand does not converge to $0$ uniformly for $x \in [0, 1]$. Instead, splitting the integral as $$\int_0^{1-\epsilon} \frac{\left(\frac{x+1}{2}\right)^n-\frac{1}{2^n}}{x} dx+\int_{1-\epsilon}^1 \frac{\left(\frac{x+1}{2}\right)^n-\frac{1}{2^n}}{x} dx$$

where $\epsilon$ approaches $0$ from the positive side. Then the integrand would converge uniformly to $0$ for $x \in [0, 1-\epsilon]$ so the first integral would converge to $0$ as well. The integrand in the second integral would converge to a finite limit, but since the lower integration bound approaches the upper bound of $1$, the second integral would approach $0$. Therefore, the overall integral would approach $0$.

Varun Vejalla
  • 8,873
  • ...the integrand converges uniformly to 0... - wrong, at $x=1$ it converges to $1$. (This doesn't break the whole idea, though.) – metamorphy Sep 26 '20 at 15:13
  • @metamorphy Is this better now? I excluded $x=1$ from uniform convergence to $0$. – Varun Vejalla Sep 26 '20 at 15:17
  • 1
    No. You don't have uniform convergence, and need something more "delicate". – metamorphy Sep 26 '20 at 15:18
  • @metamorphy Sorry, I'm not following. Wouldn't $\frac{\left( \frac{x+1}{2} \right)^n-\frac{1}{2^n}}{x} \to 0$ for all $x$ in $[0, 1)$? Maybe I'm misunderstanding uniform convergence. – Varun Vejalla Sep 26 '20 at 15:20
  • For uniform convergence, you must have $\lim\limits_{n\to\infty}\color{blue}{\sup\limits_{x\in(0,1)}}f_n(x)=0$, where $f_n(x)$ is the integrand. And this doesn't hold in our case, because the limit of $f_n(1-1/n)$ [say] is nonzero. [In fact $f_n(1-1/n^2)$ tends to $1$.] – metamorphy Sep 26 '20 at 15:29
  • (To fix it, just split $\int_0^1=\int_0^{1-\epsilon}+\int_{1-\epsilon}^1$...) – metamorphy Sep 26 '20 at 15:42
  • @metamorphy Ok thanks for the explanation. I have edited my answer to reflect your comments. – Varun Vejalla Sep 26 '20 at 15:48
2

$\newcommand{\bbx}[1]{\,\bbox[15px,border:1px groove navy]{\displaystyle{#1}}\,} \newcommand{\braces}[1]{\left\lbrace\,{#1}\,\right\rbrace} \newcommand{\bracks}[1]{\left\lbrack\,{#1}\,\right\rbrack} \newcommand{\dd}{\mathrm{d}} \newcommand{\ds}[1]{\displaystyle{#1}} \newcommand{\expo}[1]{\,\mathrm{e}^{#1}\,} \newcommand{\ic}{\mathrm{i}} \newcommand{\mc}[1]{\mathcal{#1}} \newcommand{\mrm}[1]{\mathrm{#1}} \newcommand{\on}[1]{\operatorname{#1}} \newcommand{\pars}[1]{\left(\,{#1}\,\right)} \newcommand{\partiald}[3][]{\frac{\partial^{#1} #2}{\partial #3^{#1}}} \newcommand{\root}[2][]{\,\sqrt[#1]{\,{#2}\,}\,} \newcommand{\totald}[3][]{\frac{\mathrm{d}^{#1} #2}{\mathrm{d} #3^{#1}}} \newcommand{\verts}[1]{\left\vert\,{#1}\,\right\vert}$ \begin{align} &\bbox[5px,#ffd]{\lim_{n \to \infty}\bracks{{1 \over n} + {1 \over 2^{n} - 1}\sum_{k = 1}^{n}{{n \choose k} \over k}}} = \lim_{n \to \infty}\bracks{% {1 \over 2^{n} - 1}\sum_{k = 1}^{n} {{n \choose k} \over k}} \end{align}

Note that \begin{align} \sum_{k = 1}^{n}{{n \choose k} \over k} & = \int_{0}^{1}\sum_{k = 1}^{n}{n \choose k}t^{k - 1} \,\dd t = \int_{0}^{1}{\pars{1 + t}^{n} - 1 \over t}\,\dd t \\[2mm] & = \int_{1}^{2}{t^{n} - 1 \over t - 1}\,\dd t = \int_{1}^{2}\sum_{k = 0}^{n - 1}t^{k}\,\dd t = \sum_{k = 0}^{n - 1}{2^{k + 1} - 1\over k + 1} \\[5mm] & \mbox{and}\,\,\, \lim_{n \to \infty}{1 \over 2^{n} - 1} \sum_{k = 0}^{n - 1}{2^{k + 1} - 1\over k + 1} \\[5mm] & = \lim_{n \to \infty} {\pars{2^{n + 1} - 1}/\pars{n + 1} \over 2^{n}} = \color{red}{\large 0} \end{align} \begin{align} &\mbox{} \\ \implies \bbx{\bbox[5px,#ffd]{\lim_{n \to \infty}\bracks{{1 \over n} + {1 \over 2^{n} - 1}\sum_{k = 1}^{n}{{n \choose k} \over k}}} = 0} \\ & \end{align}
Felix Marin
  • 89,464