Generating series for binary string with weight function, w(x)= (number of 1's in the string) + (length of string) For a binary string $s$, define its weight $w(s)$ to be the number of $1$’s in the string plus the length of the string itself. For example, $w(101101) = 10$. I want to find the generating series of set $T$ of all binary strings.
I have used a combinatorial argument to show that $w(s) = 2^n + \frac{n(n+1)}2$.

*

*$\sum_{k=0}^n {n \choose k} + k $, where $k$ is the number of ones in the string

However, my textbook asks to use the product lemma to get the generating series for a string of length $n$. How could I solve this problem using that method?
 A: The generating function for all strings, which I will call $W(x)$, is by definition
$$
W(x) = \sum_s x^{w(s)},
$$
where $s$ ranges over all binary strings. It seems like you first want to find the generating function for only strings of length $n$, that it you want to first find
$$
W_n(x)=\sum_{s\,:\,\text{len}(s)=n}x^{w(s)},
$$
and you want to find that using the product lemma. This means you want to express strings of length $n$ as a concatenation of smaller sets of strings, then compute $W_n(x)$ as the products of those smaller generating functions.
Since a string of length $n$ is a concatenation of $n$ strings of length $1$, the generating function for strings of length $n$ is just
$$
W_n(x)=W_1(x)\times \dots\times W_1(x)=[W_1(x)]^n
$$
Fortunately, $W_1(x)$ is simple; there are two strings of length $1$, one which has weight $1$, the other with weight $2$, so $W_1(x)=x+x^2$.
Finally, you ultimately wanted to find $W(x)$, the g.f. for all strings. This is found by summing $W_n(x)$ over all $n$:
$$
W(x)=W_0(x)+W_1(x)+W_2(x)+\dots
$$
