Competition problem — Number theory

Library / /302 of 520

Number theory Difficulty 6.2 National olympiad Prove it

Theorem 1 (Mathematical Induction) Let $P(n)$ be a property or proposition concerning the natural number $n$ . If
(i) $P(1)$ is true when $n=1$ ;
(ii) the truth of $P(n)$ implies the truth of $P(n+1)$ , then $P(n)$ is true for all natural numbers $n$ .

Solution

Proof: Let the set of all natural numbers $n$ for which $P(n)$ holds be $S$ . $S$ is a subset of $\boldsymbol{N}$ . From condition (i), we know $1 \in S$ ; from condition (ii), we know that if $n \in S$ , then $n+1 \in S$ . Therefore, by the principle of induction, $S=N$ . Proof completed.

The theory of divisibility and the basic content of elementary number theory were established long before the Peano axioms were proposed, and of course did not use the induction axiom or mathematical induction. At that time, people relied on "universally recognized" correct properties, which are the least natural number principle and the greatest natural number principle below.

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: NuminaMath-1.5, licensed Apache-2.0. Statement and solution reproduced as published; topic and difficulty added by this site.