Let's change the order of the summation: $\sum_{k=1}^n \sum_{(n)} e_k 2^{e_1 + \cdots + e_k - 2k - n}$ Note that for a given $k$, it doesn't depend on anything after $e_k$. Hence for any given term $e_k2^{e_1 + \cdots + e_k - 2k - n}$, we can multiply it by $2^{n-k}$ (to simplify the identical terms of counting all after $e_k$ into one term): $= \sum_{k=1}^n \sum_{(k)} e_k 2^{e_1 + \cdots + e_k - 2k - n} \cdot 2^{n-k}$ $= \sum_{k=1}^n \sum_{(k)} e_k 2^{e_1 + \cdots + e_k - k}$ Next, if $e_k = 0$, it doesn't contribute to the sum, hence we will assume those where $e_k = 1$. $= \sum_{k=1}^{n} \sum_{(k)} 2^{e_1 + \cdots + e_{k-1} - (k-1)}$ $= \sum_{k=0}^{n-1} \sum_{(k)} 2^{e_1 + \cdots + e_k - k}$ We will take care of each term separately. Note that for any given $i, 0 \le i \le k$, the number of solutions of $e_1 + e_2 + \cdots + e_k = i$ is $\binom{k}{i}$. Hence we can simplify $\sum_{(k)} 2^{e_1 + \cdots + e_k - k}$ to $\sum_{i=0}^k \binom{k}{i} \cdot 2^{i - k}$. Note that this is simple to calculate: $\sum_{i=0}^k \binom{k}{i} \cdot 2^{i - k}$ $= 2^{-k} \cdot \sum_{i=0}^k \binom{k}{i} \cdot 2^{i}$ $= 2^{-k} \cdot \sum_{i=0}^k \binom{k}{i} \cdot 2^{i} \cdot 1^{k-i}$ $= 2^{-k} \cdot (2+1)^k$ $= 2^{-k} \cdot 3^k$ $= \left( \dfrac{3}{2} \right)^k$ Hence our sum reduces to: $= \sum_{k=0}^{n-1} \left( \dfrac{3}{2} \right)^k$ $= \dfrac{\left( \dfrac{3}{2} \right)^n - 1}{\dfrac{3}{2} - 1}$ by geometric series sum $= \boxed{2 \left( \dfrac{3}{2} \right)^n - 2}$

The fact this is a fallacy is most easily seen by computing the sum for $n=1$, when it should be $2^{1 - 2 - 1} = 1/4$, while your formula yields $2(3/2) - 2 = 1$.

Pfft $-2k - k = -k$ :headbash: Fixed: chaotic_iak wrote: Let's change the order of the summation: $\sum_{k=1}^n \sum_{(n)} e_k 2^{e_1 + \cdots + e_k - 2k - n}$ Note that for a given $k$, it doesn't depend on anything after $e_k$. Hence for any given term $e_k2^{e_1 + \cdots + e_k - 2k - n}$, we can multiply it by $2^{n-k}$ (to simplify the identical terms of counting all after $e_k$ into one term): $= \sum_{k=1}^n \sum_{(k)} e_k 2^{e_1 + \cdots + e_k - 2k - n} \cdot 2^{n-k}$ $= \sum_{k=1}^n \sum_{(k)} e_k 2^{e_1 + \cdots + e_k - 3k}$ Next, if $e_k = 0$, it doesn't contribute to the sum, hence we will assume those where $e_k = 1$. $= \sum_{k=1}^n \sum_{(k)} 2^{e_1 + \cdots + e_{k-1} - 3(k-1) - 2}$ $= \sum_{k=0}^{n-1} \sum_{(k+1)} 2^{e_1 + \cdots + e_k - 3k - 2}$ We will take care of each term separately. Note that for any given $i, 0 \le i \le k$, the number of solutions of $e_1 + e_2 + \cdots + e_k = i$ is $\binom{k}{i}$. Hence we can simplify $\sum_{(k+1)} 2^{e_1 + \cdots + e_k - 3k - 2}$ to $\sum_{i=0}^k \binom{k}{i} \cdot 2^{i - 3k - 2}$. Note that this is simple to calculate: $\sum_{i=0}^k \binom{k}{i} \cdot 2^{i - 3k - 2}$ $= 2^{-3k - 2} \cdot \sum_{i=0}^k \binom{k}{i} \cdot 2^{i}$ $= 2^{-3k - 2} \cdot \sum_{i=0}^k \binom{k}{i} \cdot 2^{i} \cdot 1^{k-i}$ $= 2^{-3k - 2} \cdot (2+1)^k$ $= 2^{-3k - 2} \cdot 3^k$ $= \dfrac{1}{4} \cdot \left( \dfrac{3}{8} \right)^k$ Hence our sum reduces to: $= \sum_{k=0}^{n-1} \dfrac{1}{4} \cdot \left( \dfrac{3}{8} \right)^k$ $= \dfrac{1}{4} \cdot \dfrac{1 - \left( \dfrac{3}{8} \right)^n}{1 - \dfrac{3}{8}}$ by geometric series sum $= \boxed{\dfrac{2}{5} - \dfrac{2}{5} \cdot \left( \dfrac{3}{8} \right)^n}$