Show that there are infinitely many integers such that $ \binom{m}{n-1} = \binom{m-1}{n} $

Question

This question comes from the 1st Brazilian's IMO TST of 2004. I have found no solutions of it online, though I have developed one.

After getting to $ mn = (m-n)(m-n+1) $, my solution relies on the claim that $ m_z = F(2z) \cdot F(2z+1) $ and $ n_z = F(2z-1) \cdot F(2z) $ (where $ F(z) $ is the Fibonacci function), which can be easily proved by finite induction.

Another attempt I had finds that $ n = \dfrac{3m+1 \pm \sqrt{5m^2+2m+1}}{2} $, but I couldn't prove that there are infinitely many integers $ m $ such that $ \sqrt{5m^2+2m+1} $ is an integer $ \equiv m+1 \pmod2 $.

Noticing $ 5m^2+2m+1 = (2m)^2 + (m+1)^2 $, I've tried setting a primitive Pythagorean triplet $ x^2-y^2=m+1, \; 2xy=2m $, but couldn't prove $ x^2-xy-y^2=1 $ has infinitely many integer solutions. I know that this is a hyperbola and that Pell can help me a lot here, but I've tried to restrain myself to using what I've learned in high school.

Can someone conclude my second approach or provide me a different~easier one?

Answer 1

The other solutions are good. I would like to point out that getting to $ x^2 - xy - y^2 =1 $ seems almost magical / there were several hoops to jump through (relating to pythagorean, seeing some factorization, etc) . As such, it is unlikely that this is the intended solution. I'm offering an alternative that is easier to motivate, and more likely along the lines of what is expected, because you just "do the next thing".

Let’s look back at the orignial equation, which is $ mn = (m-n) ( m-n+1) $. This is a conic section, in particular a hyperbola, and people are afraid of it because it seems complicated. It is, but only because the axis are not what we are used to.

What is the next thing to do? Since we dislike cross terms, we convert it into a rectilinear system of coordinates (which you should almost always do). In this case, we take the system

$$ a = m+n, b = m- n $$

which will give us $\frac{ a+b}{2} \times \frac{a-b} { 2} = b(b+1)$, or that $a^2 = 5b^2 + 4 b $. It is clear that $m, n$ are integers if and only if $a, b$ to be integers of the same parity. From the equation $a^2 = 5b^2 + 4b \equiv b^2 \pmod{4}$, this is trivially satisfied, so we will ignore the parity condition and proceed to solve for integers.

What is the next thing to do? $a ^2 - 5b^2$ looks very Pellish. How do we transform it and get rid of $4b$? We complete the square creatively.

$$ 5a^2 = 25b^2 + 20 b = (5b + 2)^2 - 4 $$

We now have a Pell’s equation with $ X = (5b+2), Y = a$, and we have

$$ X^2 - 5Y^2 = 4$$

This has a seed solution $ X = 2, Y = 0$, or $X = 3, Y = 1$. We are almost done, but we need $ X \equiv 2 \pmod{5}$ in order for $b$ to be and integer, and in particular $X=3$ will not work (sob sob).

What is the next thing to do? From theory of Pell's equation, we know that the set of solutions is $ (2,0) * (9, 4)^n$, with the operation done as $ (p,q) * (r,s) = ( pr+5qs, ps+qr)$. Observe that $(9,4) ^2 = (161, 72)$. We have that $(2,0) * (161, 72)^n$ will satisfy the condition that $ X \equiv 2 \pmod{5}$ (since $ p \equiv 2, r \equiv 1 , pq+5rs \equiv 2 \pmod{5}$), and hence we are done.

---

Note: Had $(9,2)^2$ not worked, look at $(9,2)^3$. We are guaranteed that some power will eventually work, since we have a seed that works.

From here, you can backtrack and obtain all of the solutions for $m, n$ if you wish to do so. We have classified all of the solutions, and not just those that fall into a particular family.

Answer 2

To prove that $x^2-xy-y^2=1$ has infinite integer solutions, you can see $ (1,0) $ is a solution; and if $ (a,b) $ is a solution, $ (2a+b,a+b) $ also is. You can find this relation by observing small cases.

Answer 3

Here’s an explicit approach to arriving at ali’s solution.

Apply the quadratic formula to $x^2-xy-y^2-1=0$, looking for non-negative solutions:

$$y=\frac{-x+\sqrt{x^2+4(x^2-1)}}2=\frac{-x+\sqrt{5x^2+4}}2\;.$$

Clearly this is an integer when $y\in\{0,1,3\}$, and a little more computation turns up the next integer value at $y=8$. Now look at the integer solutions discovered so far: $\langle 1,0\rangle,\langle 2,1\rangle,\langle 5,3\rangle$, and $\langle 13,8\rangle$. Those numbers are very familiar: turn the pairs around, and you have $0,1,1,2,3,5,8,13$, i.e., the Fibonacci numbers $F_0$ through $F_7$. If we denote successive solutions by $\langle x_n,y_n\rangle$, this immediately suggests that $y_{n+1}=x_n+y_n$ and $x_{n+1}=y_{n+1}+x_n=2x_n+y_n$. Once you guess those recurrences, it’s a trivial computation to verify that they do indeed yield solutions.