Vieta Jumping is a nickname for a particular kind of descent method that has become quite popular in higher level math olympiad number theory problems. Like other instances of descent, it occurs when you have to solve a Diophantine equation (or system of equations, congruences or inequalities) whose solutions have some recursive structure. It is important to understand that Vieta Jumping is not a technique that you can choose to use or not to use: most Vieta Jumping problems can only be solved by Vieta Jumping.
How to recognize Vieta Jumping? Vieta Jumping is just a particular instance of a more general method of descent, so don't be surprised if the solutions in your problem have a more complicated recursive structure. The tell-tale sign of Vieta jumping is the existence of a Lemma (similar in spirit to the one below), which gives a relationship between different possible solutions. Look for a symmetric equation or congruence that has degree two in each of the two variables. (Note that there may also be other "parameter" variables in the problem.) Once such a lemma is recognized and established, you should look for some inequalities that will tell you in what direction to jump.
Perhaps the earliest Vieta Jumping problem was Problem 6 at the 1988 International Mathematical Olympiad. At the time, it was widely recognized as both beautiful and exceedingly hard, because the technique of Vieta Jumping was not widely used.
IMO'88/6. Let and be positive integers such that divides Show that is a perfect square.
Solution: Main Idea: suppose Then for a fixed the set of solutions has a very interesting structure, described by the following lemma.
Lemma. Suppose is a positive integer solution of the equation Then also is a solution.
Proof: Consider the quadratic equation For a given solution , we know that is a root of the above equation. By Vieta (sum of roots), we know that the other root is , which is an integer. Using the product of roots, the other root can be written as .
If let the other root be . We have If then which contradicts being the root of the equation. If then so is a perfect square and we are done. Otherwise, we can keep going, using instead of . We get a decreasing sequence of positive integers so that for all the pair satisfies Clearly, this sequence cannot continue indefinitely, so at some point one of the numbers will become proving that is a perfect square.
The infinite sequence as above is what distinguishes Vieta Jumping from other descent methods. Note that each consecutive pair is a solution, and and are two roots of a quadratic equation that involves . The condition must be symmetric and the sequence must be in some sense decreasing, so the sequence must terminate. Note also that Vieta Jumping works both ways: one can recover all solutions from the terminal ones by "jumping back".
1. [Crux Mathematicorum] Suppose and are positive integers, such that Show that is a perfect square.
Solution. Suppose For fixed and consider all positive integer pairs such that Then this set has recursive structure, given by the following lemma.
Lemma. Suppose satisfies the equation and . Then also satisfies the equation (where is plugged in for and is plugged in for ).
Proof of Lemma. The equation has as one of its roots. Because cannot be and, by Vieta's formula, the other root is
Now suppose is not a perfect square. Staring from with we will apply the Lemma. Note that cannot be negative, otherwise we get a contradiction: Since is not a perfect square, cannot be so Also, We can continue and get an infinite decreasing sequence This is impossible, so must be a perfect square.
2. Find the number of pairs of non-negative integers , such that , and .
Solution: We will first prove the following lemma.
Lemma. Suppose pair is such that , and . Then the pair satisfies the conditions , and .
Proof. The first two conditions are obvious. To prove the third one, note that and , thus .
Now starting from any pair satisfying the condition above, we apply Lemma several times, producing smaller and smaller pairs, until we get to a pair for some . Note that the above construction can be uniquely reversed: the pair is obtained from a pair by setting . So we can generate all pairs satisfying the conditions of the problem from pairs for . Specifically,
Overall, we get pairs with , plus pairs with , plus other pairs, for a grand total of pairs.