Proof by Infinite Descent

We have previously discussed proof by contradiction [1]. Here, we will be describing what can be viewed as a specialized version of this method. This method, however, is sufficiently specialized that is it worth discussing separately. As a mathematician, I find this idea absolutely brilliant. Even though it isn’t terribly difficult to explain, only an intellect of the first order with a lot of creativity could have come up with this. In fact, if you spend enough time thinking about it, this is a sort of reverse version of the method of proof by induction [2] – in fact, it is a sort of combination of the methods of induction and contradiction. We really only began to see this method in the 1600’s with the amateur mathematician Pierre de Fermat. There is a reason it took a while for this method to be used – even though the concept is nothing more than a special version of proof by contradiction, it required a lot of ingenuity to realize that there are certain kinds of problems that contradict themselves in this particular way.

You can imagine the kind of ingenuity that I am speaking of as similar to writing a beautiful poem or book. It requires a lot of time, devotion, and cleverness to write a good story. However, once the story is written down, the amount of skill required to understand the story is nowhere near the amount of skill required to write the story. The type of proof I will now explain is like that. It is not the sort of thing you’d immediately think about when you think about contradictory statements – and for this reason I consider this to be a quite enjoyable and ingenious method.

  • Suppose that we are posed with a problem for which every possible solution can be listed in order from least to greatest in an organized way.
    • For a day-to-day life example, think about the question “how much does such-and-such cost?” The ‘least’ possible answer is ‘Oh, it’s free!’ The next smallest is 1 cent, then 2 cents, and so on. When I list it out like this, I’m also not skipping anything – there isn’t a price between 1 cent and 2 cents, so we are making a genuinely complete list here.
    • For a ‘mathematical’ example, if you have an equation like x^2 + y^2 = z^2, where we assume that both x, y and z are positive whole numbers, then the value of x + y + z is a way you could ascribe an order to the solutions. The smallest possible value of x + y + z is the first solution, the next smallest is the second solution, and so on.
  • Suppose also that there really is such a thing as a first ‘possible’ solution, which may or may not actually be a solution, and that every solution only has a finite number before it.
    • In the previous example, the smallest possible value of x + y + x is 3, when x = y = z = 1. Since x, y, z > 0, the value of x + y + z could not be any smaller than 1 + 1 + 1 = 3.
    • The ‘finite number before it’ part is much like saying ‘if I choose a positive whole number, no matter which one, the number of positive whole numbers less than that one is finite.’ For instance, you could make a list of all the positive numbers less than one million – it would take a while, but you could do it.
  • Suppose that if our problem has a solution, then we can derive a ‘smaller’ solution using this solution.
    • The ‘smaller’ here is in reference to the ordering from before.

Here is the principle of infinite descent – if you can always use some hypothetical solution to a problem to derive a smaller solution to the same problem, then you could derive smaller and smaller solutions forever. Your solutions can ‘descend’ forever – hence the word ‘descent’ in the title of this article. This is not in and of itself a problem, if you had an infinite number of smaller solutions to work with, that is not a problem. But, if the context in which you are working does not allow an infinite number of potential solutions to your problem, then you eventually run out of space and contradict yourself. To see the type of contradictory statement that would result, here is an example:

There are an infinite number of whole numbers between 1 and 10.

This is obviously false – because 1, 2, 3, 4, 5, 6, 7, 8, 8, 9, and 10 are a complete list of such numbers, and this is not infinite. Here we are thinking in the style of proof by contradiction – if my starting assumptions wind up leading me to this point, then my starting assumptions were bad.

This is known today as Fermat’s method of infinite descent, or just infinite descent. It is extremely clever, and is worth reading over a few times. To repeat, the general idea is that you obtain some kind of list that, if it every begins, can be ‘decreased’ forever in some sense, but which for another reason cannot be decreased forever. Here we arrive at our contradiction, as in the methodology of proof by contradiction.

I now try to provide what I find to be a very interesting proof that uses this method.

Theorem: There is no right triangle with all three side lengths a fractional value that has an area that is the square of some fraction.

Proof: We will use the method of proof by infinite descent. For the moment, we guess that there actually is such a triangle, say with side lengths x, y, z all of which are fractions. Then since this triangle is a right triangle, it satisfies the Pythagorean theorem, so x^2 + y^2 = z^2 must be true. It also must be true that the area A = \frac{1}{2} xy of this triangle must be a perfect square, say d^2, and so we also have the equation \frac{1}{2}xy = d^2. Since all three of x, y, z are fractions, we can multiply all three numbers by the ‘least common denominator’ in order to make all of them into whole numbers that also satisfy all of the same equations, and so we can assume from the beginning that all three of x, y, z are positive whole numbers.

