Binomial Coefficient Challenge 4!

Find a closed form of

∑k=0n−2(km−1)1n−k−1\displaystyle \sum_{k=0}^{n-2} {\binom{k}{m-1} \frac{1}{n-k-1}}

Note by Kartik Sharma
4 years 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

Very elegant problem. I'm getting the closed form as (n−1m−1)(Hn−1−Hm−1) \dbinom{n-1}{m-1} (H_{n-1} - H_{m-1})

Reformulating it, we get the elegant identity :

∑k=0n−1(km)1n−k=(nm)(Hn−Hm) \sum_{k=0}^{n-1} \dbinom{k}{m} \dfrac{1}{n-k} = \dbinom{n}{m} (H_{n} - H_{m})

For m,n∈Z+m,n \in \mathbb{Z^{+}}

Will post full solution soon.

Ishan Singh - 4 years ago

Log in to reply

Correct! It's very elegant indeed.

Kartik Sharma - 4 years ago

Log in to reply

Can u tell me any name of book or any resource on internet to learn about more binomial co-efficient ??/

Kushal Bose - 4 years ago

Log in to reply

@Kushal Bose – Sure. I have mostly learnt from Concrete Mathematics. Apart from that, binomial coefficients are a good application of algebra, calculus, recurrence etc.

Kartik Sharma - 4 years ago

Log in to reply

@Kartik Sharma – Thanks for the reference

Kushal Bose - 4 years ago

For n<mn<m, the sum is 00. Also, for m=1m=1, the sum is Hn−1H_{n-1}. Henceforth, we'll assume n≥m>1n \geq m>1.

Denote the sum as AnA_{n}. Note that,

n−1k∑j=1k1(j−n)(j−n+1)=1n−k−1 \dfrac{n-1}{k} \sum_{j=1}^{k} \dfrac{1}{(j-n)(j-n+1)} = \dfrac{1}{n-k-1}

We have,

An=∑k=0n−2(km−1)1n−k−1 A_{n} = \sum_{k=0}^{n-2} {\dbinom{k}{m-1} \dfrac{1}{n-k-1}}

=(n−1)∑k=1n−2∑j=1k1k(km−1)(1(j−n)(j−n+1)) = (n-1) \sum_{k=1}^{n-2} \sum_{j=1}^{k} \dfrac{1}{k} \dbinom{k}{m-1} \left( \dfrac{1}{(j-n)(j-n+1)} \right)

=(n−1m−1)∑j=1n−2∑k=jn−21(j−n)(j−n+1)(k−1m−2) = \left(\dfrac{n-1}{m-1}\right) \sum_{j=1}^{n-2} \sum_{k=j}^{n-2} \dfrac{1}{(j-n)(j-n+1)} \dbinom{k-1}{m-2}

=(n−1m−1)∑j=1n−2(1(j−n)(j−n+1)∑k=jn−2(k−1m−2)) = \left(\dfrac{n-1}{m-1}\right) \sum_{j=1}^{n-2} \left( \dfrac{1}{(j-n)(j-n+1)} \sum_{k=j}^{n-2} \dbinom{k-1}{m-2} \right)

=(n−1m−1)∑j=1n−21(j−n)(j−n+1)((n−2m−1)−(j−1m−1)) = \left(\dfrac{n-1}{m-1}\right) \sum_{j = 1}^{n-2} \dfrac{1}{(j-n)(j-n+1)} \left( \dbinom{n-2}{m-1} - \dbinom{j-1}{m-1} \right)

=X+Y = \text{X} + \text{Y}

Now,

X=(n−1m−1)(n−2m−1)∑j=1n−21(j−n)(j−n+1) \text{X} = \left(\dfrac{n-1}{m-1}\right) \dbinom{n-2}{m-1} \sum_{j=1}^{n-2} \dfrac{1}{(j-n)(j-n+1)}

=(n−2m−1)(n−2m−1) = \left( \dfrac{n-2}{m-1} \right) \dbinom{n-2}{m-1}

Also,

Y=(n−1m−1)[∑j=1n−21n−j(j−1m−1)−∑j=1n−21n−j−1(j−1m−1)] \text{Y} = \left(\dfrac{n-1}{m-1}\right) \left[ \sum_{j=1}^{n-2} \dfrac{1}{n-j} \dbinom{j-1}{m-1} - \sum_{j=1}^{n-2} \dfrac{1}{n-j-1} \dbinom{j-1}{m-1} \right]

Re-indexing, we have,

Y=(n−1m−1)(An−An−1−(n−2m−1)) \text{Y} = \left(\dfrac{n-1}{m-1}\right) \left(A_{n} - A_{n-1} - \dbinom{n-2}{m-1} \right)

So that,

An=X+YA_{n} = \text{X} + \text{Y}

  ⟹  An=(n−1m−1)[An−An−1]−1m−1(n−2m−1) \implies A_{n} = \left(\dfrac{n-1}{m-1}\right) [A_{n} - A_{n-1}] - \dfrac{1}{m-1} \dbinom{n-2}{m-1}

  ⟹  (n−m)!(n−1)!An−(n−m−1)!(n−2)!An−1=(n−m−1)!(n−1)!(n−2m−1) \implies \dfrac{(n-m)!}{(n-1)!} A_{n} - \dfrac{(n-m-1)!}{(n-2)!} A_{n-1} = \dfrac{(n-m-1)!}{(n-1)!} \dbinom{n-2}{m-1}

  ⟹  ∑n=mN((n−m)!(n−1)!An−(n−m−1)!(n−2)!An−1)=∑n=mN(n−m−1)!(n−1)!(n−2m−1) \implies \sum_{n=m}^{N} \left(\dfrac{(n-m)!}{(n-1)!} A_{n} - \dfrac{(n-m-1)!}{(n-2)!} A_{n-1} \right) = \sum_{n=m}^{N} \dfrac{(n-m-1)!}{(n-1)!} \dbinom{n-2}{m-1}

  ⟹  (N−m)!(N−1)!AN=1(m−1)!∑k=mN1k \implies \dfrac{(N-m)!}{(N-1)!} A_{N} = \dfrac{1}{(m-1)!} \sum_{k=m}^{N} \dfrac{1}{k}

  ⟹  AN=(N−1m−1)(HN−1−Hm−1) \implies A_{N} = \dbinom{N-1}{m-1} (H_{N-1} - H_{m-1})

∴∑k=0n−1(km)1n−k=(nm)(Hn−Hm)□ \therefore \sum_{k=0}^{n-1} \dbinom{k}{m} \dfrac{1}{n-k} = \dbinom{n}{m} (H_{n} - H_{m}) \quad \square

Ishan Singh - 3 years, 12 months ago

Log in to reply

@Kartik Sharma What was your approach?

Ishan Singh - 3 years, 12 months ago

Log in to reply

Same as yours. Just a little different formatting.

Kartik Sharma - 3 years, 12 months ago

I have a doubt .In the expression when k=1 then m can be 1,2.If m >=3 then k can not be 0,1

Kushal Bose - 3 years, 12 months ago
×

Problem Loading...

Note Loading...

Set Loading...