2.5 Mathematical Induction

An essential property of the set N = (1, 2, 3, …} of positive integers follows:

2.5.1 Principle of Mathematical Induction I

Let P be a proposition defined on the positive integers; N; that is, P(n) is either true or false for each n Є N
Suppose P has the following two properties:

(i) P(1) is true.
(ii) P(k + 1) is true whenever P(k) is true.

Then P is true for every positive integer n Є N.

We shall not prove this principle. In fact, this principle is usually given as one of the axioms when N is developed axiomatically.

2.5.2.Example

Let P be the proposition that the sum of the first n odd numbers is n²; that is

2.5 Mathematical Induction

(The kth odd number is 2k + 1, and the next odd number is 2k +1). Observe that P(n) is true for n = 1; namely,


Assuming P(k) is true, we add 2k + 1 to both sides of P(k), obtaining


which is P(k + 1).. In other words, P(k + 1) is true whenever P(k) is true. By the principle of mathematical induction, P is true for all n.

There is a form of the principle of mathematical induction which is sometimes more convenient to use. Although it appears different, it is really equivalent to the above principle of induction.

2.5.3 Principle of Mathematical Induction II (Strong Induction)

Let P be a proposition defined on the positive integers N such that:

2.5 Mathematical Induction

(i) P(1) is true.
(ii) P(k) is true whenever P(j) is true for all

Then P is true for every positive integer n Є N.

2.5.4 Remark

Sometimes one wants to prove that a proposition P is true for the set of integers


Where a is any integer, possibly aero. This can be done by simply replacing 1 by a in either of the above Principles of Mathematical Induction.

2.5.5 Definition

An integer P greater than 1 is called prime if the only positive factors of P are 1 and P. a non-prime P ˃ 1 is called “composite”

2.5 Mathematical Induction

2.5.6 Example

Show that if n is an integer greater than 1, then n can be written as a product of primes solution.
We use strong induction.

(i) Basic step at n = 2 the ascertain is true since 2 is a product of one prime which is 2 itself.

(ii) Inductive step. Suppose that if j is an integer such that 2 ≤ j ≤ k than j is a product of primes. If k + 1 is a prime number we have done. Thus we assume that k + 1 is not a prime. Hence,


by the induction hypothesis, both ℓ and m can be written as a product of primes,

   Therefore   

a product of primes. Thus the assertion is true at n = k + 1. Hence the assertion is true for every n ˃ 1