66874

Principle of Mathematical Induction (PMI)

Let p( 1), p(2),p{k),... be sentences having the

following two

properties:

1)    p(\) is true;

2) Vk    [p(k) is true =ty(k + 1) is true ].

Then Vn p(n) is true.

Example:

Let’s prove the Bemoulli ineąuality:

Vn 1 + nxb (1 + x)n, x > -1.

The initial step: For n = 1 we have 1 + x 6 1 + x - true. The inductive step: We assume that for k{k >1) there

is:

1 + kx6 (1 + x)k, x >-l. Under this assumption we have to

prove the ineąuality: l+(£+l)*6(l + jc)(&+1), jc >-l. 1 + >bc6 (1 + x)k 1(1 + x) =Ąl+kx)(l + jc) 6 (1 + x)k+l 1 + (k + 1)jc + kx2 6 (1 + x)/:+l.

Since kx2 is positive, we have:

1 + {k + 1)jc 6 1 + (k + 1)jc + kx 2 6(1+ jc)£+1

=>\ + {k + l)x 6 (1 + *)(&+l). Both assumptions of PMI

are

satisfied, therefore the conclusion is true.