International Mathematics Competition
for University Students
2016

IMC2016: Day 2, Problem 9

9. 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

Hint: Induction on $k$.

  Solution