Binomial Coefficient Challenge 12!

Prove that

k=0m1(1)k(nk)Hk=n+1n+2((1)m+1(n+1m)(Hm1n+2)1n+2)\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 HmH_m is the mmth Harmonic number.

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

Note by Kartik Sharma
2 years, 2 months ago

No vote yet
1 vote

</code>...<code></code> ... <code>.">   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 </span>...<span></span> ... <span> or </span>...<span></span> ... <span> to ensure proper formatting.
2 \times 3 2×3 2 \times 3
2^{34} 234 2^{34}
a_{i-1} ai1 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

Sort by:

Top Newest

We have,

S=k=0m1(1)k(nk)Hk=k=1m1(1)k(nk)Hk \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

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

=r=1m11r[k=0m1((1)k(nk))k=0r1((1)k(nk))] = \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]

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

From Binomial Coefficient Challenge 6,

F(m)=k=0m1((1)k(nk))=(n+1n+2)(1+(1)m+1(n+1m))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)

    S=(n+1n+2)r=1m11r[(1)m+1(n+1m)(1)r+1(n+1r)] \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]

=(n+1n+2)[(1)m+1(n+1m)Hm1r=1m1(1)r+1r(n+1r)] = \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]

=(n+1n+2)[(1)m+1(n+1m)Hm11n+1r=0m2(1)r(nr)] = \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]

=(n+1n+2)[(1)m+1(n+1m)Hm11n+2(1+(1)m(n+1m1))] = \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,

k=0m1(1)k(nk)Hk=(n+1n+2)((1)m+1(n+1m)(Hm1n+2)1n+2) \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 - 2 years, 2 months 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 -

(1)k(nk)δk=n+1n+2(1)k+1(n+1k)\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,

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

Let

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

Now, we use Summation By Parts -

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

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

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

Then,

S=n+1n+2(1)k+1(n+1k)Hkn+1n+2(1)k+2(n+1k+1)δkk+1\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}}

=n+1n+2(1)k+1(n+1k)Hk1n+2(1)k(nk)δk\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}

=n+1n+2(1)k+1(n+1k)Hkn+1(n+2)2(1)k+1(n+1k)\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 00 and mm (yes, not m1m-1)

=n+1n+2((1)m+1(n+1m)(Hm1n+2)1n+2)\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 - 2 years, 1 month ago

Log in to reply

@Mark Hennings @Ishan Singh

Kartik Sharma - 2 years, 2 months ago

Log in to reply

Check the limits on the LHS - there is no H0H_0.

Is there any relationship between mm and nn, 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 - 2 years, 2 months ago

Log in to reply

Exactly. There was this problem with H0H_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 mm and nn.

Kartik Sharma - 2 years, 2 months ago

Log in to reply

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

Hn=01xn1x1 dx H_{n} = \int_{0}^{1} \dfrac{x^n - 1}{x-1} \ \mathrm{d}x

and put n=0n=0.

Btw, what was your approach?

Ishan Singh - 2 years, 2 months ago

Log in to reply

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

Kartik Sharma - 2 years, 2 months ago

Log in to reply

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

Ishan Singh - 2 years, 2 months 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,

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

Hz=k=1(1k1k+z)=n=2(1)nζ(n)zn1\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 - 2 years, 1 month ago

Log in to reply

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

Ishan Singh - 2 years, 2 months ago

Log in to reply

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

Kartik Sharma - 2 years, 2 months ago

Log in to reply

×

Problem Loading...

Note Loading...

Set Loading...