Solve $\lim_{n\to\infty} \sum_{r=0}^n \frac{\binom{n}{r}}{(n^r)(r+3)}$

Question

$\lim_{n\to\infty} \sum_{r=0}^n \frac{\binom{n}{r}}{(n^r)(r+3)}$

I have no idea how do I solve this problem. I do know I have to somehow convert this in a function of $\frac{r}{n}$ cause this looks to me as Riemann integral problem.

Any help would be appreciated.

Answer 1

Hint :

$\mathbf{\text{Method 1:}}$

Use that for large enough $n$ we have $$\binom{n}{r}\sim\frac{n^r}{r!}$$

The rest is easy assuming you know the Taylor series of $e$

$\mathbf{\text{Method 2:}}$

Using binomial theorem we have that $$(1+x)^n=\sum_{r=0}^n \binom{n}{r}x^r$$ thus $$x^2(1+x)^n=\sum_{r=0}^n \binom{n}{r}x^{r+2}$$

What happens if you integrate the above equation wrt $x$ from $0$ to $\displaystyle \frac{1}{n}$? (Note that left hand side can be easily integrated using Integration by Parts)

Answer 2

Partial answer:

Using the inequalities $$\frac{1}{r^r} \le n^{-r}\binom{n}{r} \le \frac{1}{r!}$$ we obtain $$\sum_{r=0}^n \frac{1}{r^r(r+3)} \le \sum_{r=0}^n \frac{\binom{n}{r}}{n^r (r+3)} \le \sum_{r=0}^n \frac{1}{r! (r+3)}. \tag{$*$}$$

The right-hand side of ($*$) can be written as \begin{align} \sum_{r=0}^n \frac{1}{r! (r+3)} &= \sum_{r=0}^n \frac{(r+1)(r+2)}{(r+3)!} \\ &= \sum_{r=0}^n \frac{(r+3)(r+2) - 2(r+3) + 2}{(r+3)!} \\ &\overset{n \to \infty}{\longrightarrow} (e - 1) - 2(e - 1 - 1) + 2(e - 1 - 1 - \frac{1}{2}) = e - 2. \end{align}

It remains to lower bound the desired series by $e-2$. Evidently the left-hand side of ($*$) tends to $\approx 0.640 < 0.718 \approx e-2$, so something better is required.

Answer 3

First, by angryavian's answer, we know that for all $n\in\mathbb{N}$

$$\sum_{r=0}^n\frac{\binom{n}{r}}{n^r(r+3)}\leq \sum_{r=0}^{n}\frac{1}{r!(r+3)}\leq e-2.$$

Since these are both sums of positive numbers, we are assured that they both converge. Second, let us look at how the terms in the sum behave as $n$ goes to infinity. That is, for a fixed $r$

$$\lim_{n\to\infty}\frac{\binom{n}{r}}{n^r(r+3)}=\lim_{n\to\infty}\frac{n!}{r!(n-r)!n^r(r+3)}=\left(\frac{1}{r!(r+3)}\right)\lim_{n\to\infty}\frac{n!}{(n-r)!n^r}.$$

Now, note that the terms in the limit can be expanded as

$$\frac{n!}{(n-r)!n^r}=\frac{n(n-1)(n-2)\cdots(n-r+1)}{n^r}.$$

However, note that the numerator is a polynomial of degree $r$ and leading coefficient of $1$. Thus, the limit is

$$\left(\frac{1}{r!(r+3)}\right)\lim_{n\to\infty}\frac{n!}{(n-r)!n^r}=\left(\frac{1}{r!(r+3)}\right)\lim_{n\to\infty}\frac{n^r+...}{n^r}=\frac{1}{r!(r+3)}.$$

Let $\epsilon>0$. Now, we will show that these sums are in fact equal in the limit as $n$ goes to infinity. That is, we will show

$$\lim_{n\to\infty}\left(\sum_{r=0}^n\frac{\binom{n}{r}}{n^r(r+3)}-\sum_{r=0}^n\frac{1}{r!(r+3)}\right)=0$$

Well, we may as well pull out the $r=0$ term to get

$$\lim_{n\to\infty}\left(\sum_{r=0}^n\frac{\binom{n}{r}}{n^r(r+3)}-\sum_{r=0}^n\frac{1}{r!(r+3)}\right)$$

