The Infinite Descent Method - Induction

Mathematical Writing - Vivaldi Franco 2014

The Infinite Descent Method
Induction

This is a second form of mathematical induction, developed in the 17th Century by Fermat.5 It exploits the following variant of the well-ordering principle:

·  ($$B$$) There is no infinite decreasing sequence of natural numbers.

This principle follows from the well-ordering principle ($$(A)\Rightarrow (B)$$): if there were an infinite decreasing sequence of natural numbers

$$ n_1 > n_2 > n_3 > \cdots $$

then the set $$ \{n_1,n_2,n_3,\ldots \}$$, which is a non-empty subset of $$\mathbb {N}$$, would have no smallest element. Conversely, well-ordering follows from descent ($$(B)\Rightarrow (A)$$): if there were a non-empty set $$S\subset \mathbb {N}$$ without a smallest element, then choosing an arbitrary element $$n_1\in S$$, we could find $$n_2\in S$$ with $$n_2<n_1$$. Repeating this process we would generate an infinite decreasing sequence of natural numbers.

Fermat applied this method extensively to arithmetical problems. He pointed out that infinite descent is a method for proving that certain properties or relations for whole numbers are impossible, and for this purpose he combined descent with contradiction—as we did for well-ordering. To prove that no positive integer can have a certain set of properties, we assume that a positive integer does have these properties, and we try to deduce that there is a smaller positive integer with the same set of properties. If we succeed, then, by the same argument, these properties would hold for some smaller positive integer, and so forth ad infinitum. Because a sequence of natural numbers cannot decrease indefinitely, no positive integer can have the stated properties.

Infinite descent was brought to prominence by Euler, who proved with it that it is impossible to find natural numbers $$x,y,z$$ such that

$$ x^3+y^3=z^3. $$

This is a special case of the celebrated Fermat’s last theorem, in which the exponent 3 is replaced by an arbitrary integer $$n >$$ 2. In keeping with this tradition, we now apply the method of infinite descent to prove the non-existence of integer solutions of a polynomial equation.

Theorem

For every prime $$p$$ the equation $$px^2=y^2$$ has no solutions in the natural numbers.

This statement is equivalent to the irrationality of $$\sqrt{p}$$, as one sees by dividing each term of the equation by $$x^2$$, and then taking the positive square root. The argument presented here is a variant and a generalisation of that given in Sect. 7.1 for the irrationality of $$\sqrt{2}$$.

PROOF. Suppose that there are natural numbers $$n_0,n_1$$, such that $$pn_1^2 = n_0^2$$. So $$pn_1^2$$ is the square of a natural number. Since $$p$$ divides $$n_0^2=n_0n_0$$, by the basic property of prime numbers $$p$$ must divide $$n_0$$, and we have $$n_0 = pn_2$$ for some natural number $$n_2$$. Then $$pn_1^2 = p^2n_2^2$$, and hence $$n_1^2 = pn_2^2$$. So $$n_2 < n_1$$ and $$pn_2^2$$ is the square of a natural number.

Repeating the argument, there is $$n_3 < n_2$$ such that $$pn_3^2$$ is the square of a natural number. This continues for ever, which is impossible. Hence the equation $$px^2=y^2$$ has no solution, as stated. $$\square $$