Generating function for partitions

Question

It is a theorem of Euler that $$\sum p(k)x^k=\prod\frac{1}{1-x^k}.$$ Something which annoys me is how to interpret the right hand side. I know that one can do this analytically, but I would like a purely algebraic interpretation, where the left hand side is viewed as formal power series. Is it possible to give such an interpretation?

Answer 1

The correct answer is: in several books, e.g. Bourbaki, one finds that the infinite product of formal power series is sometimes defined, and it turns out that it is defined in this case, $1/(1-x^k)=1+x^k+x^{2k}+...$

Answer 2

Write this as $\sum p(n)x^n =\prod_{k=1}^{\infty}\frac{1}{1-x^k} =\prod_{k=1}^{\infty}\sum_{j=0}^{\infty} x^{jk} $.

Whenever the sum of the terms $jk$ is $n$, that contributes to $p(n)$. So, whenever $n =a_1+2a_2+3a_3+4a_4+... $, where the term $a_i$ comes from the sum for $\frac1{1-x^i}$, that will contribute to $p(n)$. If you consider all possible sums of that form that total $n$, you get the total number of partitions.

Look at Hardy and Wright, or Andrew's book on partitions, or Generatingfunctionology, or ..., and you will see this formula explained more clearly than I have done here.