# Generating function: number of partitions that add up to at most $n$

Find a generating function $a_n$, the number of partitions that add up to at most $n$.

So I know that if it were asking the number of partitions of the integer $n$, I would have my generating function as

$$g(x) = \frac{1}{(1-x)(1-x^2)(1-x^3)\cdots}$$

But for now, all I can come up with to handle the "at most" condition is $$\prod_{r=1}^{m\leq n} \frac{1}{1-x^r}, \text{ for some } m.$$ And I really don't think that this is correct. (No solution provided).

HINT: Start with your generating function for $p(n)$:

$$g(x)=\prod_{n\ge 1}\frac1{1-x^n}\;.$$

You want cumulative sums:

$$a_n=\sum_{k=0}^np(k)\;.$$

Therefore you want to convolve the sequence $\langle p(n):n\in\Bbb N\rangle$ with the constant $1$ sequence $\langle 1,1,1,\dots\rangle$, whose generating function is

$$f(x)=\frac1{1-x}\;.$$

What is the generating function of that convolution in terms of $g$ and $f$?

• Is it just $f\cdot g?$ I don't understand why it is if this is the case. – TheRealFakeNews Mar 18 '13 at 23:04
• @Alan: Assuming that you mean the product, making it $$\frac1{1-x}\prod_{n\ge 1}\frac1{1-x^n}\;,$$ yes. Can you pin down what part you don’t understand? – Brian M. Scott Mar 18 '13 at 23:06
• Yeah, I meant product. I don't understand why that changes the number of partitions of the integer $n$ to number of partitions that add up to at most $n$. I guess I don't understand the convolution part. The only time I've been introduced to that was in differential equations. – TheRealFakeNews Mar 18 '13 at 23:14
• @Alan: The coefficient of $x^n$ in the product $$\left(\sum_{n\ge 0}a_nx^n\right)\left(\sum_{n\ge 0}b_nx^n\right)$$ is $$\sum_{k=0}^na_kb_{n-k}\;.$$ If each $b_k=1$, this is just $$\sum_{k=0}^na_k\;,$$ giving you the cumulative total of the $a_k$’s. – Brian M. Scott Mar 18 '13 at 23:16