Generalized sum of distinct integers $ \sum_{\stackrel{a_1,a_2,\ldots, a_n>0}{\text{all distinct}}} 2^{-\sum a_j} $

Question

The exact question:

Let $$ \Large S_n = \sum_{\stackrel{a_1, a_2, \ldots , a_n > 0}{(a_1, a_2, \ldots, a_n) \text{ are all distinct}}} \dfrac1{2^{a_1 + a_2 + \cdots + a_n}} $$ It's trivial that $S_1 = 1$ and $S_2 = \frac23$. Can we find a general form of $S_n ?$

Background/Attempt:

I was trying to compute $ \sum \limits_{\stackrel{i,j,k>0}{i \ne j, i \ne k , j \ne k}} \dfrac1{2^{i+j+k}} $, which brought me to hypergeometricx' answer here.

Using their exact notations, we can get:

$$ \sum \limits_{\stackrel{i,j,k>0}{i \ne j, i \ne k , j \ne k}} \dfrac1{2^{i+j+k}} = \displaystyle \left[ \sum_{i,j,k>0 } - \left( \sum_{\stackrel{i,j,k>0 }{i=j \ne k }} + \sum_{\stackrel{i,j,k>0 }{i\ne j=k }} \right) + \sum_{\stackrel{i,j,k>0 }{i=j=k }} \right] \dfrac1{2^{i+j+k}} = 1^3 - (\tfrac13 + \tfrac13) + \tfrac17 = \frac27$$

Equivalently,

$$ S_3 = \left( \sum_{i>0} \dfrac1{2^i} \right )^3 - {\color{red}{3}} \left( \sum_{i>0} \dfrac1{2^{2i}} \right) \left( \sum_{i>0} \dfrac1{2^{i}} \right) + {\color{red}{2}} \left( \sum_{i>0} \dfrac1{2^{3i}} \right) = \dfrac27 $$

Now, what got me interested is how can we decipher the coefficients colored in red. So I drew a Venn Diagram, and via inclusion-exclusion principle:

Moving forward, I tried to evaluate $S_4$ in the same manner.

However, I'm unable to decipher the following red coefficients:

$$ \dfrac8{105} \stackrel{?}{=} S_4\stackrel{?}{=} \underbrace{\left( \sum_{i>0} \dfrac1{2^i} \right )^4 }_{=\, 1} - {\color{red}{6}} \left( \sum_{i>0} \dfrac1{2^{3i}} \right) \left( \sum_{i>0} \dfrac1{2^{i}} \right) + {\color{red}{3}} \left( \sum_{i>0} \dfrac1{2^{2i}} \right) ^2 - {\color{red}{6}} \left( \sum_{i>0} \dfrac1{2^{4i}} \right) $$

Let alone

$$ \dfrac8{651} \stackrel{?}{=} S_5\stackrel{?}{=} \underbrace{\left( \sum_{i>0} \dfrac1{2^i} \right )^5 }_{=\, 1} - {\color{red}{10}} \left( \sum_{i>0} \dfrac1{2^{4i}} \right) \left( \sum_{i>0} \dfrac1{2^{i}} \right) + {\color{red}{19}} \left( \sum_{i>0} \dfrac1{2^{3i}} \right)\left( \sum_{i>0} \dfrac1{2^{2i}} \right) - {\color{red}{38}} \left( \sum_{i>0} \dfrac1{2^{5i}} \right) $$

I conjecture that, should this pattern continue

$$ S_n = 1 - { \color{red}{b_1}} \left( \sum_{j>0} \dfrac1{2^{(n-1)i}}\right) \left( \sum_{j>0} \dfrac1{2^{1i}} \right) + { \color{red}{b_2}} \left( \sum_{j>0} \dfrac1{2^{(n-2)i}} \right) \left( \sum_{j>0} \dfrac1{2^{2i}} \right) - { \color{red}{b_3}} \left( \sum_{j>0} \dfrac1{2^{(n-3)i}} \right) \left( \sum_{j>0} \dfrac1{2^{3i}} \right) + \cdots \pm { \color{red}{b_n}} \left( \sum_{j>0} \dfrac1{2^{1i}} \right) \left( \sum_{j>0} \dfrac1{2^{(n-1) i}} \right) \mp { \color{red}{b_n}} \left( \sum_{j>0} \dfrac1{2^{n i}} \right) $$

And since $ \sum \limits_{j>0} \frac1{2^{k \cdot j}} = \frac1{2^k - 1}$. The equation above is equivalent to:

