(+1) Nice method! I discovered another method while solving Challenge 4 to this question, which I have posted. Previously in the limit problem I posted, I used SBP.

Nice solution! The straightforward approach is as Sir Mark has given. How will you do with Summation by parts? I was thinking of somehow using generating functions but it didn't seem quite neat.

## Comments

Sort by:

TopNewestNote that \[ \sum_{r=1}^n \frac{1}{r 2^r} \; = \; \int_0^{\frac12} \big(1 + x + x^2 + \cdots + x^{n-1}\big)\,dx \; = \; \int_0^{\frac12}\frac{1-x^n}{1-x}\,dx \] so that \[ \begin{align} 2^n\left(H_n - \sum_{r=1}^n \frac{1}{r 2^r}\right) & = 2^n \int_{\frac12}^1 \frac{1-x^n}{1-x}\,dx \; = \; 2^n\int_0^{\frac12} \frac{1 - (1-y)^n}{y}\,dy \\ & = 2^n \int_0^{\frac12}\left(\sum_{k=1}^n (-1)^{k-1}{n \choose k} y^{k-1}\right)\,dy \; = \; \sum_{k=1}^n \frac{(-1)^{k-1}2^{n-k}}{k}{n \choose k} \end{align} \] On the other hand, \[ H_n \; = \; \sum_{r=1}^n \frac{(-1)^{r-1}}{r}{n \choose r} \] and hence \[\begin{align} \sum_{r=1}^n {n \choose r}H_r & = \sum_{r=1}^n {n \choose r} \sum_{k=1}^r \frac{(-1)^{k-1}}{k}{r \choose k} \\ & = \sum_{k=1}^n \sum_{r=k}^n \frac{(-1)^{k-1}}{k}{n \choose r}{r \choose k} \\ & = \sum_{k=1}^n \sum_{r=k}^n \frac{(-1)^{k-1}}{k}{n \choose k}{n-k \choose r-k} \; = \; \sum_{k=1}^n \frac{(-1)^{k-1}2^{n-k}}{k}{n \choose k} \end{align} \] and we are done.

Log in to reply

(+1) Nice method! I discovered another method while solving Challenge 4 to this question, which I have posted. Previously in the limit problem I posted, I used SBP.

Log in to reply

From Binomial Coefficient Challenge 4, we have,

\[\sum_{k=0}^{n-1} \dbinom{k}{r} \dfrac{1}{n-k} = \dbinom{n}{r} (H_{n} - H_{r})\]

\[ \implies \sum_{r=0}^{n} \sum_{k=0}^{n-1} \dbinom{k}{r} \dfrac{1}{n-k} = \sum_{r=0}^{n} \left( \dbinom{n}{r} (H_{n} - H_{r}) \right) \]

\[ \implies \sum_{k=0}^{n-1} \dfrac{2^{k}}{n-k} = 2^n H_{n} - \sum_{r=0}^{n} \dbinom{n}{r} H_{r} \]

\[ \implies \sum_{r=0}^{n} \dbinom{n}{r} H_{r} = 2^n H_{n} - \sum_{k=0}^{n-1} \dfrac{2^{k}}{n-k} \]

Re-indexing, we have,

\[\sum_{r=1}^{n} \dbinom{n}{r} H_{r} = 2^{n}\left( H_{n} - \sum_{r=1}^{n} \dfrac{1}{r 2^r} \right) \ \square \]

Another approach can be to use Summation By Parts, although SBP can be long winded.

Log in to reply

Nice solution! The straightforward approach is as Sir Mark has given. How will you do with Summation by parts? I was thinking of somehow using generating functions but it didn't seem quite neat.

Log in to reply

Start with the L.H.S. and use \[ \sum_{k=1}^{r} H_{k} = (r+1)(H_{r+1} - 1) \]

and then using some binomial identities, recreate the sum and along with that, you'll get another term containing with R.H.S.

Log in to reply

@Mark Hennings @Kartik Sharma

Log in to reply