2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ I'm guessing you can show it on full induction. If the assumption is true for $I_n$ than you have to show it's true for $I_{n+1}$ which is $(a^0 + a^{c_{n+1}}) I_n = (1 + a^{c_{n+1}}) I_n$. $\endgroup$ – clemens Oct 28 '17 at 16:39
  • $\begingroup$ The basis ($n=1$) seems suspiciously trivial... $\endgroup$ – TheNotMe Oct 28 '17 at 16:45
3
$\begingroup$

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}
$\endgroup$
  • $\begingroup$ Oh, so it isn't related to how many times $a^i$ is involved. Thank you. $\endgroup$ – TheNotMe Oct 28 '17 at 20:15

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.