Proving there are an infinite number of pairs of positive integers $(m,n)$ such that $\frac{m+1}{n}+\frac{n+1}{m}$ is a positive integer

The question is:

Show that there are an infinite number of pairs $(m,n): m, n \in \mathbb{Z}^{+}$, such that: $$\frac{m+1}{n}+\frac{n+1}{m} \in \mathbb{Z}^{+}$$

I started off approaching this problem by examining the fact that whenever the expression was a positive integer, the following must be true:

$$\frac{m+1}{n}+\frac{n+1}{m} - \left\lfloor\frac{m+1}{n}+\frac{n+1}{m}\right\rfloor = 0$$

However, I was unable to do much more with this expression, so I abandoned it and started the problem again from a different angle.

Next I re-arranged the expression to state that:

$$\frac{m^2+m+n^2+n}{mn} \in \mathbb{Z}^{+} \implies \frac{m(m+1) + n(n+1)}{mn} \in \mathbb{Z}^{+}$$

And therefore:

$$mn \mid (m(m+1) + n(n+1))$$

However, I'm unsure how to demonstrate there are infinitely many occurances of $(m, n)$ for which this is true. So I'd appreciate any help.

Thanks in advance

Define the Fibonacci sequence in the usual way: $F_0=0$, $F_1=1$, $F_{k+2}=F_{k+1}+F_k$ for $k\ge0$. It is easy to prove by induction that for all indices $k$ we have $$ F_{k+1}^2-F_{k+1}F_k-F_k^2=(-1)^k.\tag{1} $$ Assume that $k$ is odd. Substitute $F_{k+1}=F_{k+2}-F_k$ to equation $(1)$. After expanding it out and combining the terms we get $$ F_{k+2}^2-3F_{k+2}F_k+F_k^2=-1.\tag{2} $$ Let us select $m=F_{k+2}+1$ and $n=F_k+1$. Plugging these into equation $(2)$ gives $$ (m-1)^2-3(m-1)(n-1)+(n-1)^2=-1\Leftrightarrow (m^2+m)+(n^2+n)=3mn, $$ meaning that the choices $m=F_{k+2}+1$, $n=F_k+1$ is a solution to the equation $$ \frac{m+1}n+\frac{n+1}m=3. $$ Obviously the infinitude of the number of solutions follows from this.

How did I come up with this? Crunch out a few thousand test cases by Mathematica. Observe that $3$ occurs as the sum often. Solve for $m$ in terms of $n$ from the equation $$ \frac{m+1}n+\frac{n+1}m=3. $$ It turns out that the discriminant of this quadratic equation is $$ 5n^2-10n+1=5(n-1)^2-4. $$ From pleasant pieces of personal history (IMO1981) I knew that this is a perfect square, if $n-1$ is a Fibonacci number of an odd index.

Below is a solution based on the innate (reflection) symmetries of integer points on conics.

Hint $\ \rm\displaystyle\ \frac{m\!+\!1}n + \frac{n\!+\!1}m = 3\iff f(n) :=n^2 - (3m\!-\!1)\, n + m^2\!+\!m = 0,\ \:n,m\ne 0 $

If $\rm\:n\:$ is a root of the quadratic $\rm\,f(n)\,$ then so too is $\rm\,n' = (3m\!-\!1)\!-\!n = 3m\!-\!n\!-\!1,\:$ because the sum of the roots equals minus the linear coefficient $\rm\ n+n' =\ 3m-1\,$ by Vieta.

That there are infinitely many solutions now follows easily by noting that this yields a symmetry map on the solution space that produces "bigger" solutions, so iterating it, starting with the solution $\rm\:(2,3),\:$ yields an unbounded so infinite set of solutions. Indeed, composing the above "other root" reflection $\rm\:(n,m)\to (n',m)\:$ with $\rm(x,y)\to (y,x)\:$ yields $\rm\:(n,m)\to (m,n')\:,$ which is "bigger" by $\rm\, m > n \ge 1\Rightarrow n'>m\:$ by $\rm\:n' = 3m\!-\!n\!-\!1 = m\!-\!n + m\!-\!1 + m\, >\, m\ \ $ QED

