Infinite Descent

"Infinite Descent" is a way of proving theorems involving integers.  Sometimes this type of proof is called "Infinite Regression".  Using this tactic, a proof begins by supposing that some integers exist with certain properties, and then proceeds to find smaller (in absolute value) integers with the same properties.  Such a thing can't go on for ever, because there is a smallest (in absolute value) integer, namely zero.  Herein lies the contradiction.

In an "Infinite Descent" proof, you first assume that a set of numbers with a certain property exists.  Then you find another set of numbers with the same property that's smaller in some specific way than the set of numbers.  If you assume the first set of numbers is minimal, then just one iteration of this descent is enough to prove by contradiction that there is no number with that certain property, but the method is called "Infinite" Descent because it shows more than just a contradiction; it shows that there are no smallest numbers with the given property.   That is, the fact that the descent is infinite affords you the luxury of not needing to assume minimality in the first place.

A simple proof using this tactic shows that the square root of 2 is irrational.

Let q be the square root of 2. That is, q is the positive number such that q² = 2.
Suppose positive integers m and n exist such that m/n = q.
q(m-n) = qm-qn = q²n-qn = 2n-m, so (2n-m)/(m-n) = q
Since q is less than two, m is less than twice n, and it follows that m-n is smaller than n.
So whenever two positive integers m and n exist such that m/n = q, it follows that two smaller positive integers (2n-m) and (m-n) exist in the same ratio as m and n.
Thus there are no smallest positive integers with the given ratio, a contradiction.

As a matter of fact, this proof can be generalized to show that the square root of N is irrational, as long as N isn't a square.  It works by showing that if m/n = q, where q^2 = N, and x = floor(q) < q, then

q(m-xn) = qm-qxn = q^2n - qxn = Nn-xm, so (Nn-xm)/(m-xn) = q,
and since m-xn is the remainder of integer division of m by n, m-xn is smaller than n, but larger than zero.

so we have the infinite descent we wanted: if m/n = q, then so does (Nn-xm)/(m-xn) = q, and the latter are smaller numbers.

Related Pages in this website

Methods of Proof discusses proofs by induction, contradiction, and, yes, Infinite Descent.

No four squares in arithmetic sequence (proof 2) is a nice example of proof by infinite descent, which contains an interesting sidebar "Additional Comments" which points out that such proofs do a lot of work to derive one false statement after another!

Number Theory Home

Perfect Squares -- a proof similar to the one presented here that sqrt(N) is either an integer or irrational, along with other proofs involving squares.

Proof of no solution to A⁴+B⁴=C² by infinite descent

Two Proofs that there are no four squares in arithmetic sequence, both by infinite descent.

The webmaster and author of this Math Help site is Graeme McRae.
[home]  [search]  [email]  [twitter]