Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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|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
1  
I am trying to understand this paper on partial quick sort. lsi.upc.edu/~conrado/research/reports/ALCOMFT-TR-03-50.pdf . Page no 3 (F(z,u)*=) –  ami Jul 22 '12 at 16:41

2 Answers 2

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|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

$$\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$.)

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

Your Answer

 
discard

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.