Find a closed form of

\[\displaystyle \sum_{k=0}^{n-1}{\binom{k}{m} H_k}\]

where \(H_k\) is the \(k\)th Harmonic number.

Find a closed form of

\[\displaystyle \sum_{k=0}^{n-1}{\binom{k}{m} H_k}\]

where \(H_k\) is the \(k\)th Harmonic number.

No vote yet

1 vote

×

Problem Loading...

Note Loading...

Set Loading...

## Comments

Sort by:

TopNewest\[ \sum_{k=0}^{n} \dbinom{k}{m} H_{k} = \sum_{k=1}^{n} \dbinom{k}{m} H_{k} \]

\[ = \sum_{k=1}^{n} \sum_{r=1}^{k} \dfrac{1}{r} \dbinom{k}{m} \]

\[ = \sum_{r=1}^{n} \sum_{k=r}^{n} \dfrac{1}{r} \dbinom{k}{m} \]

\[ = \sum_{r=1}^{n} \dfrac{1}{r} \left(\dbinom{n+1}{m+1} - \dbinom{r}{m+1}\right) \]

\[ = \dbinom{n+1}{m+1} H_{n} - \dfrac{1}{m+1} \sum_{r=1}^{n}\dbinom{r-1}{m} \]

\[ = \dbinom{n+1}{m+1} H_{n} - \dfrac{1}{m+1} \dbinom{n}{m+1} \]

\[ \therefore \sum_{k=0}^{n} \dbinom{k}{m} H_{k} = \dbinom{n+1}{m+1}\left(H_{n+1} - \frac{1}{m+1}\right) \ \square\]

Alternatively, we can form a recurence in \(n\) or \(m\) and solve for the closed form. Yet another approach can be to consider the identity \[ \sum_{r=0}^{k-1} \dbinom{r}{m-1} = \dbinom{k}{m} \] and substitute in the sum.

Note that this result also holds for values of \(m\) other than positive integers.

Log in to reply

There is a typo. It should be \(\binom{n}{m+1}\) rather than \(\binom{n+1}{m+1}\). The sum is till \(n-1\).

Easiest of the lot, I guess. Yet another method is to use summation by parts. It was intended for that.

Log in to reply

Beside \(H_{n}\)? I have checked numerically, seems fine. Btw, my method is Summation By Parts only, if you look closely.

Log in to reply

Oh, indeed now I see. I was looking for the formal method, lol.

Log in to reply

Log in to reply

Log in to reply

solution of the latest problem based on Challenge 4.

Yeah, it can further be tidied up. I'll edit it. Btw, check out myLog in to reply