Combinatoral proof of an well known identity.

Standard

Proof of $\sum_{k=0}^{m} \frac{m!(n-k)!}{n!(m-k)!} = \frac{n+1}{n-m+1}$

Lets consider a bag has $n+1$ balls out of which $m$ are white and $n-m+1$ are black.

Let $X$ be a Random variable counting the no. of balls to be taken out of the box in order to end up with a black ball.

Clarly X takes value in the set $1,2,....,m+1$ .

$P(X=1)=\frac{n-m+1}{n+1}$

$P(X=2)=\frac{m}{n+1}\times \frac{n-m+1}{n}$

$P(X=3)=\frac{m}{n+1} \times \frac{m-1}{n}\times \frac{n-m+1}{n-1}$

In this way $P(X=k)=\frac{m}{n+1}\times \frac{m-1}{n}.... \times \frac{m-k+2}{n-k+3}\times \frac{n-m+1}{n-k+2}=\frac{n-m+1}{n+1}\times \frac{m!(n-(k-1))!}{n!(m-(k-1))!}$

As all the probabilities must add upto $1$

We have $\displaystyle\sum_{k=1}^{m+1}P(X=k)=1$

$\Rightarrow\displaystyle\sum_{k=1}^{m+1}\frac{n-m+1}{n+1}\times \frac{m!(n-(k-1))!}{n!(m-(k-1))!}=1$

$\Rightarrow\displaystyle\sum_{l=0}^{m}\frac{n-m+1}{n+1}\times \frac{m!(n-l)!}{n!(m-l)!}=1$

$\Rightarrow\displaystyle\sum_{l=0}^{m}\frac{m!(n-l)!}{n!(m-l)!}=\frac{n+1}{n-m+1}$

We are done.

Inequality.

Standard

Proof of : $\displaystyle 2\sqrt{n+1}-2<\sum_{k=1}^{n}{\frac{1}{\sqrt{k}}}<2\sqrt{n}-1.$

Let $\displaystyle f(x)=\sqrt{x}$

$\displaystyle f'(x)=\frac{1}{2}\frac{1}{\sqrt{x}}$

Using mean value theorem we have:

$\displaystyle \frac{f(n+1)-f(n)}{(n+1)-n}=f'(c)$ for  some $c\in(n,n+1)$

$\displaystyle \Rightarrow \frac{\sqrt{n+1}-\sqrt{n}}{1}=\frac{1}{2}\frac{1}{\sqrt{c}}$….(1)

$\displaystyle \frac{1}{\sqrt{n+1}}<\frac{1}{\sqrt{c}}<\frac{1}{\sqrt{n}}$

Using the above ineq. in $(1)$ we have,

$\displaystyle \frac{1}{2\sqrt{n+1}}<\sqrt{n+1}-\sqrt{n}<\frac{1}{2\sqrt{n}}$

Adding the left part of the inequality we have,$\displaystyle\sum_{k=2}^{n}\frac{1}{2\sqrt{k}}<\sum_{k=2}^{n}(\sqrt{k}-\sqrt{k-1})=\sqrt{n}-1$

$\Rightarrow \displaystyle\sum_{k=2}^{n}\frac{1}{\sqrt{k}}<2\sum_{k=2}^{n}(\sqrt{k}-\sqrt{k-1})=2(\sqrt{n}-1)$

$\Rightarrow \displaystyle1+\sum_{k=2}^{n}\frac{1}{\sqrt{k}}<1+2\sum_{k=2}^{n}(\sqrt{k}-\sqrt{k-1})=2\sqrt{n}-2+1=2\sqrt{n}-1$

$\Rightarrow \displaystyle\sum_{k=1}^{n}\frac{1}{\sqrt{k}}<2\sqrt{n}-1$

Similarly adding the right side of the inequality we have,

$\displaystyle\sum_{k=1}^{n}\frac{1}{2\sqrt{k}}>\sum_{k=1}^{n}(\sqrt{k+1}-\sqrt{k})=\sqrt{n+1}-1$

$\Rightarrow \displaystyle\sum_{k=1}^{n}\frac{1}{\sqrt{k}}>2(\sqrt{n+1}-1)$

This completes the proof.