Program of Lessons

# Mathematical induction

Assume its necessary to prove a statement ( formula, property etc.), depending on a natural number  n . If :

1)  this statement is valid for some natural number  n0 ,

2)  from validity of this statement at  n = k  its validity follows at  n = k + 1  for any  kn0 ,

then this statement is valid for any natural number  n n0 .

E x a m p l e 1.  Prove that  1 + 3 + 5 + ...+ ( 2n  1 ) = n 2 .

To provethis equalityweusethe mathematical induction method.

It is obvious that at  n = 1  this equality is valid. Assume that it is

valid at some  k , i.e. the following equality takes place:

1 + 3 + 5 + ... + ( 2k  1 ) = k 2 .

Prove that then it takes place also at  k + 1. Consider the correspon-

ding sum at  n = k + 1 :

1 + 3 + 5 + ... + ( 2k  1 ) + ( 2k + 1 ) = k 2 + ( 2k + 1 ) = ( k +1) 2 .

Thus, from the condition that this equality is valid at  k  it follows,

that it is valid at  k+ 1 , hence, it is valid at any natural number  n ,

which was to be proved.

E x a m p l e 2.  See the solution of the problem 5.047.

E x a m p l e 3.  See the solution of the problem 5.048.

Back