Binomial Coefficient Challenge 11!

Find a closed form of -

∑k=1n(rk)(−1)kHk\large \displaystyle \sum_{k=1}^n{\binom{r}{k} {\left(-1\right)}^k H_k}

where HkH_k denotes kkth Harmonic number.

#Algebra

Note by Kartik Sharma
3 years, 11 months ago

No vote yet
1 vote

  Easy Math Editor

This discussion board is a place to discuss our Daily Challenges and the math and science related to those challenges. Explanations are more than just a solution — they should explain the steps and thinking strategies that you used to obtain the solution. Comments should further the discussion of math and science.

When posting on Brilliant:

  • Use the emojis to react to an explanation, whether you're congratulating a job well done , or just really confused .
  • Ask specific questions about the challenge or the steps in somebody's explanation. Well-posed questions can add a lot to the discussion, but posting "I don't understand!" doesn't help anyone.
  • Try to contribute something new to the discussion, whether it is an extension, generalization or other idea related to the challenge.
  • Stay on topic — we're all here to learn more about math and science, not to hear about your favorite get-rich-quick scheme or current world events.

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×3 2 \times 3
2^{34} 234 2^{34}
a_{i-1} ai−1 a_{i-1}
\frac{2}{3} 23 \frac{2}{3}
\sqrt{2} 2 \sqrt{2}
\sum_{i=1}^3 ∑i=13 \sum_{i=1}^3
\sin \theta sin⁡θ \sin \theta
\boxed{123} 123 \boxed{123}

Comments

Theorem : ∑r=1m(−1)r(nr)Hr=(−1)m(n−1m)(Hm+1n)−1n\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,

S=∑r=1m(−1)r(nr)Hr \text{S} = \sum_{r=1}^{m} (-1)^r \dbinom{n}{r} H_{r}

From Binomial Coefficient Challenge 4, we have,

∑k=0n−1(kr)1n−k=(nr)(Hn−Hr) \sum_{k=0}^{n-1} \dbinom{k}{r} \dfrac{1}{n-k} = \dbinom{n}{r} (H_{n} - H_{r})

For r≥1r \geq 1,

∑k=1n−1(kr)1n−k=(nr)(Hn−Hr) \sum_{k=1}^{n-1} \dbinom{k}{r} \dfrac{1}{n-k} = \dbinom{n}{r} (H_{n} - H_{r})

  ⟹  ∑k=1n−1∑r=1m(−1)r(kr)1n−k=Hn∑r=1m(−1)r(nr)−∑r=1m(−1)r(nr)Hr \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}

  ⟹  ∑k=1n−1((−1)m(k−1m)−1)1n−k=Hn[(−1)m(n−1m)−1]−S \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}

  ⟹  (−1)m∑k=0n−2(km)1n−k−1−Hn−1=(−1)mHn(n−1m)−Hn−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}

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

∴∑r=1m(−1)r(nr)Hr=(−1)m(n−1m)(Hm+1n)−1n□ \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≥nm \geq n, we see that the first term vanishes and we are left with the special case,

∑r=1n(−1)r(nr)Hr=−1n \sum_{r=1}^{n} (-1)^r \dbinom{n}{r} H_{r} = - \dfrac{1}{n}

Ishan Singh - 3 years, 11 months ago

Log in to reply

There is no typo. It is a finite sum and the answer should be valid for any rr and nn.

Kartik Sharma - 3 years, 11 months ago

Log in to reply

I have answered for a general case. I have used nn and mm instead of rr and nn. Btw, what's your approach?

Ishan Singh - 3 years, 11 months ago

If we define an  =  {−1nn≥10n=0bn  =  {Hnn≥10n=0 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 Hn  =  −∑k=1n(nk)(−1)k1kn≥1 H_n \; = \; -\sum_{k=1}^n \binom{n}{k} (-1)^k \frac{1}{k} \hspace{2cm} n \ge 1 so that bn  =  ∑k=0n(nk)(−1)kak b_n \; = \; \sum_{k=0}^n \binom{n}{k} (-1)^k a_k and so, since we are using the Binomial Transform here, an  =  ∑k=0n(nk)(−1)kbk a_n \; = \; \sum_{k=0}^n \binom{n}{k} (-1)^k b_k and hence ∑k=1n(nk)(−1)kHk  =  −1nn≥1 \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 - (nk)\binom{n}{k} instead of (rk)\binom{r}{k}. Of course, this makes no difference if n>rn > r.

Mark Hennings - 3 years, 11 months 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 - 3 years, 11 months ago

There is no typo. It is a finite sum and the answer should be valid for any rr and nn.

Kartik Sharma - 3 years, 11 months ago

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

Δ((−1)k−1(r−1k−1))=(r−1k)(−1)k−(r−1k−1)(−1)k−1=(−1)k(rk)\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 -

∑u(x)Δ(v(x))=u(x)v(x)−∑v(x+1)Δ(u(x)\displaystyle \sum {u(x) \Delta(v(x))} = u(x)v(x) - \sum {v(x+1) \Delta(u(x)}

Therefore, our finite sum -

∑(rk)(−1)kHkδk\displaystyle \sum {\binom{r}{k}{(-1)}^k H_k \delta k}

=(−1)k−1(r−1k−1)Hk−∑(r−1k)(−1)kδkk+1\displaystyle = {(-1)}^{k-1}\binom{r-1}{k-1} H_k - \sum {\binom{r-1}{k}{(-1)}^k \frac{\delta k}{k+1}}

=(−1)k−1(r−1k−1)Hk−1r∑rk+1(r−1k)(−1)kδk\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}

=(−1)k−1(r−1k−1)Hk+1r∑(rk+1)(−1)k+1δ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,

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

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

=(−1)n(r−1n)Hn+1−1r(−1)n(r−1n+1)−1+r−1r\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}

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

Kartik Sharma - 3 years, 11 months ago

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

Kartik Sharma - 3 years, 11 months ago
×

Problem Loading...

Note Loading...

Set Loading...