Compute a sum with partial fraction decomposition and generating functions 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. 
 A: 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.
A: $\newcommand{\+}{^{\dagger}}
 \newcommand{\angles}[1]{\left\langle\, #1 \,\right\rangle}
 \newcommand{\braces}[1]{\left\lbrace\, #1 \,\right\rbrace}
 \newcommand{\bracks}[1]{\left\lbrack\, #1 \,\right\rbrack}
 \newcommand{\ceil}[1]{\,\left\lceil\, #1 \,\right\rceil\,}
 \newcommand{\dd}{{\rm d}}
 \newcommand{\down}{\downarrow}
 \newcommand{\ds}[1]{\displaystyle{#1}}
 \newcommand{\expo}[1]{\,{\rm e}^{#1}\,}
 \newcommand{\fermi}{\,{\rm f}}
 \newcommand{\floor}[1]{\,\left\lfloor #1 \right\rfloor\,}
 \newcommand{\half}{{1 \over 2}}
 \newcommand{\ic}{{\rm i}}
 \newcommand{\iff}{\Longleftrightarrow}
 \newcommand{\imp}{\Longrightarrow}
 \newcommand{\isdiv}{\,\left.\right\vert\,}
 \newcommand{\ket}[1]{\left\vert #1\right\rangle}
 \newcommand{\ol}[1]{\overline{#1}}
 \newcommand{\pars}[1]{\left(\, #1 \,\right)}
 \newcommand{\partiald}[3][]{\frac{\partial^{#1} #2}{\partial #3^{#1}}}
 \newcommand{\pp}{{\cal P}}
 \newcommand{\root}[2][]{\,\sqrt[#1]{\vphantom{\large A}\,#2\,}\,}
 \newcommand{\sech}{\,{\rm sech}}
 \newcommand{\sgn}{\,{\rm sgn}}
 \newcommand{\totald}[3][]{\frac{{\rm d}^{#1} #2}{{\rm d} #3^{#1}}}
 \newcommand{\ul}[1]{\underline{#1}}
 \newcommand{\verts}[1]{\left\vert\, #1 \,\right\vert}
 \newcommand{\wt}[1]{\widetilde{#1}}$
\begin{align}
\sum_{k = 1}^{n - 1}{1 \over k\pars{n - k}}&=
\sum_{k = 1}^{n - 1}{1 \over n}\,\pars{{1 \over k} + {1 \over n - k}}
={1 \over n}\sum_{k = 1}^{n - 1}{1 \over k}
+ {1 \over n}\sum_{k = 1 - n}^{-1}{1 \over -k}
={1 \over n}\sum_{k = 1}^{n - 1}{1 \over k}
+ {1 \over n}\sum_{k = 1}^{n - 1}{1 \over k}
\\[3mm]&={2 \over n}\sum_{k = 1}^{n - 1}{1 \over k}
={2 \over n}\sum_{k = 0}^{\pars{\color{#c00000}{n - 1}} - 1}
{1 \over k + \color{#00f}{1}} =
{2 \over n}\braces{%
\Psi\pars{1 + \bracks{\color{#c00000}{n - 1}}} - \Psi\pars{\color{#00f}{1}}}
\end{align}
where $\ds{\Psi\pars{z}}$ is the
Digamma Function. Also,
$\ds{\Psi\pars{1} = -\gamma}$. $\ds{\gamma \approx 0.5772}$ is the
Euler-Mascheroni Constant.

$$\color{#00f}{\large%
\sum_{k = 1}^{n - 1}{1 \over k\pars{n - k}}
={2 \over n}\,\bracks{\Psi\pars{n} + \gamma}}
$$ 

A: Note that:
$$
\frac{1}{k (n - k)} = \frac{1}{k n} + \frac{1}{n (n - k)}
$$
Thus your sum is:
$\begin{align}
\sum_{1 \le k \le n - 1} \frac{1}{k (n - k)}
  &= \sum_{1 \le k \le n - 1} \frac{1}{k n}
       + \sum_{1 \le k \le n - 1} \frac{1}{n (n - k)} \\
  &= \frac{1}{n} \sum_{1 \le k \le n - 1} \frac{1}{k}
       + \frac{1}{n} \sum_{1 \le k \le n - 1} \frac{1}{n - k} \\
  &= \frac{2}{n} \sum_{1 \le k \le n - 1} \frac{1}{k} \\
  &= \frac{2}{n} H_{n - 1}
\end{align}$
