Let $S$ be a set with $n$ elements. I want to compute the following generating function:
$$G(x)=\sum_{A\subseteq S}x^{|A|}.$$ I want to understand the following equality: $G(x)=(1+x)^n$.
In a book, it says "each of the $n$ elements in the set contributes the term $(1+x)$ to the generating function."
Is there a better explanation?
Notice the following. When you place $$(1+x)^n=(1+x)(1+x)\cdots (1+x),$$ and you unfold the product, every multiplicand will contribute with either a $1$ or an $x.$ Call the multiplicands $(1+x)^n=p_1\cdots p_n,$ where $p_i=1+x.$ If you decide to pick the $x$ in the $i-$th multiplicand, is like you are considering one more (the exponent of the $x$) in the size of the sets that you want. So this corresponds to adding $i$ to the set. In that way, the coefficient of $x^k$ in the expansion corresponds to the number of ways to create a set of size $k$ out of $n$ elements, or $\binom{n}{k}.$
For example, if $n=3$ you have $$(1+x)(1+\color{red}{x})(1+\color{blue}{x})=\underbrace{1\cdot 1\cdot 1}_{\emptyset}+\underbrace{x\cdot 1\cdot 1}_{\{1\}}+\underbrace{x\cdot \color{red}{x}\cdot 1}_{\{1,2\}}+\cdots +\underbrace{1\cdot 1\cdot \color{blue}{x}}_{\{3\}}+\cdots +\underbrace{x\cdot \color{red}{x}\cdot \color{blue}{x}}_{\{1,2,3\}}.$$ Notice that in general, unfolding the product gives rise to $2^n$ summands (that is the beauty of the binomial theorem, it puts together the $n+1$ size possibilities).