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.
$\begingroup$
$\endgroup$
2
-
2$\begingroup$ Ok.. so what have you tried? $\endgroup$– TomCommented Nov 25, 2013 at 16:28
-
$\begingroup$ As $$\frac1{k(n-k)}=\frac1n\left(\frac{n-k+k}{k(n-k)}\right)=\frac1n\left(\frac1k+\frac1{n-k}\right)$$. bUt then what? $\endgroup$– lab bhattacharjeeCommented Nov 25, 2013 at 16:33
Add a comment
|
3 Answers
$\begingroup$
$\endgroup$
2
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.
answered Nov 25, 2013 at 16:43
-
$\begingroup$ Just for completeness: $\sum_{n=1}^{\infty} H_n z^n = \sum_{n=1}^{\infty} (\sum_{k=1}^n \frac1k) z^n = \sum_{k=1}^{\infty} \frac1k \sum_{n=k}^{\infty} z^n = \sum_{k=1}^{\infty} \frac1k \frac{z^k}{1-z} = \frac{1}{1-z} \sum_{k=1}^{\infty} \frac{z^k}{k} = \frac{1}{1-z}\ln\frac{1}{1-z}$, if I've not made any mistake. So its square is $\frac{1}{(1-z)^2}\left(\ln\frac{1}{1-z}\right)^2$, but it's not clear how to get $a_n$ from that (except by solving the original problem). $\endgroup$ Commented Apr 5, 2014 at 3:55
-
$\begingroup$ @ShreevatsaR See my edited answer, and thanks for bringing it up. $\endgroup$ Commented Apr 5, 2014 at 9:02
$\begingroup$
$\endgroup$
$\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}} $$
answered Apr 5, 2014 at 9:27
$\begingroup$
$\endgroup$
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}$