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$
Find coefficient of $x^ny^m$
-
0You can write this functions as a Cauchy product of four series. Why do you want $m\leq n$? – 2012-07-22
-
1I am trying to understand this paper on partial quick sort. http://www.lsi.upc.edu/~conrado/research/reports/ALCOMFT-TR-03-50.pdf . Page no 3 (F(z,u)*=) – 2012-07-22
2 Answers
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} $$
-
0Thanks. please solve series no. 2. – 2012-07-22
-
0Thanks @Sasha. your solution is more generic. – 2012-07-22
-
0I 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)$$ – 2012-07-22
-
0@RobertIsrael Thanks, I mean to say $\sum_{k=1}^n H_k = (n+1)(H_{n+1}-1)$. – 2012-07-22
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
$$\sum_{k=1}^mH_k=(m+1)(H_{m+1}-1)$$
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)$$
$$=(n+1)\big(H_{n+1}-1\big)-(n-m)\big(H_{n-m}-1\big).$$
(Or $0$ if $m>n$.)
-
0Thanks @anon. I learned something today. :) – 2012-07-22