# Binomial Coefficient Challenge 4!

Find a closed form of

$\displaystyle \sum_{k=0}^{n-2} {\binom{k}{m-1} \frac{1}{n-k-1}}$

Note by Kartik Sharma
1 year, 1 month ago

MarkdownAppears as
*italics* or _italics_ italics
**bold** or __bold__ bold
- bulleted- list
• bulleted
• list
1. numbered2. 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 1paragraph 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 \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}$$

Sort by:

For $$n<m$$, the sum is $$0$$. Also, for $$m=1$$, the sum is $$H_{n-1}$$. Henceforth, we'll assume $$n \geq m>1$$.

Denote the sum as $$A_{n}$$. Note that,

$\dfrac{n-1}{k} \sum_{j=1}^{k} \dfrac{1}{(j-n)(j-n+1)} = \dfrac{1}{n-k-1}$

We have,

$A_{n} = \sum_{k=0}^{n-2} {\dbinom{k}{m-1} \dfrac{1}{n-k-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)$

$= \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}$

$= \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)$

$= \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)$

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

Now,

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

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

Also,

$\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,

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

So that,

$A_{n} = \text{X} + \text{Y}$

$\implies A_{n} = \left(\dfrac{n-1}{m-1}\right) [A_{n} - A_{n-1}] - \dfrac{1}{m-1} \dbinom{n-2}{m-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}$

$\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}$

$\implies \dfrac{(N-m)!}{(N-1)!} A_{N} = \dfrac{1}{(m-1)!} \sum_{k=m}^{N} \dfrac{1}{k}$

$\implies A_{N} = \dbinom{N-1}{m-1} (H_{N-1} - H_{m-1})$

$\therefore \sum_{k=0}^{n-1} \dbinom{k}{m} \dfrac{1}{n-k} = \dbinom{n}{m} (H_{n} - H_{m}) \quad \square$

- 1 year, 1 month ago

@Kartik Sharma What was your approach?

- 1 year, 1 month ago

Same as yours. Just a little different formatting.

- 1 year, 1 month ago

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

Reformulating it, we get the elegant identity :

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

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

Will post full solution soon.

- 1 year, 1 month ago

Correct! It's very elegant indeed.

- 1 year, 1 month ago

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

- 1 year, 1 month ago

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

- 1 year, 1 month ago

Thanks for the reference

- 1 year, 1 month 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

- 1 year, 1 month ago