Generating Functions Partitions

Question

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?

Answer 1

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.

Answer 2

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.

Answer 3

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} $$