Mdthbs

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_2cdotcdotcdot a_n$$

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

Thanks

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

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}&1cdot 1 cdot 1+ 1cdot x cdot 1 + 1cdot 1cdot x + 1cdot xcdot x \ &+xcdot 1 cdot 1+ xcdot x cdot 1 + xcdot 1cdot x + xcdot xcdot x. end{align}$$

Note that if $A$ and $B$ are sets then
$$Atimes B={(a,b):ain A,bin B}$$
so
$$A^2=Atimes A={(a,b):a,bin A}$$
And $$A^{n}=Atimes A^{n-1}$$
So $$A^3={(a,b,c):a,b,cin A}$$
Hence if $A={1,x}$ then
$${1,x}^3={(a,b,c):a,b,cin{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_1cdots 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 ${nchoose 0}=1$ point in $P^{(n)}_0$ and ${nchoose n}=1$ point in $P^{(n)}_n$. Then we see that there are ${nchoose 1}=n$ points in $P_1^{(n)}$ and ${nchoose n-1}=n$ points in $P_{n-1}^{(n)}$. So in general $$left|P_{j}^{(n)}right|={nchoose j}=frac{n!}{j!(n-j)!}$$
Then we define the function $$q(a_1,a_2,...,a_n)=a_1a_2cdots 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|qleft(mathbf{a}in P_{j}^{(n)}right)\
=sum_{j=0}^{n}{nchoose j}x^j=(1+x)^n$$

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

${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}timescdotstimes{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...

$$sumlimits_{(a_1,ldots,a_n)in{1,x}^n} a_1a_2cdots 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}sumlimits_{(a_1,ldots,a_n)in{1,x}^n} a_1a_2cdots a_n&=(1+x)sum_{(a_1,ldots,a_{n-1})in{1,x}^{n-1}}a_1a_2cdots a_{n-1}
\[2ex]&=(1+x)^nend{align}$$