A sum similar to Harmonic numbers.

Question

Consider the sum $$S_n=\sum_{r=2}^n \frac{(-1)^r\binom{n}{r}}{r-1} $$ My question is: What is the asymptotic for $S_n$ as $n\to \infty$ or find $R_n$ such that $S_n\sim R_n$ as $n\to \infty$.

My try: Define the $n$th Harmonic number as $$H_n=\sum_{r=1}^n \frac{1}{r}$$ Then we also have (see https://en.m.wikipedia.org/wiki/Harmonic_number ) $$H_n=\sum_{r=1}^{n} \frac{(-1)^{r-1} \binom{n}{r} }{r} $$ Then we have the asymptotic equivalence of $H_n$ as $$H_n\sim \log n+\gamma +\mathcal{O}\left(\frac{1}{n}\right)$$ How to find the asymptotic equivalence of $S_n$?

Answer 1

Note that \begin{align*} S_n & = \sum\limits_{r = 2}^n {\frac{{( - 1)^r }}{{r - 1}}\binom{n}{r}} = n\sum\limits_{r = 1}^{n - 1} {\frac{{( - 1)^{r +1} }}{{r(r + 1)}}\binom{n-1}{r}} \\ & = n\sum\limits_{r = 1}^{n - 1} {\frac{{( - 1)^{r + 1} }}{r}\binom{n-1}{r}} + n\sum\limits_{r = 1}^{n - 1} {\frac{{( - 1)^r }}{{r + 1}}\binom{n-1}{r}} \\ & = nH_{n - 1} + n\int_0^1 {\left[ {(1 - x)^{n - 1} - 1} \right]dx} = nH_{n - 1} - n\frac{{n - 1}}{n} \\ &= nH_n - n. \end{align*} Thus, we have an exact expression for $S_n$ in terms of $H_n$. The asymptotic expansion follows from that of $H_n$, i.e., $$ S_n \sim n\log n - (1 - \gamma )n + \frac{1}{2} - \frac{1}{{12n}} + \frac{1}{{120n^3 }} - \cdots $$ as $n\to +\infty$.

Answer 2

Starting with the binomial identity $$(1-x)^n = \sum_{r = 0}^{n}(-1)^r\dbinom{n}{r}x^r,$$ we can subtract $1-nx$ from both sides and divide both sides by $x^2$ to get $$\dfrac{(1-x)^n-1+nx}{x^2} = \sum_{r = 2}^{n}(-1)^r\dbinom{n}{r}x^{r-2}.$$ Integrating both sides from $0$ to $1$ yields $$\int_{0}^{1}\dfrac{(1-x)^n-1+nx}{x^2}\,dx = \sum_{r = 2}^{n}\dfrac{(-1)^r\binom{n}{r}}{r-1} = S_n.$$ So we can find asymptotic for $S_n$ using the above integral. We split the integral into two pieces. One over $[0,1/n]$ and one over $[1/n,1]$.

For the first piece, one can check that $f(x) := \tfrac{(1-x)^n-1+nx}{x^2}$ is decreasing on $[0,1/n]$, and so $$\dfrac{1}{n}f\left(\dfrac{1}{n}\right) \le \int_{0}^{1/n}f(x)\,dx \le \dfrac{1}{n}f(0),$$ $$\dfrac{1}{n} \cdot n^2\left(1-\tfrac{1}{n}\right)^n \le \int_{0}^{1/n}\dfrac{(1-x)^n-1+nx}{x^2}\,dx \le \dfrac{1}{n} \cdot \dbinom{n}{2}$$ $$n\left(1-\tfrac{1}{n}\right)^n \le \int_{0}^{1/n}\dfrac{(1-x)^n-1+nx}{x^2}\,dx \le \dfrac{n-1}{2}$$ $$\dfrac{n-1}{e} \le \int_{0}^{1/n}\dfrac{(1-x)^n-1+nx}{x^2}\,dx \le \dfrac{n-1}{2},$$ where we have slightly weakened the lower bound from $n\left(1-\tfrac{1}{n}\right)^n$ to $e^{-1}(n-1)$ in the last step.

For the second piece, we note that $0 \le (1-x)^n \le \left(1-\tfrac{1}{n}\right)^n \le e^{-1}$ for all $x \in [1/n,1]$, and so $$\int_{1/n}^{1}\dfrac{-1+nx}{x^2}\,dx \le \int_{1/n}^{1}\dfrac{(1-x)^n-1+nx}{x^2}\,dx \le \int_{1/n}^{1}\dfrac{e^{-1}-1+nx}{x^2}\,dx$$ $$n\log n - (n-1) \le \int_{1/n}^{1}\dfrac{(1-x)^n-1+nx}{x^2}\,dx \le n\log n - \left(1-\dfrac{1}{e}\right)(n-1)$$

Combining these two bounds yields: $$n\log n - \left(1-\dfrac{1}{e}\right)(n-1) \le \int_{0}^{1}\dfrac{(1-x)^n-1+nx}{x^2}\,dx \le n\log n - \left(\dfrac{1}{2}-\dfrac{1}{e}\right)(n-1),$$ and thus, $S_n = n\log n + O(n)$.