# Lesson Mathematical induction and arithmetic progressions

Algebra ->  Sequences-and-series -> Lesson Mathematical induction and arithmetic progressions      Log On

 Ad: Mathway solves algebra homework problems with step-by-step help! Ad: Algebrator™ solves your algebra problems and provides step-by-step explanations!

 Algebra: Sequences of numbers, series and how to sum them Solvers Lessons Answers archive Quiz In Depth

This Lesson (Mathematical induction and arithmetic progressions) was created by by ikleyn(4)  : View Source, Show

## Mathematical induction and arithmetic progressions

Mathematical induction  is the method of proving mathematical statements that involve natural (integer) numbers and relate to infinite sets of natural (integer) numbers.

The method of  Mathematical induction  is based on the  Principle of Mathematical induction.
The Principle of Mathematical induction has different forms, formulations and modifications.
In the simplest form, the  Principle of Mathematical induction  is read as follows:
 +-------------------------------------------------------------------------------------------------------------------------------------------- | |    Let  S(n)  be a mathematical statement which relates to any natural number of the infinite sequence  n = 1, 2, 3, . . . |        (to any natural number of the infinite set of all natural numbers). |    Suppose that two following statements are true: |        1) The statement  S(1)  is true. |        2) If the statement  S(k)  is true then the statement  S(k+1)  is true, for any positive integer  k. |    Then the statement  S(n)  is true for all positive integer numbers  n. | +-------------------------------------------------------------------------------------------------------------------------------------------- + | | | | | | | | +

The examples that follow illustrate how the method of Mathematical Induction work.

### Problem 1

Using the method of Mathematical Induction, prove the formula for the sum of the first  n  natural numbers

= .                                 (1)

Solution
Note that this formula was just proved in the lessons  Arithmetic progressions  and  The proofs of the formulas for arithmetic progressions  under the current topic
in this site.  The general formula for the sum of an arithmetic progression was used in the first lesson.  Grouping the given sum with the sum written in the reverse order
was used in the second lesson.  Here we are going to prove the same formula using the method of Mathematical Induction.

So, in the frame of this method, we have the statement  S(n)  saying that the formula  (1)  is valid for any positive integer number  n  of the infinite set of these numbers.

Doing by the method of mathematical induction,  we should first check (prove) that the statement  S(1)  is true. The statement  S(1)  says that the formula  (1)  is valid
for  n=1.  At this value of  n,  the left side of the formula  (1)  is equal to  1.  The right side of the formula  (1)  is equal to  1,  too.  Thus the statement  S(1)  is true,
and this part of proving by the method of mathematical induction is completed.

Next part of proving by the method of mathematical induction is to check that  if  the statement  S(k)  is true for the positive integer  kthen  the statement  S(k+1)
is true for the next positive integer  k+1

So, let us suppose that the statement  S(k)  is true,  that is

=                                  (2)

for the positive integer  k.
Consider the sum for the next integer  k+1

.

Let us group the first  k  additives by placing them into the brackets.  Our sum is equal to

.                                      (3)

Now you can replace the sum of the first  k  additives by    based on our assumption  (2).  Hence, the sum (3) is equal to
= + .         (4)

Simplify the right side of  (4)  by converting the additives to the common denominator, adding the fractions and factoring the numerator.  You get

+ = = = .

Now the formula  (4)  is read as

= .               (5)

Note that  (5)  is nothing else as the statement  S(k+1).

Thus, we started with the assumption that the formula  (2)  is valid, and derived from it that then the formula  (5)  is valid.
In other words, we started with the assumption that the statement  S(k)  is true, and proved that then the statement  S(k+1)  is true.

So, we completed the second part of proving by the method of Mathematical induction.
According to the  Principle of Mathematical induction,  the statement  S(n)  is true for all positive integer  n.
This means that the formula  (1)  is proved for all positive integer  n.

The proof is completed.

