Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

how can I find the coefficient of $x^ny^m$ of following series $$\frac{\log\big(\frac{1}{1-xy}\big)}{(1-x)(1-y)(1-xy)}$$ and $$ \frac{\log(\frac{1}{1-x})}{(1-x)(1-y)(1-xy)}$$ where $1 \leq m \leq n$

share|cite|improve this question
You can write this functions as a Cauchy product of four series. Why do you want $m\leq n$? – Davide Giraudo Jul 22 '12 at 16:37
I am trying to understand this paper on partial quick sort. . Page no 3 (F(z,u)*=) – ami Jul 22 '12 at 16:41

Use $\log\left(\frac{1}{1-x y}\right) = -\log(1- xy) = - \sum_{n=1}^\infty \frac{1}{n} x^n y^n$, and $$ -\frac{\log(1-x y)}{1-x y} = \sum_{n=1}^\infty x^n y^n \sum_{m=1}^n \frac{1}{n} = \sum_{n=1}^\infty x^n y^n H_n $$ Then use $$ \frac{ \sum_{n \geqslant 1, m\geqslant 1} c_{n,m} x^n y^m}{(1-x)(1-y)} = \sum_{n=1}^\infty \sum_{m=1}^\infty x^n y^m \sum_{k=1}^n \sum_{\ell=1}^m c_{k,\ell} $$ In our case $c_{k,\ell} = H_k \delta_{k,\ell}$, and $\sum_{k=1}^n \sum_{\ell=1}^m H_k \delta_{k,\ell} = \sum_{k=1}^{\min(n,m)} H_k$ $$ -\frac{\log(1-x y)}{1-x y} \cdot \frac{1}{(1-x)(1-y)} = \sum_{n=1}^\infty \sum_{m=1}^\infty x^n y^m \sum_{k=1}^{\min(n,m)} H_k = \sum_{n=1}^\infty \sum_{m=1}^\infty x^n y^m \left( \left(\min(n,m) +1\right)\left( H_{\min(n,m)+1}-1\right) \right) $$

For the second series, we start with $$ [x]^n \frac{-\log(1-x)}{1-x} = H_n \quad [x]^m \frac{1}{1-x y} = y^m $$ Therefore $$ [x]^n \frac{-\log(1-x)}{1-x} \cdot \frac{1}{1-x y} = \sum_{k=0}^{n-1} H_{n-k} y^k $$ Then $$ [y]^m [x]^n \frac{-\log(1-x)}{1-x} \cdot \frac{1}{1-x y} \cdot \frac{1}{1-y} = \sum_{k=0}^{n-1}H_{n-k} \mathbf{1}\left( k \leqslant m \right) = \sum_{k=0}^{\min(m, n-1)}H_{n-k} $$

share|cite|improve this answer
Thanks. please solve series no. 2. – ami Jul 22 '12 at 16:54
Thanks @Sasha. your solution is more generic. – ami Jul 22 '12 at 17:37
I think you're off by $1$ in the first series. You seem to be saying (in the last line) $\sum_{k=1}^K H_k = (K+1) (H_K-1)$ but it should be $\sum_{k=1}^K H_k = (K+1) (H_K-1) + 1$. So the answer should be $$\sum_{n=1}^\infty\sum_{m=1}^\infty x^n y^m \left((\min(n,m)+1)(H_{\min(n,m)}-1)+1\right)$$ – Robert Israel Jul 22 '12 at 18:25
@RobertIsrael Thanks, I mean to say $\sum_{k=1}^n H_k = (n+1)(H_{n+1}-1)$. – Sasha Jul 22 '12 at 19:29

Using geometric series and $\displaystyle\frac{1}{1-r}\log\frac{1}{1-r}=\sum_{k\ge1}H_kr^k$, with $H_k$ the $k$th harmonic number,

$$\sum_{a=0}^\infty x^a~\sum_{b=0}^\infty y^b~\sum_{k=1}^\infty H_k(xy)^k=\sum_{a,b\ge0}^{k\ge1}H_kx^{a+k}y^{b+k}.$$

The coefficient of $x^ny^m$ will be the sum of all $H_k$ with $k\le n,m$. With $m\le n$, this is


by induction. Similarly for the second,

$$\sum_{a=0}^\infty y^a\sum_{b=0}^\infty (xy)^b \sum_{k=1}^\infty H_kx^k=\sum_{a,b\ge0}^{k\ge1} H_k x^{b+k}y^{a+b}.$$

The coefficient of $x^ny^m$ will be the sum of all $k\le n$ such that $0\le n-k\le m$, i.e.

$$\sum_{k=n-m}^{n}H_k=\left(\sum_{k=1}^n H_k\right)-\left(\sum_{k=1}^{n-m-1}H_k\right)$$


(Or $0$ if $m>n$.)

share|cite|improve this answer
Thanks @anon. I learned something today. :) – ami Jul 22 '12 at 17:35

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.