$$ \begin{array} { r c l } S_n &=& 1 - \dfrac { \color{red}{b_1}} { (2^{n-1} - 1) (2^1 - 1)} + \dfrac { \color{red}{b_2}} { (2^{n-2} - 1) (2^2 - 1)} - \dfrac { \color{red}{b_3}} { (2^{n-3} - 1) (2^3 - 1)} + \cdots \pm \dfrac { \color{red}{b_n}} { (2^1 - 1) (2^{n-1} - 1)} \mp \dfrac { \color{red}{b_n}} { 2^{n} - 1} \\ \phantom0 \\ &=&1 + \left( \sum \limits_{k=1}^{n-1} \dfrac { (-1)^k \cdot \color{red}{b_k}} { (2^{n-k} - 1) (2^k - 1)} \right) + \dfrac { (-1)^n \cdot \color{red}{b_n}} { 2^n - 1} \end{array} $$

I suspect that $ {\color{red}{b_1}} = \binom n2 $. But I got nothing to go from here.

Answer 1

Restrict our attention to the case where $ a_ 1 < a_2 < a_3 \ldots $. For each instance, there are $n!$ such terms that we want to sum, so we'd have to multiply the summation by $n!$.

Use the substitution: $a_1 = x_1,$ $a_2 = a_1 + x_2 = x_1 + x_2,$ $a_3 = a_2 + x_3 = x_1 + x_2 +x_3 , \ldots,$ where $ x_ i \geq 1$, with no further restrictions.

This gives us $ \sum a_i = n x_ 1 + (n-1) x_2 + (n-2) x_3 + \ldots + x_n = \sum_{i=1}^n (n+1 - i) x_i$, and thus

$$ \sum \frac{1}{ 2^ {\sum a_i }} = \sum_{ x_i} \frac{1}{ 2^{ \sum_{i=1}^n (n+1 - i) x_i }} \\ = \prod_{i=1}^n \sum_{x_i} \frac{1}{2^{(n+1 - i)x_i}} \\ = \prod_{i=1}^n \frac{1}{2^{n+1-i} - 1 } \\ = \prod_{j=1}^n \frac{1}{ 2^j - 1 }$$

Hence, the summation has value $ n! \prod_{j=1}^n \frac{1}{ 2^j - 1 }$.

Answer 2

Given a tuple of pairwise distinct $(a_1,\cdots ,a_n)$, any permutation of this tuple is also included in the summation. Since there are $n!$ such permutations in total, we can write $$ S{=\sum_{a_n>a_{n-1}>\cdots>a_2>a_1\ge 1}\frac{n!}{2^{a_1+\cdots+a_n}} \\= \sum_{a_{n-1}>\cdots>a_2>a_1\ge 1}\sum_{a_n=a_{n-1}+1}^\infty\frac{n!}{2^{a_1+\cdots+a_n}} \\= \sum_{a_{n-1}>\cdots>a_2>a_1\ge 1}\frac{n!}{2^{a_1+\cdots+a_{n-2}+2a_{n-1}}} \\= \sum_{a_{n-2}>\cdots>a_2>a_1\ge 1}\sum_{a_{n-1}=a_{n-2}+1}\frac{n!}{2^{a_1+\cdots+a_{n-2}+2a_{n-1}}} \\= \sum_{a_{n-2}>\cdots>a_2>a_1\ge 1}\frac{n!\cdot\frac{1}{3}}{2^{a_1+\cdots+a_{n-3}+3a_{n-2}}} \\= \sum_{a_{n-3}>\cdots>a_2>a_1\ge 1}\sum_{a_{n-2}=a_{n-3}+1}\frac{n!\cdot\frac{1}{3}}{2^{a_1+\cdots+a_{n-3}+3a_{n-2}}} \\= \sum_{a_{n-3}>\cdots>a_2>a_1\ge 1}\sum_{a_{n-2}=a_{n-3}+1}\frac{n!\cdot\frac{1}{3}\cdot\frac{1}{7}}{2^{a_1+\cdots+a_{n-4}+4a_{n-3}}} \\= \\\vdots \\= n!\sum_{a_{n-k}>\cdots>a_2>a_1\ge 1}\frac{\prod_{i=1}^k\frac{1}{2^i-1}}{2^{a_1+\cdots+a_{n-k-1}+(k+1)a_{n-k}}} \\= \\\vdots \\= n!\sum_{a_1\ge 1}\frac{\prod_{i=1}^{n-1}\frac{1}{2^i-1}}{2^{na_1}} \\=n!\prod_{i=1}^{n}\frac{1}{2^i-1}. } $$ The first four terms are $S_1=1$, $S_2=\frac{2}{3}$, $S_3=\frac{2}{7}$ and $S_4=\frac{8}{105}$.