The method of descent

I hadn't intended to define this so formally, but here goes:

If $k$ is an integer, and $P$ is some property of integers, if

• whenever $P(n)$ is true for an integer $n>k$, then there must be some smaller integer $j$, $n > j \geq k$ for which $P(j)$ is true, and yet
• $P(k)$ is not true

then $P(n)$ must be false for all $n \geq k$.

Really, this is just the contrapositive of strong induction, applied to the negation of $P(n)$. In the language of the ladder metaphor, if you know you can't reach any rung without first reaching a lower rung, and you also know you can't reach the bottom rung, then you can't reach any rungs.

The above is often called finite descent, to distinguish it from the variant method known as infinite descent:

If $k$ is an integer, and $P$ is some property of integers, if

• whenever $P(n)$ is true for an integer $n>k$, there must be some smaller integer $j$, $n > j > k$ for which $P(j)$ is true

then $P(n)$ must be false for all $n>k$.

That is, if there were an $n$ for which $P(n)$ was true, you could construct a sequence $n > n_1 > n_2 > \ldots$ all of which would be greater than $k$ - but for the integers, no such descending, but bounded below sequence is possible.

9 (Putnam, 1972) Show that, for all $n > 1$, $n$ does not divide $2^n - 1$.

hint: here we are not using descent based on $n$, but on the prime factors of $n$. We will also need this much number theory (at least in my proof): $2^{p-1} \equiv 1 \bmod p$, and the smallest value $m$ for which $2^m \equiv 1 \bmod p$ must be a factor of $p-1$.

The classic example of infinite descent is in Fermat's proof that there are no positive integer solutions to $x^4 + y^4 = z^2$, or that every prime of the form $4p+1$ is the sum of two squares. I'm including one of these along with an outline of the solution.

10 There are no positive integer solutions of $x^4 + y^4 = z^2$

SKETCH of proof: You need to know that every positive integer solution of $a^2 + b^2 = c^2$ where $a$,$b$ and $c$ are relatively prime can be expressed in terms of two relatively prime numbers $m$, and $n$ where $a=m^2 - n^2$, $b=2mn$, and $c=m^2 + n^2$. (Assuming $b$ is the even one of $a$ and $b$ - one of them must be even)

So suppose you have a solution to $x^4 + y^4 = z^2$. Applying the above fact to the pythagorean triple $x^2$, $y^2$, $z$ gives $x^2 = p^2 - q^2$, $y^2 = 2pq$, and $z = p^2 + q^2$. Since $2pq$ is a square, and $p$ and $q$ have no common factors. So one of $p$ and $q$ must be 2 times a square and the other is an odd square. And since one $x$, $p$, $q$ themselves form a (relatively prime) pythagorean triple, we can see that there are $r$ and $s$ for which $x = r^2 - s^2$, $q = 2rs$, and $p = r^2 + s^2$. This means $q$ is the one that is 2 times a square ($q = 2u^2$) and $p$ is an odd square ($p= v^2$).

Now $q=2u^2 = 2rs$, which means $r$ and $s$ are themselves perfect squares. Yet $r^2 + s^2 = p = v^2$ which means $v^2$ is expressible as the sum of fourth powers. Yet if we look at the construction of $v$, we see $v^2<z^2$, which creates our infinite descent, a contradiction.