Waste less time on Facebook — follow Brilliant.
×

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.

Note by Kartik Sharma
3 months, 4 weeks ago

No vote yet
1 vote

Comments

Sort by:

Top Newest

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 months, 3 weeks ago

Log in to reply

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 months, 3 weeks ago

Log in to reply

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

Ishan Singh - 3 months, 3 weeks ago

Log in to reply

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

Kartik Sharma - 3 months, 3 weeks ago

Log in to reply

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 months, 4 weeks ago

Log in to reply

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 months, 3 weeks ago

Log in to reply

\(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 months, 3 weeks ago

Log in to reply

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

Kartik Sharma - 3 months, 3 weeks ago

Log in to reply

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

Ishan Singh - 3 months, 3 weeks ago

Log in to reply

@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 months, 3 weeks ago

Log in to reply

@Mark Hennings @Ishan Singh

Kartik Sharma - 3 months, 4 weeks ago

Log in to reply

×

Problem Loading...

Note Loading...

Set Loading...