6
$\begingroup$

The $2$-adic valuation of $n\in\mathbb{N}$, denoted $\nu(n)$, is the largest power $t$ such that $2^t$ divides $n$. The number of integer partitions of $n$, denoted by $p(n)$, has generating function $$\sum_{n\geq0}p(n)x^n=\prod_{k\geq1}\frac1{1-x^k}.$$ However, I am finding an alternative: $$\sum_{n\geq0}p(n)x^n=\prod_{k\geq1}(1+x^k)^{\nu(2k)}.$$

Question. Is this known? If so, any reference? If not, then any proof?

Caveat. I would be surprised if this is new.

$\endgroup$

3 Answers 3

4
$\begingroup$

This can be proved from the famous:

Distinct parts <-> Odd parts

which can be found in Hardy & Wright : An Introduction to the Theory of Numbers.

This states:

$$(1+x)(1+x^2)(1+x^3)\dots=\frac1{(1-x)(1-x^3)(1-x^5)\dots}$$

If you substitute $x\to x^{2^k}$ for $k=1,\dots$, and multiply together, the RHS becomes the usual partition generating function, and the LHS takes your alternative form.

$\endgroup$
1
  • $\begingroup$ +1 This is gorgeous. $\endgroup$ Commented Feb 8, 2017 at 21:33
12
$\begingroup$

We have the identity

$$\frac{1}{1 - x^k} = \prod_{i \ge 0} (1 + x^{k \cdot 2^i})$$

which is equivalent to the uniqueness of binary representations, and is also straightforward to prove using a telescoping argument by multiplying both sides by $1 - x^k$. Applying this identity to every term on the RHS of the first identity produces

$$\sum_{n \ge 0} p(n) x^n = \prod_{k \ge 1} \prod_{i \ge 0} (1 + x^{k \cdot 2^i})$$

which rearranges to your identity without much effort. The combinatorial interpretation here involves looking at the binary representation of the multiplicities of each integer in a partition.

$\endgroup$
2
  • $\begingroup$ Hint: his $k$ is different to yours. $\endgroup$ Commented Feb 5, 2017 at 16:05
  • 2
    $\begingroup$ Next hint: the number of solutions to $b\times 2^i=k$ for $b\geq1$ and $i\geq0$ is $\nu(2k)$. $\endgroup$ Commented Feb 5, 2017 at 21:54
2
$\begingroup$

I'm going to give this another go because the method reveals some points of potential interest.

The intent is to prove that $\prod_{k\geq1}\frac1{1-x^k}=\prod_{k\geq1}(1+x^k)^{\nu(2k)}$. Take logarithms on both sides and make use the Taylor series $-\log(1-y)=\sum_{i\geq1}\frac{y^i}i$. The LHS turns into \begin{align} \log\prod_{k\geq1}\frac1{1-x^k}=-\sum_{k\geq1}\log(1-x^k)=\sum_{m,k\geq1}\frac{x^{mk}}k =\sum_{n\geq1}x^n\sum_{d\vert n}\frac1d=\sum_{n\geq1}\frac{x^n}n\sigma(n), \end{align} where $\sigma(n)$ is the sum of divisors function. From $\log(1+y)=-\sum_{i\geq1}(-1)^i\frac{y^i}i$, the RHS converts to \begin{align} \log\prod_{k\geq1}(1+x^k)^{\nu(2k)} &=\sum_{k\geq1}\nu(2k)\cdot\log(1+x^k) =-\sum_{m,k\geq1}\frac{(-1)^mx^{mk}\nu(2k)}m \\ &=-\sum_{n\geq1}x^n\sum_{d\vert n}(-1)^{n/d}\frac{\nu(2d)}{n/d} =-\sum_{n\geq1}\frac{x^n}n\sum_{d\vert n}(-1)^{n/d}d\cdot\nu(2d). \end{align} In other words, we need to prove $$\sigma(n)=-\sum_{d\vert n}(-1)^{n/d}d\cdot\nu(2d).$$ Consider the Dirichlet series $f(s):=-\sum_{a\geq1}\frac{(-1)^a}{a^s}$ and $g(s):=\sum_{b\geq1}\frac{\nu(b)}{b^s}$ to obtain \begin{align} f(s+1)g(s) &=-\sum_{a\geq1}\frac{(-1)^a}{b^{s+1}}\sum_{b\geq1}\frac{b\cdot\nu(b)}{b^{s+1}} =-\sum_{n\geq1}\frac1{n^{s+1}}\sum_{d\vert n}(-1)^{n/d}d\cdot\nu(d). \tag1 \end{align} It's easy to see $f(s+1)=(1-2^{-s})\zeta(s+1), g(s)=\frac{\zeta(s)}{2^s-1}$ and $\zeta(s+1)\zeta(s)=\sum_{n\geq1}\frac{\sigma(n)}{n^{s+1}}$ where $\zeta(s)$ is the Riemann zeta function. Therefore, we have $$f(s+1)g(s)=\frac1{2^s}\sum_{n\geq1}\frac{\sigma(n)}{n^{s+1}} =\sum_{n\geq1}\frac{2\sigma(n)}{(2n)^{s+1}}.\tag2$$ Reading off the coefficients of $\frac1{(2n)^{s+1}}$, from the Dirichlet generating functions in (1) and (2), we get $$2\sigma(n)=-\sum_{d\vert 2n}(-1)^{2n/d}d\cdot\nu(d) =-\sum_{2d'\vert 2n}(-1)^{2n/(2d')}2d'\cdot\nu(2d') \tag3$$ up on using $\nu(odd)=0$. Rewrite equation (3) to obtain the desired result: $$\sigma(n)=-\sum_{d'\vert n}(-1)^{n/d'}d'\cdot\nu(2d').$$

$\endgroup$
3
  • $\begingroup$ OOoOooOOoo Boy! That is SuUuuUuuper slick. I wish I could +10 this. That is a great solution. $\endgroup$
    – user78249
    Commented Feb 7, 2017 at 5:16
  • 2
    $\begingroup$ I'm becoming more and more enthralled by your questions and your solutions @T. Amdeberhan. $\endgroup$
    – user78249
    Commented Feb 7, 2017 at 6:56
  • $\begingroup$ @james.nixon: Thank you for your generous words. $\endgroup$ Commented Feb 7, 2017 at 13:05

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .