What does $\sum_{(a_1,a_2,...,a_n)\in\{1,x\}^n} a_1a_2\cdot\cdot\cdot a_n$ mean?

Question

In my textbook, I have this summation, but I can't understand what it means:

$$\sum_{(a_1,a_2,...,a_n)\in\{1,x\}^n} a_1a_2\cdot\cdot\cdot a_n$$

For example, if $n = 3$, what would this summation expand as?

Thanks

Answer 1

Every $a_i$ is either $1$ or $x$, and you're taking the sum over all possibilities. For example, for $n=3$ you have $2^3$ terms (in order?): $$\begin{align}&1\cdot 1 \cdot 1+ 1\cdot x \cdot 1 + 1\cdot 1\cdot x + 1\cdot x\cdot x \\ &+x\cdot 1 \cdot 1+ x\cdot x \cdot 1 + x\cdot 1\cdot x + x\cdot x\cdot x. \end{align}$$

Answer 2

It just means each $a_i \in \{1,x\}$. With $n=3$ the sum is $$(1\cdot 1 \cdot 1) + (1\cdot 1 \cdot x) + (1\cdot x \cdot 1) + (1\cdot x \cdot x) + (x\cdot 1 \cdot 1) + (x\cdot 1 \cdot x) + (x\cdot x \cdot 1) + (x\cdot x \cdot x)$$ $$= 1 + 3x + 3x^2 + x^3.$$

Answer 3

Note that if $A$ and $B$ are sets then $$A\times B=\{(a,b):a\in A,b\in B\}$$ so $$A^2=A\times A=\{(a,b):a,b\in A\}$$ And $$A^{n}=A\times A^{n-1}$$ So $$A^3=\{(a,b,c):a,b,c\in A\}$$ Hence if $A=\{1,x\}$ then $$\{1,x\}^3=\{(a,b,c):a,b,c\in\{1,x\}\}$$ $$\begin{align} =\{&(1,x,x),(x,1,x),(x,x,1)\\ &(1,1,x),(1,x,1),(x,1,1)\\ &(1,1,1),(x,x,x)\} \end{align}$$ And in general, $\{1,x\}^n$ is going to have $2^n$ points. The sum in question is a sum over all those points: $$S_n=\sum_{(a_1,...,a_n)\in\{1,x\}^n}a_1\cdots a_n$$ Which will be a sum of $2^n$ terms.

Let $P^{(n)}_j$ be the set of all points $(a_1,a_2,...,a_n)$ such that there are $j$ entries $a_k$ that are $x$, and there are $n-j$ entries $a_i$ that are $1$. We see that there is ${n\choose 0}=1$ point in $P^{(n)}_0$ and ${n\choose n}=1$ point in $P^{(n)}_n$. Then we see that there are ${n\choose 1}=n$ points in $P_1^{(n)}$ and ${n\choose n-1}=n$ points in $P_{n-1}^{(n)}$. So in general $$\left|P_{j}^{(n)}\right|={n\choose j}=\frac{n!}{j!(n-j)!}$$ Then we define the function $$q(a_1,a_2,...,a_n)=a_1a_2\cdots a_n$$ And see that, since points in $P^{(n)}_j$ by definition have $j$ entries equal to $x$, $$\mathbf{a}\in P_{j}^{(n)}\Rightarrow q(\mathbf{a})=x^j$$ So of course $$S_n=\sum_{j=0}^{n}\left|P_{j}^{(n)}\right|q\left(\mathbf{a}\in P_{j}^{(n)}\right)\\ =\sum_{j=0}^{n}{n\choose j}x^j=(1+x)^n$$

The final step coming from the Binomial theorem: $$(x+y)^n=\sum_{j=0}^{n}{n\choose j}x^jy^{n-j}$$

Answer 4

$\{1,x\}^n$ is the Cartesian self product of the set to the $n$-th degree. $$\begin{align}\{1,x\}^n &= \overbrace{\{1,x\}\times\{1,x\}\times\cdots\times\{1,x\}}^{\text{$n$ factors}}\\[2ex]&=\{\underbrace{(1,1,\ldots,1, 1)}_{\text{$n$ terms}},(1,1,\ldots, 1,x),\ldots,(x,x,\ldots, x,1),(x,x,\ldots,x,x)\}\end{align}$$

So...

---

$$\sum\limits_{(a_1,\ldots,a_n)\in\{1,x\}^n} a_1a_2\cdots a_n$$

This is the sum, for all possible selections, of the product of $n$ factors each selected independently from the set $\{1,x\}$.

It is clearly equal to $(1+x)^n$

$$\begin{align}\sum\limits_{(a_1,\ldots,a_n)\in\{1,x\}^n} a_1a_2\cdots a_n&=(1+x)\sum_{(a_1,\ldots,a_{n-1})\in\{1,x\}^{n-1}}a_1a_2\cdots a_{n-1} \\[2ex]&=(1+x)^n\end{align}$$