Prove that there are infinitely many $m,n$ for which $\frac{m+1}{n}+\frac{n+1}{m}$ is an integer

$\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.

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.