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$ 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$ 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$ 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
    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
    Feb 7, 2017 at 6:56
  • $\begingroup$ @james.nixon: Thank you for your generous words. $\endgroup$ Feb 7, 2017 at 13:05

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.