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) \]

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) \]

No vote yet

1 vote

×

Problem Loading...

Note Loading...

Set Loading...

## 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. – Mark Hennings · 1 month, 3 weeks ago

Log in to reply

– Ishan Singh · 1 month, 3 weeks 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.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. – Ishan Singh · 1 month, 3 weeks ago

Log in to reply

– Kartik Sharma · 1 month, 3 weeks 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.Log in to reply

and then using some binomial identities, recreate the sum and along with that, you'll get another term containing with R.H.S. – Ishan Singh · 1 month, 3 weeks ago

Log in to reply

@Mark Hennings @Kartik Sharma – Ishan Singh · 1 month, 3 weeks ago

Log in to reply