IMC 2016 · Day 2 · P9

We prove by induction on $k$. If $k = 1$ then we have $f(n) = 2n + 1$ and the statement immediately follows from the AM-GM inequality.

Assume that $k \ge 2$ and the statement is true for $k - 1$. Let $g(m)$ be the number of integer solutions of $|x_1| + \dots + |x_{k-1}| \le m$; by the induction hypothesis $g(m-1) g(m+1) \le g(m)^2$ holds; this can be transformed to $$\frac{g(0)}{g(1)} \le \frac{g(1)}{g(2)} \le \frac{g(2)}{g(3)} \le \dots.$$ For any integer constant $c$, the inequality $|x_1| + \dots + |x_{k-1}| + |c| \le n$ has $g\bigl( n - |c| \bigr)$ integer solutions. Therefore, we have the recurrence relation $$f(n) = \sum_{c=-n}^{n} g\bigl( n - |c| \bigr) = g(n) + 2 g(n-1) + \dots + 2 g(0).$$ It follows that $$\begin{align*} \frac{f(n-1)}{f(n)} &= \frac{g(n-1) + 2 g(n-2) + \dots + 2 g(0)} {g(n) + 2 g(n-1) + \dots + 2 g(1) + 2 g(0)} \le \\ &\le \frac{g(n) + g(n-1) + (g(n-1) + \dots + 2 g(0) + 2 \cdot 0)} {g(n+1) + g(n) + (g(n) + \dots + 2 g(1) + 2 g(0))} = \frac{f(n)}{f(n+1)} \end{align*}$$ as required.

We first compute the generating function for $f(n)$: $$\sum_{n=0}^{\infty} f(n) q^n = \sum_{(x_1, x_2, \dots, x_k) \in \mathbb{Z}^k} \sum_{c=0}^{\infty} q^{|x_1| + |x_2| + \dots + |x_k| + c} = \left( \sum_{x \in \mathbb{Z}} q^{|x|} \right)^k \frac{1}{1-q} = \frac{(1+q)^k}{(1-q)^{k+1}}.$$ For each $a = 0, 1, \dots$ denote by $g_a(n)$ ($n = 0, 1, 2, \dots$) the coefficients in the following expansion: $$\frac{(1+q)^a}{(1-q)^{k+1}} = \sum_{n=0}^{\infty} g_a(n) q^n.$$ So it is clear that $g_{a+1}(n) = g_a(n) + g_a(n-1)$ ($n \ge 1$), $g_a(0) = 1$. Call a sequence of positive numbers $g(0)$, $g(1)$, $g(2)$, … good if $\frac{g(n-1)}{g(n)}$ ($n = 1, 2, \dots$) is an increasing sequence. It is straightforward to check that $g_0$ is good: $$g_0(n) = \binom{k+n}{k}, \qquad \frac{g_0(n-1)}{g_0(n)} = \frac{n}{k+n}.$$ If $g$ is a good sequence then a new sequence $g'$ defined by $g'(0) = g(0)$, $g'(n) = g(n) + g(n-1)$ ($n \ge 1$) is also good: $$\frac{g'(n-1)}{g'(n)} = \frac{g(n-1) + g(n-2)}{g(n) + g(n-1)} = \frac{1 + \frac{g(n-2)}{g(n-1)}}{1 + \frac{g(n)}{g(n-1)}},$$ where define $g(-1) = 0$. Thus we see that each of the sequences $g_1$, $g_2$, …, $g_k = f$ are good. So the desired inequality holds.