This yields $\rm\:(n,m) = (2,3),\, (3,6),\,(6,14),\,(14,35),\,(35,90),\,\ldots,\,(f_{\,2k+1}\!+1,f_{\,2k+3}\!+1),\,\ldots\:$ comprised of odd-index Fibonacci numbers plus one (same as discovered by Jyrki by means of a completely different approach). Indeed, we have

$$\begin{eqnarray}\rm \rm (n,\,m) &\to&\rm\ (m,\ 3m-n-1)\, =\, (m,n')\quad \\ \rm i.e. \ \ \ (1+f_{\,k},\,1+f_{\,k+2}) &\to&\rm\ (1+f_{\,k+2},\,1+f_{\,k+4}) \end{eqnarray}$$

because $\rm\ 1+f_{\,k+4} = 3(1+f_{\,k+2}) - (1+f_{\,k}) - 1 = 3m-n-1 = n'\:$ as is easily checked.

Remark $ $ Note that the above approach does not require any knowledge about Fibonacci numbers (or any other specialized knowledge). Instead, everything follows from the simple and ubiquitous fact that reflecting to the "other root" (called "Vieta jumping" by some), combined with the obvious reflection $\rm\:(x,y)\to (y,x)\:$ from the equation being symmetric, yields a group of symmetries on the solution space, one which allows us to generate an unbounded (so infinite) set of solutions.

These and related results have beautiful geometric interpretations via addition laws (and symmetry groups) of conics - a poor man's view of the beautiful group law on elliptic curves. Also there are close connections to simple special cases of Pell's equation and related results (see here for further discussion and literature references). But one need not know such advanced techniques to comprehend and admire the beauty of said symmetry-inspired techniques.

Here is a more inspired solution.

I will prove a stronger claim - that $$\frac{m+1}{n}+\frac{n+1}{m}=3$$ has infinitely many solutions in positive integers.

Setting $$m=2d(d+a), n=2d(d-a)$$ We have $$\frac{m+1}{n}+\frac{n+1}{m}=\frac{2d^2+2a^2+1}{d^2-a^2}$$

So for $\frac{m+1}{n}+\frac{n+1}{m}=3$ to hold, we only need $d^2-5a^2=1$.

There are infinitely many $(d,a)$ that satisfies this equation by a simple Pell-Fermat Equation.

Indeed, take positive integers $d,a$ so that $d+a\sqrt{5}=(9+4\sqrt{5})^k$ for a $k \in \mathbb{N}$.

Then, we have $d^2-5a^2=(d+a\sqrt{5})(d-a\sqrt{5})=(9+4\sqrt{5})^k(9-4\sqrt{5})^k=1$, as desired.

Never noticed this one. The viewpoint from Hurwitz (1907) is that there are solutions only if there are "fundamental" solutions. In this case, that would be integer points $(x,y),$ both positive, with $$ x^2 - kxy+y^2 + x + y = 0, $$ $$ y \geq \frac{2x+1}{k}, $$ $$ x \geq \frac{2y+1}{k}. $$ I will include some pictures. This is possible only if $$ \frac{2k+4 + \sqrt{4k^3+8k^2}}{2k^2-8} \geq 1 \; . $$

So, actually $$ k = 3,4. $$ As indicated in answers and comments, for $k=3$ we get consecutive terms in the sequence $$ x_{j+2} = 3 x_{j+1} - x_j - 1, $$ beginning $$ 2, 2, 3, 6, 14, 35, 90, 234, 611, 1598, \cdots $$

For $k=4$ we get consecutive terms in the sequence $$ x_{j+2} = 4 x_{j+1} - x_j - 1, $$ beginning $$ 1, 1, 2, 6, 21, 77, 286, 1066, \cdots $$

3       2.341640786499874
4       1.316496580927726
5       0.9632741216820454
6       0.7803300858899106
7       0.6666666666666666
8       0.5883036880224507
9       0.5305145858856961

  4            1      1
  4            2      1
  3            2      2
  3            3      2
  4            6      2
  3            6      3
  3           14      6
  4           21      6
  3           35     14
  4           77     21
  3           90     35
  3          234     90
  4          286     77
  3          611    234
  4         1066    286
  3         1598    611
  4         3977   1066
  3         4182   1598
  3        10947   4182
  4        14841   3977
  3        28658  10947