# An Inequality in Integers III

### Solution 1

$i,j\geq 2\Rightarrow (i-1)(j-1)\geq 1\Rightarrow ij-i-j\geq 0,\,$ or $ij\geq i+j\gt i+j-1.$

\displaystyle \begin{align} \sum_{i,j=1}^n \frac{i^2j^2}{i+j-1}&=\frac{1^2\cdot 2^2}{1+1-1}+\frac{1^2\cdot 2^2}{1+2-1}+\frac{2^2\cdot 1^2}{2+1-1}+\sum_{i,j=2}^n \frac{i^2j^2}{i+j-1}\\ &\geq 1+2+2+\sum_{i,j=2}^n \frac{i^2j^2}{ij}\gt \sum_{i,j=2}^n ij \underbrace{\gt}_{(1)}\Biggl(\sum_{i=1}^n i\Biggl)^2\\ &=\Biggl(\frac{n(n+1)}{2}\Biggl)^2\\ &=\Biggl(\frac{n^2+n}{2}\Biggl)^2\;\underbrace{\geq}_{AM-GM}\Biggl(\frac{2\sqrt{n^3}}{2}\Biggl)^2=n^3 \end{align}

We prove (1) by induction.

\displaystyle\begin{align} P(n):&\;\sum_{i,j=2}^n ij\gt \Biggl(\sum_{i=1}^n i\Biggl)^2\\ P(n+1):&\;\sum_{i,j=2}^{n+1} ij\gt \Biggl(\sum_{i=1}^{n+1} i\Biggl)^2\\ \sum_{i,j=2}^{n+1}ij&=\sum_{i,j=2}^n ij+2(n+1)\sum_{i=2}^{n+1}i+(n+1)^2\\ &\gt\Biggl(\sum_{i=1}^n i\Biggl)^2+2(n+1)\sum_{i=1}^n i+(n+1)^2\\ &=\Biggl(\sum_{i=1}^{n+1} i\Biggl)^2. \end{align}

### Solution 2

\displaystyle \begin{align} \sum_{i,j=1}^n\frac{i^2j^2}{i+j-1} &\ge\frac{\displaystyle \left(\sum_{i,j=1}^nij\right)^2}{\displaystyle\sum_{i,j=1}^n(i+j-1)}=\frac{\displaystyle \left(\sum_{i=1}^ni\right)^2}{\displaystyle n\sum_{i=1}^ni+n\sum_{j=1}^nj-n^2}\\ &=\frac{\displaystyle \frac{n^4(n+1)^4}{16}}{\displaystyle n^2(n+1)-n^2}=\frac{n(n+1)^4}{16}. \end{align}

Thus, suffice it to show that $(n+1)^4\ge 16n^2,\,$ i.e., $(n+1)^2\ge 4n\,$ which is $(n-1)^2\ge 0.$

### Solution 3

Let $\displaystyle I_{i,j}=\frac{i^2 j^2}{i+j-1}.\,$ $\displaystyle S_n=\sum_{i,j=1}^nI_{i,j}.\,$ We know that for $n\geq 2$,

\displaystyle\begin{align} S_n&\geq I_{n-1,n}+I_{n,n-1}+I_{n,n}\\ &=\frac{n^4}{2 n-1}+\frac{2 (n-1)^2 n^2}{2 n-2}\geq n^3. \end{align}

For $n=1$, the answer is immediate.

Example: we take the lower corner values $\{n,n\}$, $\{n,n-1\}$, and $\{n-1,n\}$, e.g. $\displaystyle \frac{1296}{11}+90+90$ in the matrix below:

$\displaystyle \left( \begin{array}{cccccc} 1 & 2 & 3 & 4 & 5 & 6 \\ 2 & \frac{16}{3} & 9 & \frac{64}{5} & \frac{50}{3} & \frac{144}{7} \\ 3 & 9 & \frac{81}{5} & 24 & \frac{225}{7} & \frac{81}{2} \\ 4 & \frac{64}{5} & 24 & \frac{256}{7} & 50 & 64 \\ 5 & \frac{50}{3} & \frac{225}{7} & 50 & \frac{625}{9} & 90 \\ 6 & \frac{144}{7} & \frac{81}{2} & 64 & 90 & \frac{1296}{11} \\ \end{array} \right)$

### Extra

As Solution 2 suggests, the problem can be generalized in many ways, e.g.,

Prove that if $a_i\ge 1,\,$ $i=1,\ldots,n\,$ and $\displaystyle \sum_{i=1}^na_i=n^2,\,$ then:

$\displaystyle\sum_{i,j=1}^n \frac{a_i^2a_j^2}{a_i+a_j-1}\ge \frac{n^2}{2n-1}.$

Or

Prove that if $a_i\ge 1,\,$ $i=1,\ldots,n\,$ and $\displaystyle \sum_{i=1}^na_i=\frac{n(n+1)}{2},\,$ then:

$\displaystyle\sum_{i,j=1}^n \frac{a_i^2a_j^2}{a_i+a_j-1}\ge n^3.$

### Soluition 4

Since, for all $i=1,\ldots,n,\,$ $a_i\ge 1,\,$ $(a_i-1)(a_j-1)\ge 0,\,$ implying $a_ia_j\ge a_i+a_j-1,\,$ such that $\displaystyle \frac{a_ja_j}{a_i+a_j-1}\ge 1\,$ and, subsequently, $\displaystyle \frac{a_j^2a_j^2}{a_i+a_j-1}\ge a_ia_j.\,$ It follows that

\displaystyle \begin{align} \sum_{i,j=1}^n\frac{a_i^2+a_j^2}{a_i+a_j-1} &\ge\sum_{i,j=1}^na_ia_j=\left(\sum_{i=1}^na_i\right)^2\\ &=\frac{n^2(n+1)^2}{4}=\frac{n^2(n-1)^2+n^2\cdot 4n}{4} \ge n^3. \end{align}

### Acknowledgment

The problem, along with the solution (Solution 1), was kindly mailed to me by Dan Sitaru on a LaTeX file. The problem has been originally proposed at the Romanian Mathematical Magazine. Solution 2 is by Leo Giugiuc; Solution 3 is by N. N. Taleb.

Marian Cucoaneş has noticed that the original extra 1 was trivial and gave a solution to the Extra 2. It may be considered as Solution 4 for the original problem.