Summation proof

[Albert Chan]

(09-11-2023 03:48 PM)Albert Chan Wrote:  \(\displaystyle \binom{x+n}{k}' \bigg\rvert_{x=0}
\;=\; \sum_{j=1}^{k} \frac{(-1)^{j+1}}{j}\; \binom{n}{k-j}
\;=\; \binom{n}{k}\;\sum_{j=n-(k-1)}^{n} \frac{1}{j}
\)

Proving the middle part is tricky, we had to drop j denominator first.
Without denominator j, it is a telescoping sum, only first term remain. (last term = 0)

\(\displaystyle \sum_{j=1}^{k} (-1)^{j+1}\; \binom{n}{k-j}
= \sum_{j=1}^{k} (-1)^{j+1}\; \left( \binom{n-1}{k-j} + \binom{n-1}{k-j-1}\right)
= \binom{n-1}{k-1}\)

To add back j denominator, we use the same trick for getting Bernoulli's number!
Summation, then take the derivative:

\(\displaystyle \sum_{x=1}^{n} \binom{x-1}{k-1} = \binom{n}{k}\)

\(\displaystyle \frac{d}{dn} \binom{n}{k} = \sum_{j=1}^{k} \frac{(-1)^{j+1}}{j}\; \binom{n}{k-j} \)

Divide LHS by \(\binom{n}{k}\), we have:

\(\displaystyle \frac{d}{dn} \ln \binom{n}{k}
= \frac{d}{dn} \left( \ln(n!) - \ln((n-k)!) - \ln(k!) \right)
= \Psi(n+1) - \Psi(n-k+1)
= \sum_{j=n-(k-1)}^{n} \frac{1}{j} \)      QED