# Proving the closed form for $\sum_{k_1=0}^{\infty}\cdots\sum_{k_n=0}^{\infty}\frac{1}{a^{k_1+\cdots+k_n}}$, where $k_1 \neq\cdots\neq k_n$ and $a>1$?

I recently encountered a problem that requires us to sum the series

$$\sum_{i=0}^{\infty} \sum_{j=0}^{\infty} \sum_{k=0}^{\infty} \frac{1}{3^i 3^j 3^k}$$

given the condition that $i \neq j \neq k$. Upon generalizing the problem, I get this:

$$\sum_{k_1=0}^{\infty}\sum_{k_2=0}^{\infty}\cdots\sum_{k_n=0}^{\infty} \frac{1}{a^{k_1+\cdots+k_2}} = \frac{n! \times a^n}{\prod_{i=1}^{n} (a^i - 1)}$$

for $a>1$ and $k_1 \neq \cdots \neq k_2$, i.e. all indices are distinct at all times. Now the closed form expression (on the right hand side) for the infinite series has been obtained purely by guessing. However, I've verified that the equation works, through a computer program. The only task now left to do is to prove the formula, which I'm unable to do.

• @NilabroSaha How did you come up with the second equation? – 3-in-441 Dec 28 '16 at 3:57
• After solving the first problem, I replaced 3 with 'a' and found a closed form expression $\frac{6a^3}{(a-1)(a^2-1)(a^3-1)}$. So I though that maybe the general expression can be as I have stated in the question. – Nilabro Saha Dec 28 '16 at 3:59
• You can do this by inclusion-exclusion on $i,j,k$. Ignore the condition that they're all different, then subtract off the unwanted terms, add back the things that were subtracted twice, etc... – Scott Burns Dec 28 '16 at 4:28
• Sorry for misreading your post and giving the wrong title. But FWIW, the notation $i\neq j\neq k$ does not imply that the three indices are distinct. It might be that $i=k=1$ and $j=2$, for example. The relation $\neq$ isn't transitive, in other words. – symplectomorphic Dec 28 '16 at 5:12
• For my question though, all the indices are distinct at any instant. How should I express that? – Nilabro Saha Dec 28 '16 at 5:16

Consider the sum $$\sum_{i=0}^{\infty}\sum_{j=i+1}^\infty\sum_{k=j+1}^\infty\frac{1}{3^i3^j3^k} = \sum_{i=0}^{\infty}\left(\frac{1}{3^i}\sum_{j=i+1}^\infty\left(\frac{1}{3^j}\left(\sum_{k=j+1}^\infty\frac{1}{3^k}\right)\right)\right) =$$$$\frac{1}{2}\sum_{i=0}^{\infty}\left(\frac{1}{3^i}\sum_{j=i+1}^\infty\left(\frac{1}{3^j}\cdot 3^{-j}\right)\right) = \frac{1}{2}\sum_{i=0}^{\infty}\left(\frac{1}{3^i}\sum_{j=i+1}^\infty\left(9^{-j}\right)\right) =$$ $$\frac{1}{2}\sum_{i=0}^{\infty}\left(\frac{1}{3^i}\cdot3^{-2i-2}\cdot\frac{9}{8}\right)= \frac{1}{16}\sum_{i=0}^\infty 3^{-3i} = \frac{1}{16}\cdot\frac{27}{26} = \frac{27}{416}$$ This is summing over all $i<j<k$, which is one of the six possible cases when $i,j,k$ are distinct. Thus, the above number is one sixth of the answer.

To be clear, each of the intermediate steps were simply using the formula for infinite geometric series.

Now let's go for the general case. Suppose your general formula works for some $n$. Similarly, consider the sum