The method of Mathematical Induction is the subject which, probably, is not easy to understand to the person who learn it for the first time.  This is why I wrote this
proof in a very detailed way to make all the nuts visible to you.  In practice, "in the everyday life", the writers present the proofs by the method of Mathematical Induction
in a more light style.  So, for  Problem 2  and  Problem 3  below the similar proofs are presented more shortly.  I also re-state the method of proving in the more direct way
as follows:
 +-------------------------------------------------------------------------------------------------------------------------------------------- | |    Let  S(n)  be a mathematical statement which relates to any natural number of the infinite sequence  n = 1, 2, 3, . . . |    Two steps should be done to prove this statement by the method of mathematical induction : |        1) We have to prove that the statement  S(1)  is true. |        2) We have to prove next implication: |              If the statement  S(k)  is true then the statement  S(k+1)  is true, for any positive integer  k. |    If these two steps are done, then the statement  S(n)  is proved for all positive integer numbers  n. | +-------------------------------------------------------------------------------------------------------------------------------------------- + | | | | | | | | +

I like this re-statement because it points to you directly what to do.

### Problem 2

Using the method of Mathematical Induction, prove the formula for the sum of the first  n  odd natural numbers

= .                                 (6)

Solution
Note that this formula was just proved in the lesson  The proofs of the formulas for arithmetic progressions  under the current topic in this site.  The general formulas
for the sum of an arithmetic progression were used in that lesson.  Here we are going to prove the same formula using the method of Mathematical Induction.

First, let us check it for  n=1.  Both the left and the right side of this formula are equal to  1  at  n=1.  So, the base of the Mathematical Induction method is true.

Now, let us prove the implication step of the Mathematical Induction. In other words, let us suppose that the formula  (6)  is valid for some positive integer  k:

= .                                 (7)

Consider the sum for the next integer  k+1

.

Let us group the first  k  additives by placing them into the brackets.  Our sum is equal to

.                           (8)

Now you can replace the sum of the first  k  additives by    based on our assumption  (7).  Hence, the sum  (8)  is equal to
= + .    (9)

The right side of  (9)  is nothing else as  :
+ = .

Now the formula  (9)  is read as

= .            (10)

The formula  (10)  is exactly the formula  (7)  applied to the next integer  k+1  instead of  k.  So, we proved that if the formula  (7)  is true for the positive integer  k, then it is true for the next positive integer  k+1. The step of induction is completed.

According to the  Principle of Mathematical induction,  the formula  (6)  is proved for all positive integer  n.

### Problem 3

Using the method of Mathematical Induction, prove the formula for the sum of the first  n  even natural numbers

= .                               (11)

Solution
Note that this formula was just proved in the lesson  The proofs of the formulas for arithmetic progressions  under the current topic in this site.  The general formulas
for the sum of an arithmetic progression were used in that lesson.  Here we are going to prove the same formula using the method of Mathematical Induction.

First, let us check it for  n=1.  Both the left and the right side of this formula are equal to  1  at  n=1.  So, the base of the Mathematical Induction method is true.

Now, let us prove the implication step of the Mathematical Induction. In other words, let us suppose that the formula  (6)  is valid for some positive integer  k:

= .                               (12)

Consider the sum for the next integer  k+1

.

Let us group the first  k  additives by placing them into the brackets.  Our sum is equal to

.                                    (13)

Now you can replace the sum of the first  k  additives by    based on our assumption  (12).  Hence, the sum  (13)  is equal to
= + .      (14)

Simplify the right side of  (14)  as follows
+ = + = .

Now the formula  (14)  is read as

= .               (15)

The formula  (15)  is exactly the formula  (12)  applied to the next integer  k+1  instead of  k.  So, we proved that if the formula  (12)  is true for the positive integer  k, then it is true for the next positive integer  k+1. The step of induction is completed.

According to the  Principle of Mathematical induction,  the formula  (11)  is proved for all positive integer  n.

### Problem 4

Using the method of Mathematical Induction  prove yourself  the formula for the n-th term of the arithmetic progression

= ,

where is the first term and    is the common difference of the arithmetic progression.

### Problem 5

Using the method of Mathematical Induction  prove yourself  the formula for the sum of the first n terms of the arithmetic progression  , , , ...,

= = ,

where is the first term and    is the common difference of the progression.

### Problem 6

Using the method of Mathematical Induction  prove yourself  the formula for the sum of the first n terms of the arithmetic progression  , , , ...,

= = ,

where is the first term, is the n-th term and    is the common difference of the progression.

This lesson has been accessed 1196 times.