Calculating this sum in $O(n)$ time

Question

Assume that $\forall 1 \leq i \leq n : a>0, c_i > 0 $ where $n \in \mathbb{N}$. I need to show that it is possible to compute this sum in $O(n)$ time:

$$I = \sum_{(\epsilon_1,...,\epsilon_n) \in \{0,1\}^n}a^{c_1 \epsilon_1 + ... + c_n \epsilon_n}$$

(a sum over all binary vectors of length $n$) I notice that in $I$, for any fixed $1\leq i \leq n$, we have that $a^{c_i\epsilon_i} = 1$ in $2^{n-1}$ of the times, and $a^{c_i}$ in the other $2^{n-1}$ of the times. So $I$ can be written as follows:

$$2^{n-1}\cdot a^{c_1} \cdot \sum_{(\epsilon_2,...,\epsilon_n)\in \{0,1\}^{n-1}}a^{c_2\epsilon_2}\cdot ... \cdot a^{c_n \epsilon_n} + 1 \cdot \sum_{(\epsilon_2,...,\epsilon_n)\in \{0,1\}^{n-1}}a^{c_2\epsilon_2}\cdot ... \cdot a^{c_n \epsilon_n}$$

But coming to expand this for $i=2,...,n$ I immediately realize that this won't turn out to be $O(n)$. I would appreciate some guidance.

Answer 1

You can prove this by full induction, which gives you an algorithm, too. The claim is $$I_n = \sum_{(\epsilon_1,...,\epsilon_n) \in \{0,1\}^n}a^{c_1 \epsilon_1 + ... + c_n \epsilon_n} = (1 + a^{c_1})(1 + a^{c_2}) \ldots (1 + a^{c_n}) $$ The product of the right side can be computed in $O(n)$ steps if the exponentiation requires constant time.

Proof:

1. For $n=1$ the claim is obviously true: $I_1 = 1 + a^{\epsilon_1}$.
2. $n \rightarrow n+1$: Let the claim be true for $n$: \begin{eqnarray} (1 + a^{c_{n+1}})I_n & = & (1 + a^{\epsilon_{n+1}})\sum_{(\epsilon_1,...,\epsilon_n) \in \{0,1\}^n}a^{c_1 \epsilon_1 + ... + c_n \epsilon_n} \\ & = & \sum_{(\epsilon_1,...,\epsilon_n) \in \{0,1\}^n}a^{c_1 \epsilon_1 + ... + c_n \epsilon_n} + a^{c_{n+1}}\sum_{(\epsilon_1,...,\epsilon_n) \in \{0,1\}^n}a^{c_1 \epsilon_1 + ... + c_n \epsilon_n} \\ & = & \sum_{(\epsilon_1,...,\epsilon_n) \in \{0,1\}^n,\\ \epsilon_{n+1}=0}a^{c_1 \epsilon_1 + ... + c_n \epsilon_n + c_{n+1} \epsilon_{n+1}} + \sum_{(\epsilon_1,...,\epsilon_n) \in \{0,1\}^n,\\ \epsilon_{n+1}=1}a^{c_1 \epsilon_1 + ... + c_n \epsilon_n + c_{n+1} \epsilon_{n+1}} \\ & = & \sum_{(\epsilon_1,...,\epsilon_n,\epsilon_{n+1}) \in \{0,1\}^{n+1}}a^{c_1 \epsilon_1 + ... + c_n \epsilon_n + c_{n+1} \epsilon_{n+1}} \\ & = & I_{n+1} \end{eqnarray}