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 0 ,
2) from validity of this statement at
n
=
k
its validity follows at
n
=
k
+ 1
for any
k
n
0
,
then this statement is valid for any natural number
n
n
0
.
E x a m p l e 1. Prove that 1 + 3 + 5 + ... + ( 2 n – 1 ) = n 2 .
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 + ... + ( 2 k – 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 + ... + ( 2 k – 1 ) + ( 2 k + 1 ) = k 2 + ( 2 k + 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 .