Let $b_{n}$ denote the number of compositions of $n$ into $k$ parts, where each part is one or two. Find the generating series for $b_{n}$ I am stuck with this combinatorics problems -
Let $n$ be a positive integer and let $b_{n}$ denote the number of compositions of $n$ into $k$ parts, where each part is one or two. For example, $(1, 2, 1, 2, 1)$ and $(2, 2, 1, 1, 1)$ are two compositions of $n = 7$ into $k = 5$ parts.
Firstly, we need to find the generating series for $b_{n}$
Secondly, Prove that $b_{n} = {k \choose n-k}$ for $k\le n \le2k$ and $b_{n} = 0$ otherwise.
 A: In order to calculate the generating series -
Let {1,2}$^{}$ be the set of compositions with k parts, each of which is either 1 or 2.
Then, applying the "Product Lemma"
$$\varphi_{s}(x) = (\varphi_{(1,2)} (x))^{k} = (x+x^{2})^{k} $$
Proving -
A composition of n with k parts will have $i$ parts equal
to 2, for some $0\le i\le k$. Note that the number of parts equal to 1 is $k-i$,
and $n = (k-i) + 2i$, giving $i = n-k$. There are $k$ positions for the $n-k$
parts equal to 2, so there are a total of {k \choose n-k} compositions of $n$ into $k$ parts, each either $1$ or $2$. Note that $0\le i\le k$ implies $k\le n\le 2k$, and the number of compositions is zero otherwise.
A: There's a nice combinatorial proof for the second question:
The number of compositions of $n$ into $k$ parts each equal to $1$ or $2$ is equal to the number of compositions of $n-k$ into $k$ parts each equal to $0$ or $1$. Clearly there must be $n-k$ $1$s in such a composition, and there are $\binom k{n-k}$ ways of arranging those $1$s among the $k$ parts.
A: (1) It is $(x+x^2)^k=x^k(1+x)^k$
(2) The coefficient of $x^n$ is in $x^k(1+x)^k$ same as $x^{n-k}$ in $(1+x)^k$. Therefore by binomial theorem it is ${k\choose n-k}$
