Mongolian National Mathematical Olympiad

Let $X_n := \{(x, y, z) \in \mathbb{Z}^3 \mid 0 \le x \le y \le z \le x+y \text{ and } x+y+z=n\}$. Then $c_n = |X_n|$. Let $Y_n := \{(p, q, r) \in \mathbb{Z}^3 \mid 0 \le p, q, r \text{ and } 2p+3q+4r=n\}$ and define the maps $f: X_n \to Y_n$ by
$$f(x, y, z) := (y - x, x + y - z, z - y)$$
and $g: Y_n \to X_n$ by
$$g(p, q, r) := (q + r, p + q + r, p + q + 2r).$$
Then $f$ and $g$ are inverse to each other, and therefore $c_n = |Y_n|$, i.e. $c_n$ is the number of ways in which $n$ can be expressed as a sum of 2, 3 and 4. Thus
$$n \cdot c_n = \sum_{(p,q,r) \in Y_n} 2p + 3q + 4r.$$
For $m \ge 0$, the number of elements of $Y_n$ such that $p \ge m$ is $c_{n-2m}$. So there are exactly $c_{n-2m} - c_{n-2(m+1)}$ elements with $p=m$. Here we mean $c_k = 0$ if $k < 0$. Thus 2 is added $\sum_{m \ge 1} c_{n-2m}$ times in the sum above. Similarly, we can compute the coefficient of 3 and 4 and hence
$$\begin{aligned} n \cdot c_n &= \sum_{k=2}^{4} \sum_{m=1}^{[n/k]} k c_{n-km} \\ &= \sum_{j=2}^{n} \left( \sum_{\substack{2 \le k \le 4 \\ k \mid j}} k \right) c_{n-j} \le 9 \sum_{m=0}^{n-2} c_m. \end{aligned}$$