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
Best Answer
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.