Waste less time on Facebook — follow Brilliant.
×

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

No vote yet
1 vote

Comments

Sort by:

Top Newest

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.

Mark Hennings - 4 months ago

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.

Ishan Singh - 4 months ago

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 - 4 months ago

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.

Kartik Sharma - 4 months ago

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.

Ishan Singh - 4 months ago

Log in to reply

Log in to reply

×

Problem Loading...

Note Loading...

Set Loading...