$$=\lim_{n\to\infty}\left(\frac{\binom{n}{r}}{n^0(0+3)}-\frac{1}{0!(0+3)}\right)+\lim_{n\to\infty}\left(\sum_{r=1}^n\frac{\binom{n}{r}}{n^r(r+3)}-\sum_{r=1}^n\frac{1}{r!(r+3)}\right)$$

$$=\left(\frac{1}{0!(0+3)}-\frac{1}{0!(0+3)}\right)+\lim_{n\to\infty}\left(\sum_{r=1}^n\frac{\binom{n}{r}}{n^r(r+3)}-\sum_{r=1}^n\frac{1}{r!(r+3)}\right)$$

$$=\lim_{n\to\infty}\left(\sum_{r=1}^n\frac{\binom{n}{r}}{n^r(r+3)}-\sum_{r=1}^n\frac{1}{r!(r+3)}\right).$$

Of course, we could perform the same maneuver with $r=1$ to conclude that in the limit

$$=\lim_{n\to\infty}\left(\sum_{r=1}^n\frac{\binom{n}{r}}{n^r(r+3)}-\sum_{r=1}^n\frac{1}{r!(r+3)}\right)=\lim_{n\to\infty}\left(\sum_{r=2}^n\frac{\binom{n}{r}}{n^r(r+3)}-\sum_{r=2}^n\frac{1}{r!(r+3)}\right).$$

In fact, for any $r_0\in\mathbb{N}$, we can say

$$=\lim_{n\to\infty}\left(\sum_{r=r_0}^n\frac{\binom{n}{r}}{n^r(r+3)}-\sum_{r=r_0}^n\frac{1}{r!(r+3)}\right).$$

However, from the beginning of the proof we know that the sum on the right is convergent. Thus, there exists $R$ such that the tail of the sum (past $R$) is less than $\epsilon /2$. That is, for $r_0\geq R$

$$\lim_{n\to\infty}\sum_{r=r_0}^n\frac{1}{r!(r+3)}\leq \frac{\epsilon}{2}.$$

Then using the inequality established above (again, from angryavian's answer) we also know that for $r_0\geq R$

$$\lim_{n\to\infty}\sum_{r=r_0}^n\frac{\binom{n}{r}}{n^r(r+3)}\leq \lim_{n\to\infty}\sum_{r=r_0}^n\frac{1}{r!(r+3)}\leq \frac{\epsilon}{2}.$$

Then for $r_0\geq R$

$$\lim_{n\to\infty}\left(\sum_{r=r_0}^n\frac{\binom{n}{r}}{n^r(r+3)}-\sum_{r=r_0}^n\frac{1}{r!(r+3)}\right)=\lim_{n\to\infty}\sum_{r=r_0}^n\frac{\binom{n}{r}}{n^r(r+3)}-\lim_{n\to\infty}\sum_{r=r_0}^n\frac{1}{r!(r+3)}$$

$$=\left|\lim_{n\to\infty}\sum_{r=r_0}^n\frac{\binom{n}{r}}{n^r(r+3)}\right|-\left|\lim_{n\to\infty}\sum_{r=r_0}^n\frac{1}{r!(r+3)}\right|$$

$$\leq \left|\lim_{n\to\infty}\sum_{r=r_0}^n\frac{\binom{n}{r}}{n^r(r+3)}\right|+\left|\lim_{n\to\infty}\sum_{r=r_0}^n\frac{1}{r!(r+3)}\right|\leq \frac{\epsilon}{2}+\frac{\epsilon}{2}=\epsilon.$$

We conclude that

$$\lim_{n\to\infty}\left(\sum_{r=0}^n\frac{\binom{n}{r}}{n^r(r+3)}-\sum_{r=0}^n\frac{1}{r!(r+3)}\right)=0$$

and thus

$$\lim_{n\to\infty}\sum_{r=0}^n\frac{\binom{n}{r}}{n^r(r+3)}=\lim_{n\to\infty}\sum_{r=0}^n\frac{1}{r!(r+3)}$$

Finally, again referencing angryavian's answer, we know the right hand side of this goes to $e-2$. Thus, the original limit in question is $e-2$.