Remember that $\text{lcm}(x,y)=\displaystyle\frac{x\cdot y}{\gcd(x,y)}$ so we have
\[A(m,n):=\text{lcm}(m,n)+\text{lcm}(m+1,n+1) = \frac{m\cdot n}{\gcd(m,n)}+\frac{(m+1)\cdot (n+1)}{\gcd(m+1,n+1)}\]
and then clearly
\[A(m,n) > \frac{m\cdot n}{\gcd(m,n)}+\frac{m\cdot n}{\gcd(m+1,n+1)} = m\cdot n \cdot \left( \tfrac{1}{\gcd(m,n)}+\tfrac{1}{\gcd(m+1,n+1)} \right)\]
Now let us use the AM-GM inequality ( $x+y \geq 2\sqrt{x\cdot y}$ for $x,y\geq 0$) to get
\[\frac{1}{\gcd(m,n)}+\frac{1}{\gcd(m+1,n+1)} \geq \frac{2}{\sqrt{\gcd(m,n)\cdot \gcd(m+1,n+1)}}\]
Next note that if we get $\gcd(m,n)\cdot \gcd(m+1,n+1) \leq m-n$, we are done.
To prove it, note that $d_1 = \gcd(m,n) = \gcd(n,m-n)$ which divides $m-n$, and $d_2=\gcd(m+1,n+1)=\gcd(n+1,m-n)$ which also divides $m-n$. But $d_1$ divides $n$ and $d_2$ divides $n+1$ ... and $\gcd(n,n+1)=1$ :p so in fact $\gcd(d_1,d_2)=1$ !.
Hence $d_1\cdot d_2$ must divide $m-n$, and so $d_1\cdot d_2 \leq m - n$ completing the proof $\square$.
