×

Binomial Coefficient Challenge 10

Prove That

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

Note by Ishan Singh
4 months ago

Sort by:

Note 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.

- 4 months ago

(+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.

- 4 months ago

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.

- 4 months ago

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.

- 4 months ago

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.

- 4 months ago