Summation proof

[Albert Chan]

Hi, rprosperi

The math is an optimization trick used in code. (recursion to iterative sum)
Based on experiments, I was 99% sure it is correct. Prove get the final 1%.

I don't know how to explain beauty of math, but consider the proof, for k=3

\(\displaystyle
\binom{n}{3} \left(
\frac{1}{n} + \frac{1}{n-1} + \frac{1}{n-2}
\right) =
\frac{1}{1}\binom{n}{2} -
\frac{1}{2}\binom{n}{1} +
\frac{1}{3}\binom{n}{0}\)

Why is this even true?
Where is the harmonic series comes from?

Well, harmonic series comes from Psi, derivative of log gamma function.

Eureka! RHS must be \(\displaystyle \frac{d}{dn} \binom{n}{3}\) in disguise.