I have written before about right triangles with integer length sides, and we know from that discussion that we can remove all the common factors of x, y, z, and we can find some positive whole numbers a,b which have no common factors and one of which is even, that satisfy x = 2ab, y = a^2-b^2, and z = a^2+b^2 (to see why, see my posts *CITE ARTICLES*). We can use these new equations for x and y as substitutions into $\frac{1}{2} xy = d^2$ to obtain the new equation ab(a^2-b^2) = d^2, and remembering the difference-of-squares formula a^2 - b^2 = (a-b)(a+b), we can see that ab(a-b)(a+b) = d^2.

Now, this last equation contains a ton of information. Because, remember that the numbers a and b cannot have any factors in common, and for the same kind of reason that “even + odd = odd”, no two of the four of the numbers a, b, a-b, a+b have any common factors. Now, since d^2 is a perfect square, any prime factor in the equation ab(a-b)(a+b) = d^2 must show up an even number of times. Since no factors are shared by any of the four numbers on the left-hand side, only one of these four numbers can have as a factor any prime number that factors into d^2, and since everything winds up equal in the end, there must be the same number of factors on the left and the right. You can convince yourself along these lines of thought that all four of the numbers a, b, a-b, a+b must themselves be perfect squares.

In particular, we may choose some positive whole numbers r,s that satisfy the rule $r^2 = a-b$ and $s^2 = a+b$. Since one of a,b was odd and the other even, both of r^2, s^2 are odd, and so both of r,s are also odd (since only by multiplying two odds can you get an odd). Then because adding subtracting odds gives an even number, both of r-s, r+s are even. We now define some new numbers, u = \frac{s-r}{2} and v = \frac{s+r}{2}, which are whole numbers since both of the numerators are even. If we add these together, we find that u+v = \frac{s-r+s+r}{2} = \frac{2s}{2} = s, which is odd. The only way this can happen is if exactly one of the numbers u,v is odd, and the other is even.

We now want to learn a bit more about u and v. If we square each of them, and if we remember our formulas for r^2 and $s^2$ from earlier, and we use the simplifications (s-r)^2 + (s+r)^2 = 2(r^2+s^2), we realize that

u^2+v^2 = \frac{(s-r)^2+(s+r)^2}{4} = \frac{2(r^2+s^2)}{4} = \frac{2(a+b)+2(a-b)}{4} = a.

Earlier, we have already remarked that a is a perfect square. Therefore, the three numbers u,v,\sqrt{a} actually satisfy the Pythagorean equation, and the area of the resulting triangle is

\frac{1}{2} uv = \frac{1}{2}\frac{(s-r)(s+r)}{2*2} = \frac{1}{2}\frac{s^2-r^2}{4} = \frac{1}{2} \frac{(a+b) - (a-b)}{4} = \frac{1}{2} \frac{2b}{4} = \frac{b}{4}.

Remember, however, that b is a whole number and perfect square, and since 4 is a perfect square, so is b/4. So we have generated a new triangle with exactly the same property as before, that has a smaller area.

But we could do this all over again, finding smaller and smaller and smaller areas. We cannot actually do this, since you cannot have a list of positive whole number areas that gets smaller forever. Therefore, there cannot be any such triangle to begin with. We have now finished our proof.

This is a more complicated proof than some, but because it is more complicated, we can learn much more from it. Because we now know that all of the numbers we used along the way in this proof are impossibilities, we can say a great deal more than just our original statement about triangles.

For example, along the way we found three numbers a-b, a, a+b which were all perfect squares. These three form what is called an arithmetic sequence, because I can form this list by using a starting point (namely a-b) and repeatedly adding some number to form the next entry (here, we add b each time). We therefore now also know that there is no such thing as three perfect squares in an arithmetic progression.

Another thing we know, is that if a,b were actually perfect squares, we would have solved the equation z^2 = a^2 + b^2 by using perfect squares for a,b. In other words, if a = x^2 and b = y^2, we would have solved z^2 = x^4 + y^4. So we now also know that this equation is impossible if x,y,z are all positive whole numbers. This turns out to be a special case of what became a very important problem in mathematics known as Fermat’s Last Theorem, which makes the much broader claim that the equation x^n + y^n = z^n, even though it is just the Pythagorean equation when n=2, never has any solutions at all for any value of n larger than 2. What we have just done, in effect, is to say that for n = 4 there are no solutions.

This is one of my favorite methods of proof in mathematics. It isn’t used especially often, but I like the clever twists and turns in the argument. To me, it feels a lot like reading a well-written short story. I hope my readers can have a taste of that kind of feeling. If you do, then perhaps you can better understand why those of us who like mathematics feel the way we do about it.




Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

%d bloggers like this: