Compute a sum with partial fraction decomposition and generating functions

Question

I am trying to compute $$\sum_{k=1}^{n-1} \frac{1}{k(n-k)}$$ using a term by term partial fraction decomposition and also with generating functions, but I'm stuck.

Answer 1

Hint: Generating functions is a good idea. Notice that $a_n:= \displaystyle \sum_{k=1}^{n-1} \frac{1}{k(n-k)}$ is of the form of a Cauchy product. We have $$A(z) := \sum_{n=1}^{\infty} a_n z^n = \left( \sum_{n=1}^{\infty} H_n z^n \right)^2$$ where $H_n = \sum_{k=1}^n 1/k$ is the sequence of Harmonic numbers. Try to go on from here.

---

Sorry, I wrote down something silly after telling you to recognize the Cauchy product, but the method is still ok. I'll give some details:

$$A(z) = \sum_{n=1}^{\infty} \left( \sum_{k=1}^{n-1} \frac{1}{k} \frac{1}{n-k} \right) z^n = \left( \sum_{n=1}^{\infty} \frac{z^n}{n} \right)^2 = \log^2(1-z).$$

So (by ShreevatsaR's computation in the comments) $A'(z) = \dfrac{-2\log(1-z) }{1-z} = \displaystyle \sum_{n=1}^{\infty} 2H_n z^n,$ and integrating gives $a_n = 2H_{n-1}/n .$

---

It is much quicker to use partial fractions as in lab bhattacharjee's comment.