Mfcttrf

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

$$sum_(a_1,a_2,...,a_n)in1,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?): $$beginalign&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. endalign$$

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,cin1,x$$
$$beginalign
=&(1,x,x),(x,1,x),(x,x,1)\
&(1,1,x),(1,x,1),(x,1,1)\
&(1,1,1),(x,x,x)
endalign$$
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)in1,x^na_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=fracn!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$,
$$mathbfain P_j^(n)Rightarrow q(mathbfa)=x^j$$
So of course
$$S_n=sum_j=0^nleft|P_j^(n)right|qleft(mathbfain P_j^(n)right)\
=sum_j=0^nnchoose jx^j=(1+x)^n$$

The final step coming from the Binomial theorem:
$$(x+y)^n=sum_j=0^nnchoose jx^jy^n-j$$

$1,x^n$ is the Cartesian self product of the set to the $n$-th degree. $$beginalign1,x^n &= overbrace1,xtimes1,xtimescdotstimes1,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)endalign$$

So...

$$sumlimits_(a_1,ldots,a_n)in1,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$

$$beginalignsumlimits_(a_1,ldots,a_n)in1,x^n a_1a_2cdots a_n&=(1+x)sum_(a_1,ldots,a_n-1)in1,x^n-1a_1a_2cdots a_n-1
\[2ex]&=(1+x)^nendalign$$