# Interchanging summands and double summation [closed]

could someone please explain how the equal sign is satisfied? Like how did they go from LHS to RHS, read this on a research paper which didn't really provide clarification.

Thanks!

enter image description here

## closed as unclear what you're asking by JMoravitz, JonMark Perry, Juniven, Shailesh, Claude LeiboviciMar 30 '17 at 7:44

Please clarify your specific problem or add additional details to highlight exactly what you need. As it's currently written, it’s hard to tell exactly what you're asking. See the How to Ask page for help clarifying this question. If this question can be reworded to fit the rules in the help center, please edit the question.

• What is $\sigma_l(k)$ in this context? What was this paper on? Can we have some sort of context please... – JMoravitz Mar 30 '17 at 1:01
• @JMoravitz Hello, I am sorry haha. Please click into added image under "EDITED:" That's what we are trying to prove. The paper is about sum of lth power of divisors of n for any natural number n. – J. Doe Mar 30 '17 at 1:06
• The "added image" is exactly the same as the original image, just slightly off-center... Perhaps you should just link to the paper itself – JMoravitz Mar 30 '17 at 1:07
• @JMoravitz cds.cern.ch/record/818185/files/0501027.pdf (pg23) – J. Doe Mar 30 '17 at 1:10
• They provide clarification on the very next line at (A14)... did you bother to read that? Which step from the next line do you not follow? – JMoravitz Mar 30 '17 at 1:16

Here in this context, $\sigma_l(k)$ denotes the sum of the $l$-th powers of the positive divisors of $k$. That is to say $\sigma_l(k):=\sum\limits_{d\mid k} d^l$

Note also before continuing that the formal power series $1+x+x^2+\dots$ can be rewritten as $\sum\limits_{k=0}^\infty x^k = \frac{1}{1-x}$ (or instead of thinking as a formal power series just an ordinary series with $|x|<1$) As such, we have $x+x^2+x^3+\dots = \frac{x}{1-x}$. This is the standard geometric series formula. In particular, letting $q^n$ play the role of $x$ we have $\frac{q^n}{1-q^n}=q^n+q^{2n}+q^{3n}+\dots = \sum\limits_{k=1}^\infty q^{nk}$

So, we have:

$$\sum\limits_{n=1}^\infty\frac{n^lq^n}{1-q^n}=\sum\limits_{n=1}^\infty n^l\cdot\left(\frac{q^n}{1-q^n}\right) = \sum\limits_{n=1}^\infty \left[n^l\left(\sum\limits_{k=1}^\infty q^{nk}\right)\right]$$

Now... from here, let us look more closely at the coefficient of $q^x$ in the expansion of the above. The terms which contribute to the coefficient of $q^x$ will be of the form $n^lq^{nk}$ where $nk=x$. In particular, for each specific choice of $n$ where $n$ is a positive divisor of $x$ there will be exactly one term which contributes to the overall coefficient and it does so by an amount of $n^l$.

Since each time a contribution is made to the coefficient of $q^x$ it is done so by a positive divisor of $x$, we may choose to simply sum over the divisors instead. We have then:

$$\sum\limits_{n=1}^\infty\left[n^l\left(\sum\limits_{k=1}^\infty q^{nk}\right)\right] = \sum\limits_{x=1}^\infty \left(\sum\limits_{d\mid x} d^l\right)q^x$$

The author of this paper seems to prefer using $n$'s and $k$'s and so renames what I called $x$ to $k$ to have this as his index instead.

$$\dots=\sum\limits_{k=1}^\infty \left(\sum\limits_{d\mid k} d^l\right)q^k=\sum\limits_{k=1}^\infty \sigma_l(k)q^k$$

where this final equality follows from the definition of $\sigma_l(k)$

• Looks like we posted our answers at the same time. – Matthew Leingang Mar 30 '17 at 1:40
• @JMoravitz, my only question is that I feel like the d comes out of nowhere. You said we may choose to simply sum over the divisors, okay but the first thing comes to mine would be n. Where did that d come from? :) – J. Doe Mar 30 '17 at 2:03

First, remember the geometric series formula $$\frac{1}{1-q^n} = \sum_{d=0}^\infty (q^n)^j = \sum_{d=0}^\infty q^{nd}$$ So $$\frac{q^n}{1-q^n} = \frac{1}{1-q^n} - 1 = \sum_{d=0}^\infty q^{nd} -1 = \sum_{d=1}^\infty q^{nd}$$ Therefore $$\sum_{n=1}^\infty \frac{n^l q^n}{1-q^n} =\sum_{n=1}^\infty n^l \sum_{d=1}^\infty q^{dn} =\sum_{n=1}^\infty \sum_{d=1}^\infty n^l q^{dn}$$ As $n$ and $d$ both range from $1$ to $\infty$, their products $nd$ will hit all of the positive integers at least once. All prime numbers get hit exactly twice, while all composite numbers get hit once for each factor. So instead of summing $n$ from $1$ to $\infty$, and $d$ from $1$ to $\infty$, sum the product $k$ from $1$ to $\infty$, then for each $k$ sum over all pairs $(d,n)$ such that $dn=k$. $$\sum_{n=1}^\infty \sum_{d=1}^\infty n^l q^{dn} =\sum_{k=1}^\infty \sum_{\substack{(n,d) \\ nd = k}} n^l q^k =\sum_{k=1}^\infty \sum_{\substack{(d,n) \\ nd = k}} d^l q^k$$ In the last equality, we can interchange $d$ and $n$ by symmetry; all that matters is their product is $k$. Finally, notice $$\sum_{\substack{(d,n) \\ nd = k}} d^l =\sum_{d \mathrel{|} k} d^l = \sigma_l(k)$$ and you are done.

• Thanks a lot, Matthew! My only concern is if nd=k, then how do we know d is a divisor of n? I would assume we only know that n divides k and d divides k? – J. Doe Mar 30 '17 at 1:44
• @J.Doe: oops, typo. I meant $d \mathrel{|} k$ instead of $d \mathrel{|} n$. Fixing. – Matthew Leingang Mar 30 '17 at 2:05