An integer partition, is a way of writing n as a sum of positive integers. Two sums that differ only in the order of their summands are considered the same partition. Quote: For example, 4 can be partitioned in five distinct ways: 4 3 + 1 2 + 2 2 + 1 + 1 1 + 1 + 1 + 1 The number of partitions of n is given by the partition function $p\left ( n \right )$. So $p\left ( 4 \right ) = 5$ . Determine all the positive integers so that $p\left ( n \right )+p\left ( n+4 \right )=p\left ( n+2 \right )+p\left ( n+3 \right )$.
Problem
Source: 2018 China Team Selection Test 2 Problem 2
Tags: function, Integer partitions, number theory, combinatorics
12.01.2018 17:04
Solution with Brice Huang, Kevin Sun, and Ashwin Sah: The answers are $n = 1, 3, 5$. We instead show that $N = 5, 7, 9$ are the only solutions to \[ p(N) + p(N-4) = p(N-1) + p(N-2). \](which is equivalent via $N = n+4$). Terminology A partition of $n$ is called coarse if all the parts are at least three. It is nontrivial if it has more than one part. Let $q(n)$ denote the number of coarse partitions of $n$. Given a coarse partition $\pi$, we let $t(\pi)$ denote the number of distinct odd parts it has. We say a coarse partition $\pi$ is even if $t(\pi) = 0$ (meaning all parts of $\pi$ are even), and odd otherwise.
Reduction to coarse partitions The motivation for defining $q(n)$ comes from the following generating functions computation. Claim: For all $N \ge 5$, \begin{align*} &\quad P(N) + P(N-4) - P(N-1) - P(N-2) \\ &= Q(N) - Q(N-3) - Q(N-5) - Q(N-7) - Q(N-9) - \dots. \end{align*} Proof. This proof is by generating functions. First, write: \begin{align*} \frac{1-X-X^2+X^4}{(1-X)(1-X^2)(1-X^3)\dots} &= \frac{\frac{1-X-X^2+X^4}{(1-X)(1-X^2)}} {(1-X^3)(1-X^4)(1-X^5)\dots} \\ &= \frac{\frac{1-X^2-X^3}{1-X^2}} {(1-X^3)(1-X^4)(1-X^5)\dots} \\ &= \frac{1-\frac{X^3}{1-X^2}} {(1-X^3)(1-X^4)(1-X^5)\dots} \\ &= \frac{1-X^3-X^5-X^7-X^9-\dots} {(1-X^3)(1-X^4)(1-X^5)\dots}. \end{align*}Since $\prod_{k \ge 1} (1-X^k)^{-1} = \sum_N p(N) X^N$, and $\prod_{k \ge 3} (1-X^k)^{-1} = \sum_N q(N) X^N$, this implies the desired result. $\blacksquare$ Estimates First, we completely resolve the case when $N$ is odd. Claim: For all odd $N \ge 5$, \[ q(N) \le q(N-3) + q(N-5) + q(N-7) + \dots \]with equality if and only if $N=5$, $N=7$, $N=9$. Proof. The main observation is that $q(N-3)$ counts the number of coarse partitions of $N$ containing at least one $3$, et cetera. As $N$ is odd, $t(\pi) \ge 1$ for all coarse partitions $\pi$ of $N$. Then we have \[ q(N) = \sum_\pi 1 \le \sum_\pi t(\pi) = q(N-3) + q(N-5) + \dots \]where the sum is over coarse partitions of $N$ as desired. Equality holds if and only if $t(\pi)=1$ for every $\pi$. This occurs when $N=5,7,9$ but not for $N \ge 11$ in light of the coarse partition $3+5+(N-8)$. $\blacksquare$ The even case will require some more care. Claim: For $N \in \{6,8,10,12\}$ we have \[ q(N) - 1 = q(N-3) + q(N-5) + q(N-7) + \dots \]and for all even $N \ge 14$ we have \[ q(N) < q(N-3) + q(N-5) + q(N-7) + \dots. \] Proof. The proof is similar to before, but this time we must take care of even partitions. Consider the following operation $f$: given an even coarse partition $\pi = a_1 + a_2 + \dots + a_k$ with $k \ge 2$ (here $4 \le a_1 \le \dots \le a_k$), we consider the partition \[ f(\pi) = (a_1-1) + a_2 + \dots + (a_k+1). \]This is an odd coarse partition with $t(f(\pi)) = 2$. Observe that $f$ is injective, and let $S$ denote its image. Thus \begin{align*} q(N) &= 1 + \sum_{\text{odd } \pi} 1 + \sum_{\text{even nontriv } \pi} 1 = 1 + \sum_{\text{odd } \pi} 1 + \sum_{\text{odd } \pi \in S} 1 \\ &= 1 + \sum_{\text{odd } \pi \notin S} 1 + \sum_{\text{odd } \pi \in S} 2 \\ &\le 1 + \sum_{\text{odd } \pi \notin S} t(\pi) + \sum_{\text{odd } \pi \in S} t(\pi) = 1 + \sum_{\text{odd } \pi} t(\pi) \\ &= 1 + q(N-3) + q(N-5) + \dots. \end{align*}One can then observe that for $N \in \{6,8,10,12\}$, all the estimates are sharp, in the sense that $t(\pi) \le 2$ with equality when $\pi \in S$ for odd coarse partitions of $N$. As for $N \ge 14$, notice that $\pi_1 = 3+3+3+(N-9)$ and $\pi_2 = 3+5+(N-8)$ are two partitions of $N$ with $t(\pi_1) = t(\pi_2) = 2$ but which are not in $S$, thus giving us $q(N) \le -2 + (1+q(N-3)+\dots)$ as claimed. $\blacksquare$
10.02.2018 10:52
A purely combinatorial argument. Let $f(n, k)$ denote the partitions of $n$ such that each part is at least $k$. Note that $f(n, k) = f(n, k + 1) + f(n - k, k)$ for all $n, k$. Note that $f(n, 1) - f(n - 1, 1) = f(n, 2)$, so we can write the equation $p(n) + p(n + 4) = p(n + 2) + p(n + 3)$ as $f(n + 4, 2) = f(n + 2, 2) + f(n + 1, 2)$. $f(n + 4, 2) = f(n + 2, 2) + f(n + 4, 3) = f(n + 2, 2) + f(n + 1, 3) + f(n + 4, 4) = f(n + 2, 2) + f(n + 1, 2) - f(n - 1, 2) + f(n + 4, 4)$, so we want $f(n - 1, 2) = f(n + 4, 4)$. Let $N = n + 4$ for convenience and thus we now require $f(N, 4) = f(N - 5, 2)$ where $N \ge 5$. We claim that $N = 5, 7, 9$ are the only solutions. We can check all cases $N \le 14$ manually so we assume $N \ge 15$. We will prove that $f(N, 4) < f(N - 5, 2)$ for $N \ge 15$. We will map each partition on the left side to a partition to the right side such that no two partitions are mapped to the same partition on the right side and there exist at least one partition on the right side that has not been mapped. For a partition of length $\ge 3$ with each element $\ge 4$ of $N$, $(a_{1}, a_{2}, ..., a_{k})$, where $a_{i} \ge a_{j}$ when $i \le j$, we map it to $(a_{1} - 2, a_{2} - 2, a_{3} - 1, a_{4}, ..., a_{k})$. Verify that no two such partitions are mapped to the same partition. (In fact, we can get the first partition from the second by sorting the elements of the second in non-decreasing order and add $2$ to the first two elements and add $1$ to the third element). For the partition of length $1$ of $N$, map it to the partition of length $1$ of $N - 5$. For the partitions of length $2$ of $N$, $(x, N - x)$ with $x \le N - x$ and $x \ge 5$, map it to $(x - 3, N - x - 2)$. Finally, only $(4, N - 4)$ has been left unmapped. We claim that there are at least two partitions on the right side that has not been mapped by any element on the left side, which completes the proof. Consider the partitions $(2, 2, 2, N - 11)$ and $(2, 2, 2, 2, N - 13)$ (both are valid since $N \ge 15$). If one of them is mapped from some partition from the left side, it must come from the first case. However, $a_{1} - 2 \le a_{2} - 2 < a_{3} - 1 < a_{4} \le a_{5} ... \le a_{k}$, so we cannot have the smallest three elements equal, a contradiction. Thus, $n = 1, 3, 5$ are the only solutions. Edit : Made a mistake in bounds of $N$.