OpenCart Templates
Friday , July 28 2017
Home / Elementary Number Theory / Principle of induction| Elementary number theory

Principle of induction| Elementary number theory

Theorem (Principle of induction): Let S be a set of positive integers with the properties (i) 1 belongs to S and (ii) Whenever the integer K is in S then the next integer K+1 must also be in S. Then S is the set of all positive integers.

Proof: Let T be the set of all positive integers not in S and assume that T is non empty. The well ordering principle tells us that T possess a least element, which we denote by a certainly a>1 and so 0<a-1<a.

The choice of a as the smallest positive integer in T implies that a-1 is not member of T, or equivalently, that a-1 belongs to S. By hypothesis, S must also contain (a-1)+1=a, which contradicts the fact that a lies in T. We conclude that T is empty, and in consequence that’s contains all the positive integers.            (Proved)

Check Also

Application of Euclidian’s algorithm in Diophantine equation

Problem-1: Which of the following Diophantine equations cannot be solved –   a) 6x + ...

Leave a Reply

Your email address will not be published. Required fields are marked *