-2
$\begingroup$

Consider the number of integer partitions $p(n)$ of $n$ whose generating function is $$\sum_{n\geq0}p(n)\,x^n=\prod_{k\geq1}\frac1{1-x^k}.$$ Also, the number of partitions into distinct parts $Q(n)$ of $n$ whose genertaing function is $$\sum_{n\geq0}Q(n)x^n=\prod_{k\geq1}(1+x^k).$$ Expand the ratio of these two generating functions so that $$\sum_{n\geq0}a(n)x^n=\prod_{k\geq1}\frac{1+x^k}{1-x^k}.$$

QUESTION. Why is $a(n)\equiv 2\,\, (\text{mod}\, 4)$ iff $n$ is a perfect square, for $n\geq1$?

$\endgroup$
1

1 Answer 1

6
$\begingroup$

$$\frac{1+x^k}{1-x^k}=(1+x^k)(1+x^k+x^{2k}+\dots)=1+2x^k+2x^{2k}+\dots$$ Multiplying all these together and looking at terms contributing to the coefficient of $x^n$, we see that the term will be contributing something divisible by $4$ unless it comes from multiplying a bunch of $1$s together with $2x^{k\cdot d}$ for $k\mid n$. This means $a(n)\equiv 2d(n)\pmod 4$, where $d(n)$ is the number of divisors of $n$. Since $d(n)$ is odd iff $n$ is a square, we get the result.

$\endgroup$

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