Waste less time on Facebook — follow Brilliant.
×

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
5 months 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

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

Ishan Singh - 4 months, 4 weeks ago

Log in to reply

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

Kartik Sharma - 4 months, 4 weeks ago

Log in to reply

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

Ishan Singh - 4 months, 4 weeks ago

Log in to reply

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

Mark Hennings - 4 months, 4 weeks ago

Log in to reply

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

Kartik Sharma - 4 months, 4 weeks ago

Log in to reply

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

Ishan Singh - 4 months, 4 weeks ago

Log in to reply

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

Kartik Sharma - 4 months, 3 weeks ago

Log in to reply

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

Kartik Sharma - 5 months ago

Log in to reply

×

Problem Loading...

Note Loading...

Set Loading...