$$\sum_{k_1=0}^\infty \sum_{k_2=k_1+1}^\infty \sum_{k_3=k_2+1}^\infty... \sum_{k_n=k_{n-1}+1}^\infty \frac{1}{a^{k_1}a^{k_2}...a^{k_n}} =$$ (replacing $k_2$ with $k_2' = k_2-k_1-1$) $$\sum_{k_1=0}^\infty \sum_{k_2'=0}^\infty \sum_{k_3=k_2'+k_1+2}^\infty... \sum_{k_n=k_{n-1}}^\infty \frac{1}{a^{k_1}a^{k_2'+k_1+1}...a^{k_n}} =$$ (now, replacing $k_3$ with $k_3' = k_3-k_1-1$) $$\sum_{k_1=0}^\infty \sum_{k_2'=0}^\infty \sum_{k_3'=k_2'+1}^\infty\sum_{k_4 = k_3'+k_1+2}^\infty... \sum_{k_n=k_{n-1}}^\infty \frac{1}{a^{k_1}a^{k_2'+k_1+1}a^{k_3'+k_1+1}...a^{k_n}} =$$ (repeating this until we define $k_n'$) $$\sum_{k_1=0}^\infty\sum_{k_2'=0}^\infty\sum_{k_3'=k_2'+1}^\infty...\sum_{k_n'=k_{n-1}'+1}^\infty \frac{1}{a^{nk_1+n-1}a^{k_2'}...a^{k_n'}} = \sum_{k_1=0}^\infty \frac{1}{a^{nk_1+n-1}}c =$$$$\frac{ca^{1-n}}{1-a^{-n}} = \frac{ca}{a^n-1}$$ Where $c$ is simply your formula, with $n-1$ being the number of sums, without the factorial term. Just as we had to multiply by $6=3!$ above, here, we multiply by $n!$ to come to your formula.

That takes care of the inductive step. The base case should be straightforward. My apologies if any of this was unclear.

• Shouldn't it be $k_2 = k_1 + 1$ and so on? – Nilabro Saha Dec 28 '16 at 4:36
• @NilabroSaha Corrected my mistake. It should be good now. – florence Dec 28 '16 at 4:46

After writing this I noticed it looks close to the approach in florence answer, so I leave it as CW to complement that answer as the induction step here is a bit different.

By symmetry the product can be written

$$n!\sum_{i_1=0}^\infty\sum_{i_2=i_1+1}^\infty\sum_{i_3=i_2+1}^\infty\cdots \sum_{i_n=i_{n-1}+1}^\infty \frac{1}{a^{i_1+\ldots+i_n}}$$

Performing the sums one-by-one from right to left the summand changes to

$$\frac{1}{a^{i_1+\ldots+i_n}}\to \frac{1}{a^{i_1+\ldots+i_{n-2}}a^{2i_{n-1}}} \left(\frac{1}{a-1}\right)\to \frac{1}{a^{i_1+\ldots+i_{n-3} + i_{n-2}}a^{3i_{n-2}}} \left(\frac{1}{a^2-1}\right)\left(\frac{1}{a-1}\right)$$

The pattern we see, the summand after performing $k$ sums is $\frac{1}{a^{i_1+\ldots + i_{n-k-1}}a^{(k+1)i_{n-k}}}\frac{1}{\prod_{i=1}^k a^i-1}$, can be proven by induction:

$$\sum_{i_{n-k} = i_{n-k}+1} \frac{1}{a^{i_1+\ldots + i_{n-k-1}}a^{(k+1)i_{n-k}}}\frac{1}{\prod_{i=1}^k a^i-1} = \frac{1}{a^{i_1+\ldots + i_{n-k-2}}a^{(k+2)i_{n-k-1}}}\frac{1}{\prod_{i=1}^{k+1} a^i-1}$$

which is the induction hypotesis for $k+1$. Taking $k=n-1$ we get

$$n!\sum_{i_1=0}^\infty\sum_{i_2=i_1+1}^\infty\sum_{i_3=i_2+1}^\infty\cdots \sum_{i_n=i_{n-1}+1}^\infty \frac{1}{a^{i_1+\ldots+i_n}} = \frac{n!}{\prod_{i=1}^{n-1}a^i-1}\sum_{i=0}^\infty \frac{1}{a^{ni_1}} = \frac{n!a^n}{\prod_{i=1}^{n}a^i-1}$$

• @NilabroSaha This is your choice, but I would consider leaving the accepted mark on the other answer as it was first with the right idea. I just meant this to be supplementary. – Winther Dec 28 '16 at 6:18
• I'm torn. I wanted to mark both of them as accepted. – Nilabro Saha Dec 28 '16 at 9:25