Generating Functions Partitions Let $U(x)=\sum_{n=0}^{\infty} u_nx^n$, where $u_n$ is the number of partitions of $n$ into at most two parts. For example, $u_4=3$ because $4$ can be partitioned into at most two parts as $4$, $3+1$, or $2+2$. Use the convention that $u_0=1$.
Then $\frac 1{U(x)}$ is a polynomial. What polynomial is it? 

Can I use generating functions to solve this? If so, how?
 A: Hint:
First show that (think about how the partitions of $n$ are related to those of $n-2$)
$$u_{n} = u_{n-2}+1$$
By multiplying the recurence relation above by $x^{n}$ and summing over $n=2,3,\ldots$ we get
$$U(x)-1-x = x^2 U(x) + \frac{x^2}{1-x}$$
Showing that $\frac{1}{U(x)}$ is a polynomial is now just simple algebra.
A: Note that $u_n$ is the number of ordered pairs $\langle k,\ell\rangle$ of non-negative integers such that $k+\ell=n$ and $k\le\ell$. It’s not hard to show that
$$u_n=\left\lfloor\frac{n}2\right\rfloor+1$$
for all $n\in\Bbb N$. Thus,
$$\begin{align*}
U(x)&=\sum_{n\ge 0}\left(\left\lfloor\frac{n}2\right\rfloor+1\right)x^n\\
&=\sum_{n\ge 0}\left\lfloor\frac{n}2\right\rfloor x^n+\sum_{n\ge 0}x^n\\
&=\sum_{n\ge 0}nx^{2n}+\sum_{n\ge 0}nx^{2n+1}+\sum_{n\ge 0}x^n\\
&=(1+x)\sum_{n\ge 0}nx^{2n}+\sum_{n\ge 0}x^n\\
&=(1+x)\sum_{n\ge 1}nx^{2n}+\sum_{n\ge 0}x^n\\
&=(1+x)x^2\sum_{n\ge 1}n\left(x^2\right)^{n-1}+\sum_{n\ge 0}x^n\\
&=\frac12(1+x)x\sum_{n\ge 1}n\left(x^2\right)^{n-1}(2x)+\sum_{n\ge 0}x^n\;.\tag{1}
\end{align*}$$
Now find closed forms for the two summations in $(1)$, and take the reciprocal of the resulting expression. You should know a closed form for the second summation, and I’ve manipulated the first into a form that makes it quite easy to find a closed form for it; just use a little calculus.
A: Hint: It is pretty easy to see that
$$
u_n=\left\lfloor\frac n2\right\rfloor+1
$$
This will be a useful series here
$$
\begin{align}
\frac1{(1-x)^2}
&=\frac{\mathrm{d}}{\mathrm{d}x}\frac1{1-x}\\
&=\frac{\mathrm{d}}{\mathrm{d}x}\left(1+x+x^2+x^3+\dots\,\right)\\[6pt]
&=1+2x+3x^2+\dots
\end{align}
$$
Thus,
$$
\begin{align}
U(x)
&=1+x+2x^2+2x^3+3x^4+3x^5+\cdots\\[12pt]
&=(1+x)(1+2x^2+3x^4+\cdots\,)\\[6pt]
&=\frac{1+x}{(1-x^2)^2}
\end{align}
$$
