Estimate the sum of combination Let $$S=\sum _ { i = 0 } ^ { n - 1 } \sum _ { k = 0 } ^ { n - 1 } (k+1) P ( i , k )$$ where $$P ( i , k ) = \frac { \binom { i} { k } } { \binom { n } { k }  } \times \frac { n - i } { n - k }$$
How to estimate $S$ in terms of $n$?
I find that $$S=(n+1)\left(\frac {1} 2 +\frac {1} 3 +\cdots +\frac {1} {n+1}\right)$$
But I have no idea to prove the above equation.
 A: Once you have your final line, you can write $S(n)=H_{n+1}-1$ where $H_n$ is the $n^{th}$ harmonic number.
A: First of all, note that
$$
(k+1)P(i,k) = \frac{\binom{i}k(n-i)}{\binom{n}k\frac{n-k}{k+1}}=\frac{\binom{i}k(n-i)}{\binom{n}{k+1}}
$$
Now, let us reverse the order of summation. 
$$
\sum_{k=0}^{n-1}\frac1{\binom{n}{k+1}}\sum_{i=0}^n \binom{i}k(n-i)
$$
The inner summation is
$$
(n+1)\sum_{i=0}^n \binom{i}k-\sum_{i=0}^n\binom{i}k(i+1)\tag{1}
$$
By the Hockey Stick identity, the first sum is
$$
(n+1)\sum_{i=0}^n \binom{i}k=(n+1)\binom{n+1}{k+1},
$$ 
 while the second is 
$$
\sum_{i=0}^n\binom{i}k(i+1)=\sum_{i=0}^n\binom{i+1}{k+1}(k+1)=(k+1)\cdot \binom{n+2}{k+2}=(n+2)\binom{n+1}{k+1}-\binom{n+2}{k+2}
$$
where we have again eliminated the summation using the Hockey Stick identity. Therefore, $(1)$ simplifies to
$$
(n+1)\binom{n+1}{k+1}-\left((n+2)\binom{n+1}{k+1}-\binom{n+2}{k+2}\right)=\binom{n+2}{k+2}-\binom{n+1}{k+1}=\binom{n+1}{k+2},
$$
so the whole summation is
$$
\sum_{k=0}^{n-1}\frac{\binom{n+1}{k+2}}{\binom{n}{k+1}}=\sum_{k=0}^{n-1}\frac{n+1}{k+2}=(n+1)\left(\frac12+\frac13+\dots+\frac1{n+1}\right)
$$
