Binomial Coefficient Challenge 12!

Prove that

$\displaystyle \sum_{k=0}^{m-1}{\frac{{(-1)}^k}{\binom{n}{k}} H_k} = \frac{n+1}{n+2}\left(\frac{{(-1)}^{m+1}}{\binom{n+1}{m}}\left(H_m - \frac{1}{n+2}\right) - \frac{1}{n+2}\right)$

where $H_m$ is the $m$ th Harmonic number.

PS - This is what I am getting. If you get something else, you can report.

#Algebra

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.

Markdown	Appears as
`italics` or `_italics_`	italics
`bold` or `__bold__`	bold
- bulleted - list	bulleted list
1. numbered 2. list	numbered 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"

Math	Appears 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

We have,

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

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

$= \sum_{r=1}^{m-1} \dfrac{1}{r} \left[ \sum_{k=0}^{m-1} \left( \dfrac{{(-1)}^k}{\binom{n}{k}} \right) - \sum_{k=0}^{r-1} \left(\dfrac{{(-1)}^k}{\binom{n}{k}} \right) \right]$

$= \sum_{r=1}^{m-1} \dfrac{1}{r} (F(m) - F(r))$

From Binomial Coefficient Challenge 6,

$F(m) = \sum_{k=0}^{m-1} \left( \dfrac{{(-1)}^k}{\binom{n}{k}} \right) = \left(\dfrac{n+1}{n+2}\right) \left(1+\dfrac{(-1)^{m+1}}{\dbinom{n+1}{m}}\right)$

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

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

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

$= \left( \dfrac{n+1}{n+2} \right) \left[ \dfrac{(-1)^{m+1}}{\dbinom{n+1}{m}} H_{m-1} - \dfrac{1}{n+2} \left( 1 + \dfrac{(-1)^m}{\dbinom{n+1}{m-1}} \right) \right]$

Simplifying, we get,

$\sum_{k=0}^{m-1} \dfrac{{(-1)}^k}{\dbinom{n}{k}} H_k = \left(\dfrac{n+1}{n+2} \right)\left( \dfrac{(-1)^{m+1}}{\dbinom{n+1}{m}} \left( H_{m} - \dfrac{1}{n+2} \right) - \dfrac{1}{n+2} \right) \quad \square$

Ishan Singh - 3 years, 11 months ago

The following editing may feel weird if you are seeing it for the first time.

We will use the fact that the finite sum -

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

This is proven here in BCC 6. A finite sum is just like indefinite integral, it must come with a constant but we are going to bound it eventually(where constants will cancel).

Or,

$\displaystyle \Delta\left(\frac{n+1}{n+2} \frac{{(-1)}^{k+1}}{\binom{n+1}{k}}\right) = \frac{{(-1)}^k}{\binom{n}{k}}$

Let

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

Now, we use Summation By Parts -

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

where $\Delta(a(x)) = a(x+1) - a(x)$ .

For the current sum, take $u(k) = H_k, v(k) = \frac{n+1}{n+2} \frac{{(-1)}^{k+1}}{\binom{n+1}{k}}$ .

Then,

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

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

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

Now, we can put our bounds $0$ and $m$ (yes, not $m-1$ )

$\displaystyle = \frac{n+1}{n+2}\left(\frac{{(-1)}^{m+1}}{\binom{n+1}{m}}\left(H_m - \frac{1}{n+2}\right) - \frac{1}{n+2}\right)$

PS - If you think I am cheating, then I must tell you that this method may not look like clever, but the theorems of finite calculus I have used(without mentioning) is just basic algebra. It simplifies many sums by cutting the repetitive tasks we would do for each sum. If you feel interested, grab a book on finite calculus.

Kartik Sharma - 3 years, 11 months ago

@Mark Hennings @Ishan Singh

Kartik Sharma - 3 years, 11 months ago

Check the limits on the LHS - there is no $H_0$ .

Is there any relationship between $m$ and $n$ , or is this general? I can see a possible way through this one, but want to be sure as to the problem before I start...

Mark Hennings - 3 years, 11 months ago

Exactly. There was this problem with $H_0$ . I am not sure what the author is considering it. I have considered it to be zero. It doesn't really show much in the working anyway.

Yes. There is no relation between $m$ and $n$ .

Kartik Sharma - 3 years, 11 months ago

$H_{0}$ is generally defined to be $0$ . One way to look at it is to use the integral definition,

$H_{n} = \int_{0}^{1} \dfrac{x^n - 1}{x-1} \ \mathrm{d}x$

and put $n=0$ .

Btw, what was your approach?

Ishan Singh - 3 years, 11 months ago

@Ishan Singh – Summation by parts. I will post the solution tomorrow.

Kartik Sharma - 3 years, 11 months ago

@Kartik Sharma – Nice. Although my approach is SBP too, just formatted differently. What about BCC11?

Ishan Singh - 3 years, 11 months ago

@Ishan Singh – Sorry for the late reply. I have written solutions for both of them. I was busy lately. Plus I do not think finite calculus is an attractive approach.

BTW,

$H_0 = 0$ should be true due to the generalized harmonic series given by

$\displaystyle H_z = \sum_{k=1}^{\infty}{\left(\frac{1}{k} - \frac{1}{k+z}\right)} = \sum_{n=2}^{\infty}{{(-1)}^n \zeta(n) z^{n-1}}$

It is a good exercise to find the power series expansion(i.e. to prove the second equality) of harmonic series.

Kartik Sharma - 3 years, 11 months ago

There will be a (-) sign before $\dfrac{1}{n+2}$ . Rest is fine.

Ishan Singh - 3 years, 11 months ago

I got a $-$ only but then changed it because I wrongly checked for the case $m=1$ . Thanks!

Kartik Sharma - 3 years, 11 months ago

Math	Appears 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}$