# 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.

• That last display should be $mn\mid(m(m+1)+n(n+1))$. – Gerry Myerson May 30 '12 at 12:42
• So it should, apologies and thanks for pointing it out. – Thomas Russell May 30 '12 at 12:43
• This looks interesting: checking a few low numbers I haven't yet found even one single example of such a pair $\,(m,n)\,$! Could anyone post at least 2-3 example of such pairs? – DonAntonio May 30 '12 at 13:05
• @DonAntonio $(1,1)$, $(2,2)$ – Simon Markett May 30 '12 at 13:08
• So far I've shown it's also true for $(2, 2)$, $(2, 3)$ – Thomas Russell May 30 '12 at 13:09

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.

• Thank you very much for your answer; especially the addendum explaining how you came to this conclusion. Extremely helpful! – Thomas Russell May 30 '12 at 13:24
• But can we find ALL the pairs $(m,n)$? – Jyrki Lahtonen May 30 '12 at 13:28
• Let's see if I understood: we have the seq. $\,0,1,1,2,3,5,8,13,21,34,...\,$ , and let us take say $\,k=4\,\Longrightarrow F_{4+2}+1=F_6+1=8+1=9\,\,,\,F_4+1=3+1=4$ , so we'd get a sol. with $\,m=9\,,\,n=4$...but we don't: $$\frac{9+1}{4}+\frac{4+1}{9}=\frac{5}{2}+\frac{5}{9}\neq \mathbb{N}$$ so what am I misinterpreting? – DonAntonio May 30 '12 at 13:31
• @DonAntonio the index of the fibonacci number, $k$, must be odd for this to work, but as there are an infinite number of odd indices, and thus an infinite number of odd-indexed fibonacci terms, there are infinitely many pairs of positive integers $(m, n)$ – Thomas Russell May 30 '12 at 13:47
• @Inceptio: Most certainly not! That came from the old IMO problem. While working on that (solutions of the equation $(x^2-xy-y^2)^2=1$) I spent about an hour looking for solutions $(x,y)$ using the quadratic formula, and checking when it spews out integers. I stared and stared long and hard at the solutions I did find. I started noticing patterns, and then, finally, a bell was ringing. These are all in the Fibonacci sequence! After that it was more or less plain sailing. This time it was way faster, because I had learned something... – Jyrki Lahtonen Jun 19 '13 at 7:19

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

Notice if $$\rm\:n\:$$ is a root of $$\rm\ n^2 - (3m\!-\!1)\, n + m^2\!+\!m\:$$ then so too is $$\rm\,n' = (3m\!-\!1)\!-\!n = 3m\!-\!n\!-\!1,\:$$ since the sum of the roots equals minus the linear coefficient $$\rm\ n+n' =\ 3m-1.$$

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" since $$\rm\: m > n \ge 1\:\Rightarrow\: n'>m\:$$ by $$\rm\:n' = 3m\!-\!n\!-\!1 = m\!-\!n\, +\, m\!-\!1\, +\, m\, >\, m\quad$$ 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, 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 lterature referneces). But one need not know such advanced techniques to comprehend and admire the beauty of said symmetry-inspired techniques.

• +1 Bill's observations might lead to a complete solution of this problem! The pairs $(m,n)\in\{(1,2),(2,6),(6,21),(21,77),(77,286),\ldots\}$ all give $4$. Using Bill's method we get a recurrence relation $(m',n')=(n,4n-1-m)$ for this family of solutions. Are there others? – Jyrki Lahtonen May 30 '12 at 17:09
• @JyrkiLahtonen: Indeed. This is the sequence A101879 on OEIS. – Théophile May 30 '12 at 17:37

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