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  n₀ ,

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

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

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

                        To prove this equality we use the 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 ² .

                        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 ² + ( 2k + 1 ) = ( k  + 1 ) ² .

                        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.

Back