| |||||||||
IMC2016: Day 2, Problem 99. Let $k$ be a positive integer. For each nonnegative integer $n$, let $f(n)$ be the number of solutions $(x_1,\ldots,x_k)\in\mathbb{Z}^k$ of the inequality $|x_1|+...+|x_k|\leq n$. Prove that for every $n\ge1$, we have $f(n-1)f(n+1)\leq f(n)^2$. Proposed by Esteban Arreaga, Renan Finder and José Madrid, IMPA, Rio de Janeiro Solution 1. 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|+...+|x_{k-1}|\leq m$; by the induction hypothesis $g(m-1)g(m+1)\leq g(m)^2$ holds; this can be transformed to $$ \frac{g(0)}{g(1)}\leq\frac{g(1)}{g(2)}\leq\frac{g(2)}{g(3)}\leq\ldots. $$ For any integer constant $c$, the inequality $|x_1|+...+|x_{k-1}|+|c|\leq n$ has $g\big(n-|c|\big)$ integer solutions. Therefore, we have the recurrence relation $$ f(n) = \sum_{c=-n}^n g\big(n-|c|\big) = g(n)+2g(n-1)+...+2g(0). $$ It follows that $$ \frac{f(n-1)}{f(n)} = \frac{g(n-1)+2g(n-2)+...+2g(0)}{g(n)+2g(n-1)+...+2g(1)+2g(0)} \leq $$ $$ \leq \frac{g(n)+g(n-1)+(g(n-1)+...+2g(0)+2\cdot0)}{ g(n+1)+g(n)+(g(n)+...+2g(1)+2g(0))} = \frac{f(n)}{f(n+1)} $$ as required. Solution 2. We first compute the generating function for $f(n)$: \[ \sum_{n=0}^\infty f(n) q^n \;= \sum_{(x_1,x_2,\ldots,x_k)\in\mathbb{Z}^k} \sum_{c=0}^\infty q^{|x_1| + |x_2| + \cdots + |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,\ldots$ denote by $g_a(n)$ ($n=0,1,2,\ldots$) 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\geq 1$), $g_a(0)=1$. Call a sequence of positive numbers $g(0)$, $g(1)$, $g(2)$, \ldots \emph{good} if $\frac{g(n-1)}{g(n)}$ ($n=1,2,\ldots$) is an increasing sequence. It is straightforward to check that $g_0$ is good: \[ g_0(n) = \binom{k+n}{k},\quad \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\geq 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$, \ldots, $g_k=f$ are good. So the desired inequality holds. | |||||||||
© IMC |