Prove that there are infinitely many $m,n$ for which $\frac{m+1}{n}+\frac{n+1}{m}$ is an integer Prove that there are infinitely many pairs of positive integers (m,n) such that 
$\frac{m+1}{n}+\frac{n+1}{m}$ 
is a positive integer.
I tried following:
clearly $(1,1)$ satisfies the condition. we assume that $(a,b)$ satisfies the condition. If we can find some $f(a)$ and $f(b)$ that satisfy the condition and they are increasing functions then we are done. But i didn't get such thing.
 A: $\frac{m+1}{n}+\frac{n+1}{m}=k$ is equivalent to $m^2+m+n^2+n=kmn$.  We rewrite as a quadratic in $n$:
$n^2+(1-km)n+(m^2+m)=0$. And because the quadratic is monic, any rational roots will be integers.
Applying the quadratic formula gives $$n=\frac{(km-1)\pm\sqrt{(k^2-4)m^2-(2k+4)m+1}}{2}(*)$$
If we find values of $m$ and $k$ that give a solution, we should get two values of $n$ that work with the given $m$ and $k$.  One value of $n$ will be less than or equal to $m$ (corresponding to the minus in the quadratic formula; and the other will be greater than $m$, corresponding to the plus.  This will allow us to generate sequences of values.
The OP observed that there is a solution to the original problem at $(m,n)=(1,1)$. The corresponding value of $k$ is $4$.  Then $(*)$ becomes $$n=\frac{(4m-1)\pm\sqrt{12m^2-12m+1}}{2}$$ 
Taking $m=1$ and the plus root gives $n=2$.  So $(m,n)=(1,2)$ is a solution.  So is $(2,1)$.
Taking $m=2$ and the plus root gives $n=6$.  So $(2,6)$ and $(6,2)$ are solutions.
Taking $m=6$ and the plus root gives $n=21$.  So $(6,21)$ and $(21,6)$ are solutions.
Continuing we generate the sequence $1, 1, 2, 6, 21, 77,286,1066,3977,14841,\dots$ where consecutive terms are solutions to the original problem.
We can also get a second family of solutions corresponding to $k=3$ (as suggested in Daniel's comment).  Appropriate changes must be made to the quadratic; but the resulting sequence is $2,3,6,14,35,90,234,611,1598,\dots$.
I do not know if there are other families of solutions (corresponding to other values of $k$).
P.S. Credit to Daniel's comment for pointing toward a fruitful direction for this problem.
A: Apply the ideas of Vieta's root jumping to $ \frac{m+1}{n} + \frac{n+1}{m} = k $.
OP found $(1,1)$ as a solution, which give us the equation $ \frac{m+1}{n}+ \frac{n+1}{m} = 4$.
This simplifies to the quadratic $m^2 + (1-4n)m + n^2 + n = 0$.
Divide by $ m \neq 0$ to get: $ m - (4n-1) + \frac{n^2 + n}{m} = 0$.
So, if we have an integer solution $(m, n)$ , then

*

*$ \frac{n^2+n}{m}$ is an integer.

*$m+ \frac{n^2+n}{m} = 4n-1$.

Thus, for a fixed $n$, if $m$ is a solution to $X^2 + ( 1-4n)X + n^2+n = 0$, then so is $ \frac{n^2+n}{m}$.
This allows us to establish the Vieta root jumping: Define a recurrence via $ a_ 1 = 1, a _2 = 1, a_{n+2} = 4a_{n+1} - a_{n} - 1 = \frac{a_{n+1} ^2 + a_{n+1} } { a_n}$, and the above shows that $(a_{n}, a_{n+1})$ satisfies the conditions of the problem.
Observe that if $ a_{n+1} \geq a_{n}  > 0$, then $ a_{n+2} > \frac{a_{n+1}^2}{a_{n} } \geq a_{n+1}$.
Hence, we have a sequence of strictly increasing integers (apart from possibly the initial values), which gives us infinitely many solutions as desired.
Further Notes

*

*With $k=4$, this gives us the $1, 1, 2, 6, 21, \ldots$ solution found by paw.

*With $ k = 3$ (modify the above as needed), this gives us $2, 2, 3, 6, 14, 35, \ldots$ solution found by daniel.

*Furthermore, Vieta tells us that if we have any solution with $ m > n$, we can reverse engineer the sequence [IE Repeatedly apply $(m, n) \rightarrow (n, \frac{n^2+n}{m} )$] to end up with $ m=n$. Then, $ \frac{2(m+1)}{m}  = 2+\frac{2}{m}$ is an integer, which happens iff $ m = 1, 2$ giving us $k=4, 3$ respectively. Hence, we've found all solutions to the condition.

*We could show that $a_i $ was a strictly increasing sequence using just the linear recurrence via $ka_{n+1} - a_n - 1 > a_{n+1}$ for $ k = 4$. With $ k =3$, we have to be slightly careful.

A: Equation:
$$\frac{m+1}{n}+\frac{n+1}{m}=a$$ 
Can be solved using the Pell equation:  $p^2-(a^2-4)s^2=1$ 
Then the solutions are of the form:  
$$n=2(p-(a+2)s)s$$  
$$m=-2(p+(a+2)s)s$$ 
And another solution:  
$$n=\frac{2p(p+(a-2)s)}{a-2}$$  
$$m=\frac{2p(p-(a-2)s)}{a-2}$$
Another possible formula solution to record if the ratio is such that the equation   $p^2-(a^2-4)s^2=4$ and using its solutions. Then the formula is:  
$$n=\frac{p-(a-2)s+2}{2(a-2)}$$  $$m=\frac{p+(a-2)s+2}{2(a-2)}$$
A: Equating the given expression to an integer $k$ and clearing out denominators, we have an equation of the form
$$m^2+m+n^2+n=kmn$$
to solve in positive integers.  Multiplying both sides by $2$ allows us to write this as
$$(m+n)^2+(m-n)^2+2(m+n)=2kmn$$
If we now let $a=m+n$ and $b=m-n$, so that $m=(a+b)/2$ and $n=(a-b)/2$, the equation to solve now becomes
$$a^2+b^2+2a=k{a^2-b^2\over2}$$
which can be rewritten as
$$(k+2)b^2=(k-2)a^2-4a$$
with the understanding that $a$ and $b$ are to have the same parity.
At this point, it becomes extremely convenient to let $k=3$.  (This will lead to a stronger version of the requested result, namely that there are infinitely many $m$ and $n$ for which the sum of $(m+1)/n$ and $(n+1)/m$ equals $3$, and not just some integer.)  If we do, the equation to solve becomes
$$5b^2=a^2-4a$$
Before we go on, note that any $a$ and $b$ that solve this equation necessarily have the same parity, so that we'll be able to extract integer values of $m$ and $n$ from them.  Noting that $a^2-4a=(a-2)^2-4$, let's go ahead and look for even solutions, writing $a-2=2u$ and $b=2v$, so that the equation simplifies to
$$5v^2=u^2-1$$
or
$$u^2-5v^2=1$$
At this point, if you know about Pell's equation, you can pretty much call it a day:  any equation of the form $u^2-dv^2=1$ with non-square $d$ has infinitely many positive integer solutions.  If you don't know the general theory, you can still get what you need by proving it for this specific equation.  You can do that by noting that
$$(9+4\sqrt5)(9-4\sqrt5)=81-16\cdot5=1$$
and therefore
$$(9+4\sqrt5)^n(9-4\sqrt5)^n=1^n=1$$
When you expand $(9+4\sqrt5)^n$ (with my apologies for reusing the symbol $n$), you get an expression of the form $u+v\sqrt5$ with coefficients $u$ and $v$ that grow with the exponent.  There's a straightforward recursion:  if $(u,v)$ is a solution, then $(9u+20v,4u+9v)$ is too, since
$$(9+4\sqrt5)(u+v\sqrt5)=(9u+20v)+(4u+9v)\sqrt5$$
A: The following is basically a rehash of previous solutions, but (for me, anyway) it's a little clearer.

Say a solution $(m,n)$ is "good" if $m$ and $n$ are positive integers and $m<n$.
Claim: if $(m,n)$ is good then so is $\left(n,\tfrac{n(n+1)}{m}\right)$.
Proof: let $k=\tfrac{m+1}{n}+\frac{n+1}{m}\in\mathbb{Z}$, so $m$ is a root of $f(X)=X^2-(kn-1)X+n^2+n$.  The product of the roots is $n^2+n$, so the other root is $m^\prime=\tfrac{n^2+n}{m}>n$.  The sum of the roots is an integer, so $m^\prime$ is too.  $\square$
Noting that $(1,2)$ is good, define: $a_1=1,a_2=2$ and $a_{k+1}=\frac{a_k(a_k+1)}{a_{k-1}}$ for $k\ge 2$.  Then $(a_k)$ is an increasing sequence in which each $(a_k,a_{k+1})$ is a good pair.  We are done.
