3
$\begingroup$

Definition: A tuple $\lambda = (\lambda_1, \ldots, \lambda_k)$ of natural numbers is called a numeric partition of $n$ if $1 \leq \lambda_1 \leq \cdots \leq \lambda_k$ and $\lambda_1 + \cdots + \lambda_k = n$ and is written as $\lambda \vdash n$.

Exercise: Let $p(n)$ be the amount of numeric partitions of $n$. Prove that

i) Let $f_n := \prod_{i=1}^n (1-x^i)^{-1}$. Prove that $(f_n)_{n\geq 0}$ creates a Cauchy sequence in $\mathbb{C}[[x]]$.

ii) Prove that $ \sum\limits_{n \geq 0} p(n) x^n = \lim\limits_{n \rightarrow \infty} f_n = \prod\limits_{i=1}^\infty (1-x^i)^{-1} .$

I tried to play around with the definition of $f_n$ and tried (quite successfully as I hope) to understand what a Cauchy sequence is. But how do I prove that?

What should I do to prove the second one? Any hints?

Thanks in advance!

  • 0
    Okay, that would explain why you're confused. The metric isn't unique, but for example it can be given by $d(a, b) = 2^{-\nu(a-b)}$ where $\nu(a-b)$ is the largest power of $x$ dividing $a-b$. This metric satisfies a very strong form of the triangle inequality (see http://en.wikipedia.org/wiki/Ultrametric_space) and it turns out to be very easy to characterize convergence: a series converges if and only if its terms tend to $0$, and a product converges if and only if its terms are nonzero and tend to $1$.2011-05-29

2 Answers 2

3

First note that $ \frac{1}{1-x^i}=\sum_{j=0}^{\infty}x^{ij}. $ We have $f_{n+1}-f_n$ is divisible by $x^{n+1}$, so we get convergence in $\mathbb{C}[[x]]$ (see http://en.wikipedia.org/wiki/Formal_power_series or something similar, neighborhoods of zero are powers of the ideal $(x)$).

For the connection to the partition function, think about a partition of $n$. choose how many $1$'s will appear, how many $2$'s etc., and pick them out in the product $ (1+x+x^2+ \cdots)(1+x^2+(x^2)^2+\cdots)(1+x^3+(x^3)^2+\cdots) \cdots. $ Pick the number of ones from the $(1+x)^{-1}$ (i.e., if you want three $1$'s in the partition pick $x^3$), pick the number of $2$'s from the $(1+x^2)^{-1}$ (i.e., if you want three $2$'s in the partition pick $(x^2)^3$).

Adding up every way you can do this is exactly the coefficient of $x^n$ in $\lim f_n$ (or $f_N$ for large enough $N$). (If this isnt clear just multiply out the first few coefficients or look up the partition function online and you'll see a better exposition.)

  • 0
    @muffel power series are "smaller" if they are more highly divisible by $x$. the wikipedia page on formal power series gives a few different equivalent ways of talking about the topology2011-05-30
0

The function $f_n$ already has all the correct coefficients up to $p(n)$. Open the expression up (following yoyo's advice) and see if you can figure out why.

Continuing, when you move from $f_n$ to $f_{n+1}$, all the low-order coefficients remain the same, and this is the reason that the infinite product converges - since every particular coefficient is equal to some finite sum (that counts the number of integer partitions of that size).