Solution:
Observe that
$$\operatorname{gcd}(m+j, n+j)=\operatorname{gcd}(m+j,|m-n|)$$
for $j=0,1,2$. Hence we can find positive integers $a, b, c$ such that
$$\operatorname{gcd}(m, n)=\frac{|m-n|}{a}, \quad \operatorname{gcd}(m+1, n+1)=\frac{|m-n|}{b}, \quad \operatorname{gcd}(m+2, n+2)=\frac{|m-n|}{c}$$
It follows that $|m-n|$ divides $m a,(m+1) b$ and $(m+2) c$. Hence we can see that $|m-n|$ divides $a b$ and $b c$. We get $|m-n| \leq a b$ and $|m-n| \leq b c$. This leads to
$$b \geq \frac{|m-n|}{a}, \quad b \geq \frac{|m-n|}{c}$$
Thus
$$\begin{aligned} \operatorname{gcd}(m, n)+\operatorname{gcd}(m+1, n+1)+\operatorname{gcd}(m+2, & n+2) \\ & =\frac{|m-n|}{a}+\frac{|m-n|}{b}+\frac{|m-n|}{c} \leq 2 b+\frac{|m-n|}{b} \end{aligned}$$
We have to prove that
$$2 b+\frac{|m-n|}{b} \leq 2|m-n|+1$$
Taking $|m-n|=K$, we have to show that $2 b^{2}+K \leq b(2 K+1)$. This reduces to $(b-K)(2 b-1) \leq 0$. However
$$K=|m-n| \geq b \geq 1>\frac{1}{2}$$
Equality holds only when $(m, n)=(k, k+1)$ or $(2 k, 2 k+2)$ or permutations of these for some $k$.