Waste less time on Facebook — follow Brilliant.
×

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

No vote yet
1 vote

Comments

Sort by:

Top Newest

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 \] Ishan Singh · 2 months ago

Log in to reply

@Ishan Singh @Kartik Sharma What was your approach? Ishan Singh · 2 months ago

Log in to reply

@Ishan Singh Same as yours. Just a little different formatting. Kartik Sharma · 2 months ago

Log in to reply

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. Ishan Singh · 2 months, 1 week ago

Log in to reply

@Ishan Singh Correct! It's very elegant indeed. Kartik Sharma · 2 months, 1 week ago

Log in to reply

@Kartik Sharma Can u tell me any name of book or any resource on internet to learn about more binomial co-efficient ??/ Kushal Bose · 2 months, 1 week 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 · 2 months, 1 week ago

Log in to reply

@Kartik Sharma Thanks for the reference Kushal Bose · 2 months, 1 week ago

Log in to reply

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 · 2 months ago

Log in to reply

×

Problem Loading...

Note Loading...

Set Loading...