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
11 months, 1 week ago

No vote yet
1 vote

  Easy Math Editor

MarkdownAppears as
*italics* or _italics_ italics
**bold** or __bold__ bold

- bulleted
- list

  • bulleted
  • list

1. numbered
2. list

  1. numbered
  2. list
Note: you must add a full line of space before and after lists for them to show up correctly
paragraph 1

paragraph 2

paragraph 1

paragraph 2

[example link](https://brilliant.org)example link
> This is a quote
This is a quote
    # I indented these lines
    # 4 spaces, and now they show
    # up as a code block.

    print "hello world"
# I indented these lines
# 4 spaces, and now they show
# up as a code block.

print "hello world"
MathAppears as
Remember to wrap math in \( ... \) or \[ ... \] to ensure proper formatting.
2 \times 3 \( 2 \times 3 \)
2^{34} \( 2^{34} \)
a_{i-1} \( a_{i-1} \)
\frac{2}{3} \( \frac{2}{3} \)
\sqrt{2} \( \sqrt{2} \)
\sum_{i=1}^3 \( \sum_{i=1}^3 \)
\sin \theta \( \sin \theta \)
\boxed{123} \( \boxed{123} \)

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 - 11 months, 1 week 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 - 11 months, 1 week 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.

Ishan Singh - 11 months, 1 week 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 - 11 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 - 11 months ago

Log in to reply

@Mark Hennings @Kartik Sharma

Ishan Singh - 11 months, 1 week ago

Log in to reply

×

Problem Loading...

Note Loading...

Set Loading...