Using a probability argument I got the sum. Can it be done directly?

[mathman]

TL;DR

Using a probability argument I got the sum. Can it be done directly?

$\sum\limits_{k=0}^{n-m} \frac{\binom{n-m}{k}}{\binom{n}{k}}\frac{m}{n-k}=1$. Can be derived from question. For $n\ge m$, pick $m$ marbled out of a set size $n$ labeled from $1$ to $n$, what is probability distribution of minimum of the number labels on the marbles? The terms is the summation are probabilities that minimum label $=k+1$.

 

[fresh_42]

May we assume $2m\geq n$?

 

[mathman]

May we assume $2m\geq n$?

Error in original post - has been corrected. m can be anything up to n.

 

[fresh_42]

We can set $N:=n-m$ and rephrase the statement as
$$
\sum_{k=0}^N\prod_{j=1}^k\dfrac{N-j+1}{n-j}=\dfrac{n}{n-N}
$$
and attempt an induction on $N$. It is true for $N=0,1,2.$
I think that such an induction is the best way to prove it.

 

[mathman]

The sum should = 1, why n/m? Also the denominator in the product should be n-j+1.

 

[fresh_42]

The sum should = 1, why n/m? Also the denominator in the product should be n-j+1.

No, I distributed $\dfrac{m}{n}$ out of the sum and put it on the other side. My formula is correct (I think). I only skipped a few elementary calculation steps.

Edit: By checking the calculation for $N=2$ I saw that multiplying with the common denominator is probably better than an induction. The induction brought a weighted sum such that the induction hypothesis couldn't be applied.

 

[mathman]

At the opposite end, m=n or m=n-1 can be checked directly. Math induction probably won't work. There might be a tricky way to do the sum, but I have no ideas.

 

[fresh_42]

There is still a little work to do, but I broke it down to an inductionable statement:
$$
\sum_{k=0}^N\prod_{j=1}^k\dfrac{N-j+1}{n-j}=\dfrac{n}{n-N}
$$
\begin{align*}
\dfrac{n}{n-N}&= 1+\dfrac{N}{n-1}+\dfrac{N(N-1)}{(n-1)(n-2)}+\ldots+\dfrac{N}{n-1}\cdots \dfrac{1}{n-N}\\
\dfrac{n!}{n-N}&=(n-1)!+N(n-2)!+N(N-1)(n-3)!+\ldots +N!\\
n!&=(n-1)!(n-N)+N(n-N)(n-2)!+\ldots +N!(n-N)
\end{align*}
Now it is in a form where we can perform an induction.
\begin{align*}
N=0\, &: \,(n-1)!(n-0)=n!\\
N=1\, &: \,(n-1)!(n-1)+(n-1)(n-2)!=(n-1)!(n-1+1)=n!\\
N=2\, &: \,(n-1)!(n-2)+2(n-2)(n-2)!+2(n-2)(n-3)!\\
\phantom{N=2\, }&\phantom{\,=}=(n-2)!((n-1)(n-2)+2(n-2)+2)\\
\phantom{N=2\, }&\phantom{\,=}=(n-2)!(n^2-3n+2+2n-4+2)=(n-2)!(n^2-n)=n!
\end{align*}

 

[mathman]

I see it as a direct calculation. I don't see the induction?

 

[fresh_42]

I see it as a direct calculation. I don't see the induction?

I haven't checked. Maybe it can be done directly.

 

[mathman]

As far as I can tell, for each N (or m) it could be done directly. This is tedious.