# Binomial Coefficient Challenge 11!

Find a closed form of -

$\large \displaystyle \sum_{k=1}^n{\binom{r}{k} {\left(-1\right)}^k H_k}$

where $$H_k$$ denotes $$k$$th Harmonic number.

Note by Kartik Sharma
1 year ago

MarkdownAppears as
*italics* or _italics_ italics
**bold** or __bold__ bold
- bulleted- list
• bulleted
• list
1. numbered2. 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 1paragraph 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}$$

Sort by:

Theorem : $\sum_{r=1}^{m} (-1)^r \dbinom{n}{r} H_{r} = (-1)^m \dbinom{n-1}{m} \left( H_{m} + \dfrac{1}{n} \right) - \dfrac{1}{n}$

Let,

$\text{S} = \sum_{r=1}^{m} (-1)^r \dbinom{n}{r} H_{r}$

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})$

For $$r \geq 1$$,

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

$\implies \sum_{k=1}^{n-1} \sum_{r=1}^{m} (-1)^r \dbinom{k}{r} \dfrac{1}{n-k} = H_{n} \sum_{r=1}^{m} (-1)^r \dbinom{n}{r} - \sum_{r=1}^{m} (-1)^r \dbinom{n}{r} H_{r}$

$\implies \sum_{k=1}^{n-1} \left((-1)^m \dbinom{k-1}{m} - 1 \right)\dfrac{1}{n-k} = H_{n} \left[ (-1)^m \dbinom{n-1}{m} - 1 \right] - \text{S}$

$\implies (-1)^m \sum_{k=0}^{n-2} \dbinom{k}{m} \dfrac{1}{n-k-1} - H_{n-1} = (-1)^m H_{n} \dbinom{n-1}{m} - H_{n} - \text{S}$

$\implies \text{S} = (-1)^m \dbinom{n-1}{m} \left( H_{m} + \dfrac{1}{n} \right) - \dfrac{1}{n}$

$\therefore \sum_{r=1}^{m} (-1)^r \dbinom{n}{r} H_{r} = (-1)^m \dbinom{n-1}{m} \left( H_{m} + \dfrac{1}{n} \right) - \dfrac{1}{n} \quad \square$

For $$m \geq n$$, we see that the first term vanishes and we are left with the special case,

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

- 1 year ago

There is no typo. It is a finite sum and the answer should be valid for any $$r$$ and $$n$$.

- 1 year ago

I have answered for a general case. I have used $$n$$ and $$m$$ instead of $$r$$ and $$n$$. Btw, what's your approach?

- 1 year ago

If we define $a_n \; = \; \left\{ \begin{array}{lll} -\tfrac{1}{n} & \hspace{1cm} & n \ge 1 \\ 0 & & n = 0 \end{array}\right. \hspace{2cm} b_n \; = \; \left\{ \begin{array}{lll} H_n & \hspace{1cm} & n \ge 1 \\ 0 & & n = 0 \end{array} \right.$ then $H_n \; = \; -\sum_{k=1}^n \binom{n}{k} (-1)^k \frac{1}{k} \hspace{2cm} n \ge 1$ so that $b_n \; = \; \sum_{k=0}^n \binom{n}{k} (-1)^k a_k$ and so, since we are using the Binomial Transform here, $a_n \; = \; \sum_{k=0}^n \binom{n}{k} (-1)^k b_k$ and hence $\sum_{k=1}^n \binom{n}{k}(-1)^k H_k \; = \; -\frac{1}{n} \hspace{2cm} n \ge 1$ I presume that there is a slight typo in the question - $$\binom{n}{k}$$ instead of $$\binom{r}{k}$$. Of course, this makes no difference if $$n > r$$.

- 1 year ago

There is no typo. It is a finite sum and the answer should be valid for any $$r$$ and $$n$$.

- 1 year ago

Surprisingly, there is a general closed form too! I discovered it using challenge 4. BCC 4 is indeed an intriguing problem.

- 1 year ago

After some experience in finite calculus, it is not difficult to observe

$$\displaystyle \Delta\left({(-1)}^{k-1}\binom{r-1}{k-1}\right) = \binom{r-1}{k} {(-1)}^k - \binom{r-1}{k-1}{(-1)}^{k-1} = {(-1)}^k \binom{r}{k}$$

And we would be using SBP -

$\displaystyle \sum {u(x) \Delta(v(x))} = u(x)v(x) - \sum {v(x+1) \Delta(u(x)}$

Therefore, our finite sum -

$\displaystyle \sum {\binom{r}{k}{(-1)}^k H_k \delta k}$

$\displaystyle = {(-1)}^{k-1}\binom{r-1}{k-1} H_k - \sum {\binom{r-1}{k}{(-1)}^k \frac{\delta k}{k+1}}$

$\displaystyle = {(-1)}^{k-1}\binom{r-1}{k-1} H_k - \frac{1}{r}\sum {\frac{r}{k+1}\binom{r-1}{k}{(-1)}^k \delta k}$

$\displaystyle = {(-1)}^{k-1}\binom{r-1}{k-1} H_k + \frac{1}{r}\sum {\binom{r}{k+1}{(-1)}^{k+1} \delta k}$

Using our first difference in the sum form,

$\displaystyle = {(-1)}^{k-1}\binom{r-1}{k-1} H_k + \frac{1}{r} {(-1)}^k\binom{r-1}{k}$

Now using the limits $$1$$ and $$n+1$$,

$\displaystyle = {(-1)}^{n}\binom{r-1}{n} H_{n+1} - \frac{1}{r} {(-1)}^n\binom{r-1}{n+1} - 1 + \frac{r-1}{r}$

$\displaystyle = {(-1)}^{n}\binom{r-1}{n} \left(H_n + \frac{1}{r}\right) - \frac{1}{r}$

- 1 year ago

@Ishan Singh @Mark Hennings Try not to use calculus approach.

- 1 year ago