Examples - mathematical induction. Method of mathematical induction calculator online Examples of mathematical induction with explanations

Lecture 6. Method of mathematical induction.

New knowledge in science and life is obtained in different ways, but all of them (if you do not go into details) are divided into two types - the transition from the general to the specific and from the specific to the general. The first is deduction, the second is induction. Deductive reasoning is what is commonly called in mathematics. logical reasoning, and in mathematical science deduction is the only legitimate method of investigation. The rules of logical reasoning were formulated two and a half millennia ago by the ancient Greek scientist Aristotle. He created a complete list of the simplest correct reasoning, syllogisms– “building blocks” of logic, while simultaneously indicating typical reasoning that is very similar to correct, but incorrect (we often encounter such “pseudological” reasoning in the media).

Induction (induction - in Latin guidance) is clearly illustrated by the famous legend of how Isaac Newton formulated the law of universal gravitation after an apple fell on his head. Another example from physics: in a phenomenon such as electromagnetic induction, an electric field creates, “induces” a magnetic field. “Newton's apple” is a typical example of a situation where one or more special cases, that is, observations, “suggest” a general statement; a general conclusion is drawn on the basis of particular cases. The inductive method is the main one for obtaining general patterns in both the natural and human sciences. But it has a very significant drawback: based on particular examples, an incorrect conclusion can be drawn. Hypotheses arising from private observations are not always correct. Let's consider an example due to Euler.

We will calculate the value of the trinomial for some first values n:

Note that the numbers obtained as a result of calculations are prime. And one can directly verify that for each n 1 to 39 polynomial value
is a prime number. However, when n=40 we get the number 1681=41 2, which is not prime. Thus, the hypothesis that could arise here, that is, the hypothesis that for each n number
is simple, turns out to be false.

Leibniz proved in the 17th century that for every positive whole n number
divisible by 3, number
divisible by 5, etc. Based on this, he assumed that for any odd k and any natural n number
divided by k, but soon I noticed that
is not divisible by 9.

The considered examples allow us to draw an important conclusion: a statement can be fair in a number of special cases and at the same time unfair in general. The question of the validity of a statement in the general case can be resolved by using a special method of reasoning called by mathematical induction(complete induction, perfect induction).

6.1. The principle of mathematical induction.

♦ The method of mathematical induction is based on principle of mathematical induction , which is as follows:

1) the validity of this statement is checked forn=1 (induction basis) ,

2) the validity of this statement is assumed forn= k, Wherek– arbitrary natural number 1(induction assumption) , and taking this assumption into account, its validity is established forn= k+1.

Proof. Let us assume the opposite, that is, suppose that the statement is not true for every natural n. Then there is such a natural m, What:

1) statement for n=m not fair,

2) for everyone n, smaller m, the statement is true (in other words, m is the first natural number for which the statement is not true).

It's obvious that m>1, because For n=1 the statement is true (condition 1). Hence,
- natural number. It turns out that for a natural number
the statement is true, and for the next natural number m it's unfair. This contradicts condition 2. ■

Note that the proof used the axiom that any collection of natural numbers contains the smallest number.

A proof based on the principle of mathematical induction is called by the method of complete mathematical induction .

 Example6.1. Prove that for any natural n number
divisible by 3.

Solution.

1) When n=1, so a 1 is divisible by 3 and the statement is true when n=1.

2) Suppose that the statement is true for n=k,
, that is, that number
is divisible by 3, and we establish that when n=k+1 number is divisible by 3.

Indeed,

Because Each term is divisible by 3, then their sum is also divisible by 3. ■ 

 Example6.2. Prove that the sum of the first n natural odd numbers is equal to the square of their number, that is.

Solution. Let's use the method of complete mathematical induction.

1) We check the validity of this statement when n=1: 1=1 2 – this is true.

2) Suppose that the sum of the first k (
) of odd numbers is equal to the square of the number of these numbers, that is. Based on this equality, we establish that the sum of the first k+1 odd numbers is equal to
, that is .

We use our assumption and get

. ■ 

The method of complete mathematical induction is used to prove some inequalities. Let us prove Bernoulli's inequality.

 Example6.3. Prove that when
and any natural n inequality is true
(Bernoulli's inequality).

Solution. 1) When n=1 we get
, which is true.

2) We assume that when n=k there is inequality
(*). Using this assumption, we prove that
. Note that when
this inequality holds and therefore it suffices to consider the case
.

Let's multiply both sides of the inequality (*) by the number
and we get:

That is (1+
. ■ 

Proof by method incomplete mathematical induction some statement depending on n, Where
carried out in a similar way, but at the beginning fairness is established for the smallest value n.

Some problems do not explicitly state a statement that can be proven by mathematical induction. In such cases, you need to establish the pattern yourself and make a hypothesis about the validity of this pattern, and then use the method of mathematical induction to test the proposed hypothesis.

 Example6.4. Find the amount
.

Solution. Let's find the sums S 1 , S 2 , S 3. We have
,
,
. We hypothesize that for any natural n the formula is valid
. To test this hypothesis, we will use the method of complete mathematical induction.

1) When n=1 hypothesis is correct, because
.

2) Suppose that the hypothesis is true for n=k,
, that is
. Using this formula, we establish that the hypothesis is true even when n=k+1, that is

Indeed,

So, based on the assumption that the hypothesis is true when n=k,
, it has been proven that it is true also for n=k+1, and based on the principle of mathematical induction we conclude that the formula is valid for any natural number n. ■ 

 Example6.5. In mathematics, it is proven that the sum of two uniformly continuous functions is a uniformly continuous function. Based on this statement, you need to prove that the sum of any number
of uniformly continuous functions is a uniformly continuous function. But since we have not yet introduced the concept of “uniformly continuous function,” let us pose the problem more abstractly: let it be known that the sum of two functions that have some property S, itself has the property S. Let us prove that the sum of any number of functions has the property S.

Solution. The basis of induction here is contained in the formulation of the problem itself. Having made the induction assumption, consider
functions f 1 , f 2 , …, f n , f n+1 that have the property S. Then . On the right side, the first term has the property S by the induction hypothesis, the second term has the property S by condition. Consequently, their sum has the property S– for two terms the induction basis “works”.

This proves the statement and we will use it further. ■ 

 Example6.6. Find all natural n, for which the inequality is true

Solution. Let's consider n=1, 2, 3, 4, 5, 6. We have: 2 1 >1 2, 2 2 =2 2, 2 3<3 2 , 2 4 =4 2 , 2 5 >5 2, 2 6 >6 2. Thus, we can make a hypothesis: inequality
has a place for everyone
. To prove the truth of this hypothesis, we will use the principle of incomplete mathematical induction.

1) As was established above, this hypothesis is true when n=5.

2) Assume that it is true for n=k,
, that is, the inequality is true
. Using this assumption, we prove that the inequality
.

Because
and at
there is inequality

at
,

then we get that
. So, the truth of the hypothesis at n=k+1 follows from the assumption that it is true when n=k,
.

From paragraphs. 1 and 2, based on the principle of incomplete mathematical induction, it follows that the inequality
true for every natural
. ■ 

 Example6.7. Prove that for any natural number n the differentiation formula is valid
.

Solution. At n=1 this formula looks like
, or 1=1, that is, it is correct. Making the induction assumption, we have:

Q.E.D. ■ 

 Example6.8. Prove that the set consisting of n elements, has subsets

Solution. A set consisting of one element A, has two subsets. This is true because all its subsets are the empty set and the empty set itself, and 2 1 =2.

Let us assume that every set of n elements has subsets If the set A consists of n+1 elements, then we fix one element in it - we denote it d, and divide all subsets into two classes - those not containing d and containing d. All subsets from the first class are subsets of the set B obtained from A by removing an element d.

The set B consists of n elements, and therefore, by induction, he has subsets, so in the first class subsets

But in the second class there are the same number of subsets: each of them is obtained from exactly one subset of the first class by adding an element d. Therefore, in total the set A
subsets

Thus the statement is proven. Note that it is also true for a set consisting of 0 elements - the empty set: it has a single subset - itself, and 2 0 = 1. ■ 

Using the method of mathematical induction, prove that for any natural n the following equalities are valid:
A) ;
b) .

Solution.

a) When n= 1 the equality is true. Assuming the validity of the equality at n, let us show its validity even when n+ 1. Indeed,

Q.E.D.

b) When n= 1 the validity of the equality is obvious. From the assumption of its validity at n should

Given the equality 1 + 2 + ... + n = n(n+ 1)/2, we get

1 3 + 2 3 + ... + n 3 + (n + 1) 3 = (1 + 2 + ... + n + (n + 1)) 2 ,

i.e. the statement is also true when n + 1.

Example 1. Prove the following equalities

Where n ABOUT N.

Solution. a) When n= 1 the equality will take the form 1=1, therefore, P(1) is true. Let us assume that this equality is true, that is, it holds

. It is necessary to check (prove) thatP(n+ 1), that is true. Since (using the induction hypothesis) we get that is, P(n+ 1) is a true statement.

Thus, according to the method of mathematical induction, the original equality is valid for any natural n.

Note 2. This example could have been solved differently. Indeed, the sum is 1 + 2 + 3 + ... + n is the sum of the first n terms of an arithmetic progression with the first term a 1 = 1 and difference d= 1. By virtue of the well-known formula , we get

b) When n= 1 the equality will take the form: 2 1 - 1 = 1 2 or 1=1, that is, P(1) is true. Let us assume that the equality

1 + 3 + 5 + ... + (2n - 1) = n 2 and prove that it occursP(n + 1): 1 + 3 + 5 + ... + (2n - 1) + (2(n + 1) - 1) = (n+ 1) 2 or 1 + 3 + 5 + ... + (2 n - 1) + (2n + 1) = (n + 1) 2 .

Using the induction hypothesis, we obtain

1 + 3 + 5 + ... + (2n - 1) + (2n + 1) = n 2 + (2n + 1) = (n + 1) 2 .

Thus, P(n+ 1) is true and, therefore, the required equality is proven.

Note 3. This example can be solved (similar to the previous one) without using the method of mathematical induction.

c) When n= 1 the equality is true: 1=1. Let us assume that the equality is true

and show that that is, truthP(n) implies truthP(n+ 1). Really, and, since 2 n 2 + 7 n + 6 = (2 n + 3)(n+ 2), we get and, therefore, the original equality is valid for any naturaln.

d) When n= 1 the equality is true: 1=1. Let us assume that it takes place

and we will prove that

Really,

e) Approval P(1) true: 2=2. Let us assume that the equality

is true, and we will prove that it implies the equality Really,

Consequently, the original equality holds for any natural n.

f) P(1) true: 1/3 = 1/3. Let there be equality P(n):

. Let us show that the last equality implies the following:

Indeed, considering that P(n) holds, we get

Thus, equality is proven.

g) When n= 1 we have a + b = b + a and therefore equality is fair.

Let Newton's binomial formula be valid for n = k, that is,

Then Using equality we get

Example 2. Prove inequalities

a) Bernoulli inequality: (1 + a) n ≥ 1 + n a , a > -1, n ABOUT N.

b) x 1 + x 2 + ... + x n ≥ n, If x 1 x 2 · ... · x n= 1 and x i > 0, .

c) Cauchy's inequality with respect to the arithemetic mean and the geometric mean
Where x i > 0, , n ≥ 2.

d) sin 2 n a + cos 2 n a ≤ 1, n ABOUT N.

f) 2 n > n 3 , n ABOUT N, n ≥ 10.

Solution. a) When n= 1 we get the true inequality

1 + a ≥ 1 + a . Let us assume that there is an inequality

(1 + a) n ≥ 1 + n a

(1)

and we will show that then it takes place and(1 + a) n + 1 ≥ 1 + (n+ 1)a .

Indeed, since a > -1 implies a + 1 > 0, then multiplying both sides of inequality (1) by (a + 1), we obtain

(1 + a) n(1 + a) ≥ (1 + n a )(1 + a ) or (1 + a ) n + 1 ≥ 1 + (n+ 1)a + n a 2 Since n a 2 ≥ 0, therefore(1 + a) n + 1 ≥ 1 + (n+ 1)a + n a 2 ≥ 1 + ( n+ 1)a .

Thus, if P(n) is true, then P(n+ 1) is true, therefore, according to the principle of mathematical induction, Bernoulli’s inequality is true.

b) When n= 1 we get x 1 = 1 and therefore x 1 ≥ 1 that is P(1) is a fair statement. Let's pretend that P(n) is true, that is, if adica, x 1 ,x 2 ,...,x n - n positive numbers whose product is equal to one, x 1 x 2 ·...· x n= 1, and x 1 + x 2 + ... + x n ≥ n.

Let us show that this sentence entails the truth of the following: if x 1 ,x 2 ,...,x n ,x n+1 - (n+ 1) positive numbers such that x 1 x 2 ·...· x n · x n+1 = 1, then x 1 + x 2 + ... + x n + x n + 1 ≥n + 1.

Consider the following two cases:

1) x 1 = x 2 = ... = x n = x n+1 = 1. Then the sum of these numbers is ( n+ 1), and the required inequality is satisfied;

2) at least one number is different from one, let, for example, be greater than one. Then, since x 1 x 2 · ... · x n · x n+ 1 = 1, there is at least one more number different from one (more precisely, less than one). Let x n+ 1 > 1 and x n < 1. Рассмотрим n positive numbers

x 1 ,x 2 ,...,x n-1 ,(x n · x n+1). The product of these numbers is equal to one, and, according to the hypothesis, x 1 + x 2 + ... + x n-1 + x n x n + 1 ≥ n. The last inequality is rewritten as follows: x 1 + x 2 + ... + x n-1 + x n x n+1 + x n + x n+1 ≥ n + x n + x n+1 or x 1 + x 2 + ... + x n-1 + x n + x n+1 ≥ n + x n + x n+1 - x n x n+1 .

Because the

(1 - x n)(x n+1 - 1) > 0, then n + x n + x n+1 - x n x n+1 = n + 1 + x n+1 (1 - x n) - 1 + x n =
= n + 1 + x n+1 (1 - x n) - (1 - x n) = n + 1 + (1 - x n)(x n+1 - 1) ≥ n+ 1. Therefore, x 1 + x 2 + ... + x n + x n+1 ≥ n+1, that is, if P(n) is true, thenP(n+ 1) fair. The inequality has been proven.

Note 4. The equal sign holds if and only if x 1 = x 2 = ... = x n = 1.

c) Let x 1 ,x 2 ,...,x n- arbitrary positive numbers. Consider the following n positive numbers:

Since their product is equal to one: according to the previously proven inequality b), it follows that where

Note 5. Equality holds if and only if x 1 = x 2 = ... = x n .

d) P(1) is a fair statement: sin 2 a + cos 2 a = 1. Let us assume that P(n) is a true statement:

Sin 2 n a + cos 2 n a ≤ 1 and show what happensP(n+ 1). Really, sin 2( n+ 1) a + cos 2( n+ 1) a = sin 2 n a sin 2 a + cos 2 n a cos 2 a< sin 2n a + cos 2 n a ≤ 1 (if sin 2 a ≤ 1, then cos 2 a < 1, и обратно: если cos 2 a ≤ 1, then sin 2 a < 1). Таким образом, для любого n ABOUT N sin 2 n a + cos 2 n ≤ 1 and the equality sign is achieved only whenn = 1.

e) When n= 1 statement is true: 1< 3 / 2 .

Let's assume that and we will prove that

Because the

considering P(n), we get

f) Taking into account remark 1, let's check P(10): 2 10 > 10 3, 1024 > 1000, therefore, for n= 10 the statement is true. Let's assume that 2 n > n 3 (n> 10) and prove P(n+ 1), that is 2 n+1 > (n + 1) 3 .

Since when n> 10 we have or , follows that

2n 3 > n 3 + 3n 2 + 3n+ 1 or n 3 > 3n 2 + 3n + 1. Given the inequality (2 n > n 3 ), we get 2 n+1 = 2 n·2 = 2 n + 2 n > n 3 + n 3 > n 3 + 3n 2 + 3n + 1 = (n + 1) 3 .

Thus, according to the method of mathematical induction, for any natural n ABOUT N, n≥ 10 we have 2 n > n 3 .

Example 3. Prove that for anyone n ABOUT N

Solution. a) P(1) is a true statement (0 is divided by 6). Let P(n) is fair, that is n(2n 2 - 3n + 1) = n(n - 1)(2n- 1) is divisible by 6. Let us show that then it occurs P(n+ 1), that is, ( n + 1)n(2n+ 1) is divisible by 6. Indeed, since

And How n(n - 1)(2 n- 1), and 6 n 2 are divisible by 6, then their sum isn(n + 1)(2 n+ 1) is divisible by 6.

Thus, P(n+ 1) is a fair statement, and therefore n(2n 2 - 3n+ 1) divisible by 6 for any n ABOUT N.

b) Let's check P(1): 6 0 + 3 2 + 3 0 = 11, therefore, P(1) is a fair statement. It should be proven that if 6 2 n-2 + 3 n+1 + 3 n-1 is divided by 11 ( P(n)), then 6 2 n + 3 n+2 + 3 n also divisible by 11 ( P(n+ 1)). Indeed, since

6 2n + 3 n+2 + 3 n = 6 2n-2+2 + 3 n+1+1 + 3 n-1+1 = = 6 2 6 2 n-2 + 3 3 n+1 + 3 3 n-1 = 3·(6 2 n-2 + 3 n+1 + 3 n-1) + 33 6 2 n-2 and like 6 2 n-2 + 3 n+1 + 3 n-1 and 33 6 2 n-2 are divisible by 11, then their sum is 6 2n + 3 n+2 + 3 n is divisible by 11. The statement is proven. Induction in geometry

Example 4. Calculate side of correct 2 n-a triangle inscribed in a circle of radius R.

Lecture 6. Method of mathematical induction.

We will calculate the value of the trinomial for some first values n:

6.1. The principle of mathematical induction.

♦ The method of mathematical induction is based on principle of mathematical induction , which is as follows:

1) the validity of this statement is checked forn=1 (induction basis) ,

2) the validity of this statement is assumed forn= k, Wherek– arbitrary natural number 1(induction assumption) , and taking this assumption into account, its validity is established forn= k+1.

Proof. Let us assume the opposite, that is, suppose that the statement is not true for every natural n. Then there is such a natural m, What:

1) statement for n=m not fair,

2) for everyone n, smaller m, the statement is true (in other words, m is the first natural number for which the statement is not true).

Note that the proof used the axiom that any collection of natural numbers contains the smallest number.

A proof based on the principle of mathematical induction is called by the method of complete mathematical induction .

 Example6.1. Prove that for any natural n number
divisible by 3.

Solution.

1) When n=1, so a 1 is divisible by 3 and the statement is true when n=1.

2) Suppose that the statement is true for n=k,
, that is, that number
is divisible by 3, and we establish that when n=k+1 number is divisible by 3.

Indeed,

Because Each term is divisible by 3, then their sum is also divisible by 3. ■ 

 Example6.2. Prove that the sum of the first n natural odd numbers is equal to the square of their number, that is.

Solution. Let's use the method of complete mathematical induction.

1) We check the validity of this statement when n=1: 1=1 2 – this is true.

We use our assumption and get

. ■ 

The method of complete mathematical induction is used to prove some inequalities. Let us prove Bernoulli's inequality.

 Example6.3. Prove that when
and any natural n inequality is true
(Bernoulli's inequality).

Solution. 1) When n=1 we get
, which is true.

2) We assume that when n=k there is inequality
(*). Using this assumption, we prove that
. Note that when
this inequality holds and therefore it suffices to consider the case
.

Let's multiply both sides of the inequality (*) by the number
and we get:

That is (1+
. ■ 

Proof by method incomplete mathematical induction some statement depending on n, Where
carried out in a similar way, but at the beginning fairness is established for the smallest value n.

 Example6.4. Find the amount
.

1) When n=1 hypothesis is correct, because
.

2) Suppose that the hypothesis is true for n=k,
, that is
. Using this formula, we establish that the hypothesis is true even when n=k+1, that is

Indeed,

This proves the statement and we will use it further. ■ 

 Example6.6. Find all natural n, for which the inequality is true

1) As was established above, this hypothesis is true when n=5.

2) Assume that it is true for n=k,
, that is, the inequality is true
. Using this assumption, we prove that the inequality
.

Because
and at
there is inequality

at
,

then we get that
. So, the truth of the hypothesis at n=k+1 follows from the assumption that it is true when n=k,
.

From paragraphs. 1 and 2, based on the principle of incomplete mathematical induction, it follows that the inequality
true for every natural
. ■ 

 Example6.7. Prove that for any natural number n the differentiation formula is valid
.

Solution. At n=1 this formula looks like
, or 1=1, that is, it is correct. Making the induction assumption, we have:

Q.E.D. ■ 

 Example6.8. Prove that the set consisting of n elements, has subsets

Solution. A set consisting of one element A, has two subsets. This is true because all its subsets are the empty set and the empty set itself, and 2 1 =2.

The set B consists of n elements, and therefore, by induction, he has subsets, so in the first class subsets

But in the second class there are the same number of subsets: each of them is obtained from exactly one subset of the first class by adding an element d. Therefore, in total the set A
subsets

Thus the statement is proven. Note that it is also true for a set consisting of 0 elements - the empty set: it has a single subset - itself, and 2 0 = 1. ■ 

One of the most important methods of mathematical proof is rightfully method of mathematical induction. The vast majority of formulas relating to all natural numbers n can be proven by the method of mathematical induction (for example, the formula for the sum of the first n terms of an arithmetic progression, Newton's binomial formula, etc.).

In this article, we will first dwell on the basic concepts, then consider the method of mathematical induction itself and analyze examples of its application in proving equalities and inequalities.

Page navigation.

Induction and deduction.

By induction called the transition from particular statements to general ones. On the contrary, the transition from general statements to specific ones is called deduction.

An example of a particular statement: 254 is divisible by 2 without a remainder.

From this particular statement one can formulate a lot of more general statements, both true and false. For example, the more general statement that all integers ending in four are divisible by 2 without a remainder is true, but the statement that all three-digit numbers are divisible by 2 without a remainder is false.

Thus, induction allows us to obtain many general statements based on known or obvious facts. And the method of mathematical induction is designed to determine the validity of the obtained statements.

As an example, consider the number sequence: , n is an arbitrary natural number. Then the sequence of sums of the first n elements of this sequence will be as follows

Based on this fact, it can be argued by induction that .

We present the proof of this formula.

Method of mathematical induction.

The method of mathematical induction is based on principle of mathematical induction.

It is as follows: a certain statement is true for every natural number n if

it is valid for n = 1 and
from the validity of the statement for any arbitrary natural number n = k, it follows that it is valid for n = k+1.

That is, the proof using the method of mathematical induction is carried out in three stages:

firstly, the validity of the statement will be checked for any natural number n (usually the check is done for n = 1);
secondly, the validity of the statement is assumed for any natural number n=k;
thirdly, the validity of the statement for the number n=k+1 is proved, starting from the assumption of the second point.

Examples of proofs of equations and inequalities using the method of mathematical induction.

Let's return to the previous example and prove the formula .

Proof.

The method of mathematical induction involves a three-point proof.

Thus, all three steps of the method of mathematical induction have been completed and our assumption about the formula has been proven.

Let's look at a trigonometry problem.

Example.

Prove the identity .

Solution.

First, we check the validity of the equality for n = 1. To do this, we will need basic trigonometry formulas.

That is, the equality is true for n = 1.

Secondly, suppose that the equality is true for n = k, that is, the identity is true

Method of mathematical induction

Introduction

Main part

Complete and incomplete induction
Principle of mathematical induction
Method of mathematical induction
Solving Examples
Equalities
Dividing numbers
Inequalities

Conclusion

List of used literature

Introduction

The basis of any mathematical research is deductive and inductive methods. The deductive method of reasoning is reasoning from the general to the specific, i.e. reasoning, the starting point of which is the general result, and the final point is the particular result. Induction is used when moving from particular results to general ones, i.e. is the opposite of deductive method.

The method of mathematical induction can be compared to progress. We start from the lowest, and as a result of logical thinking we come to the highest. Man has always strived for progress, for the ability to develop his thoughts logically, which means that nature itself destined him to think inductively.

Although the scope of application of the method of mathematical induction has grown, little time is devoted to it in the school curriculum. Well, tell me that those two or three lessons will be useful to a person, during which he will hear five words of theory, solve five primitive problems, and, as a result, will receive an A for the fact that he knows nothing.

But it is so important to be able to think inductively.

Main part

In its original meaning, the word “induction” is applied to reasoning through which general conclusions are obtained based on a number of specific statements. The simplest method of reasoning of this kind is complete induction. Here is an example of such reasoning.

Let it be necessary to establish that every even natural number n within 4< n < 20 представимо в виде суммы двух простых чисел. Для этого возьмём все такие числа и выпишем соответствующие разложения:

4=2+2; 6=3+3; 8=5+3; 10=7+3; 12=7+5;

14=7+7; 16=11+5; 18=13+5; 20=13+7.

These nine equalities show that each of the numbers we are interested in is indeed represented as the sum of two simple terms.

Thus, complete induction consists of proving the general statement separately in each of a finite number of possible cases.

Sometimes the general result can be predicted after considering not all, but a sufficiently large number of particular cases (the so-called incomplete induction).

The result obtained by incomplete induction remains, however, only a hypothesis until it is proven by precise mathematical reasoning, covering all special cases. In other words, incomplete induction in mathematics is not considered a legitimate method of rigorous proof, but is a powerful method for discovering new truths.

Let, for example, you want to find the sum of the first n consecutive odd numbers. Let's consider special cases:

1+3+5+7+9=25=5 2

After considering these few special cases, the following general conclusion suggests itself:

1+3+5+…+(2n-1)=n 2

those. the sum of the first n consecutive odd numbers is n 2

Of course, the observation made cannot yet serve as proof of the validity of the given formula.

Complete induction has only limited applications in mathematics. Many interesting mathematical statements cover an infinite number of special cases, but we are not able to test them for an infinite number of cases. Incomplete induction often leads to erroneous results.

In many cases, the way out of this kind of difficulty is to resort to a special method of reasoning, called the method of mathematical induction. It is as follows.

Suppose you need to prove the validity of a certain statement for any natural number n (for example, you need to prove that the sum of the first n odd numbers is equal to n 2). Direct verification of this statement for each value of n is impossible, since the set of natural numbers is infinite. To prove this statement, first check its validity for n=1. Then they prove that for any natural value of k, the validity of the statement under consideration for n=k implies its validity for n=k+1.

Then the statement is considered proven for all n. In fact, the statement is true for n=1. But then it is also true for the next number n=1+1=2. The validity of the statement for n=2 implies its validity for n=2+

1=3. This implies the validity of the statement for n=4, etc. It is clear that, in the end, we will reach any natural number n. This means that the statement is true for any n.

Summarizing what has been said, we formulate the following general principle.

The principle of mathematical induction.

If a sentence A(n), depending on a natural number n, is true for n=1 and from the fact that it is true for n=k (where k is any natural number), it follows that it is also true for the next number n=k +1, then assumption A(n) is true for any natural number n.

In a number of cases, it may be necessary to prove the validity of a certain statement not for all natural numbers, but only for n>p, where p is a fixed natural number. In this case, the principle of mathematical induction is formulated as follows.

If the proposition A(n) is true for n=p and if A(k)ÞA(k+1) for any k>p, then the proposition A(n) is true for any n>p.

The proof using the method of mathematical induction is carried out as follows. First, the statement to be proved is checked for n=1, i.e. the truth of statement A(1) is established. This part of the proof is called the induction basis. Then comes the part of the proof called the induction step. In this part, they prove the validity of the statement for n=k+1 under the assumption of the validity of the statement for n=k (induction assumption), i.e. prove that A(k)ÞA(k+1).

Prove that 1+3+5+…+(2n-1)=n 2.

Solution: 1) We have n=1=1 2 . Hence,

the statement is true for n=1, i.e. A(1) is true.

2) Let us prove that A(k)ÞA(k+1).

Let k be any natural number and let the statement be true for n=k, i.e.

1+3+5+…+(2k-1)=k 2 .

Let us prove that then the statement is also true for the next natural number n=k+1, i.e. What

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

Indeed,

1+3+5+…+(2k-1)+(2k+1)=k 2 +2k+1=(k+1) 2 .

So, A(k)ÞA(k+1). Based on the principle of mathematical induction, we conclude that assumption A(n) is true for any nÎN.

Prove that

1+x+x 2 +x 3 +…+x n =(x n+1 -1)/(x-1), where x¹1

Solution: 1) For n=1 we get

1+x=(x 2 -1)/(x-1)=(x-1)(x+1)/(x-1)=x+1

therefore, for n=1 the formula is correct; A(1) is true.

2) Let k be any natural number and let the formula be true for n=k, i.e.

1+x+x 2 +x 3 +…+x k =(x k+1 -1)/(x-1).

Let us prove that then the equality

1+x+x 2 +x 3 +…+x k +x k+1 =(x k+2 -1)/(x-1).

Indeed

1+x+x 2 +x 3 +…+x k +x k+1 =(1+x+x 2 +x 3 +…+x k)+x k+1 =

=(x k+1 -1)/(x-1)+x k+1 =(x k+2 -1)/(x-1).

So, A(k)ÞA(k+1). Based on the principle of mathematical induction, we conclude that the formula is true for any natural number n.

Prove that the number of diagonals of a convex n-gon is equal to n(n-3)/2.

Solution: 1) For n=3 the statement is true

And 3 is meaningful, because in a triangle

 A 3 =3(3-3)/2=0 diagonals;

A 2 A(3) is true.

2) Let us assume that in every

a convex k-gon has-

A 1 x A k =k(k-3)/2 diagonals.

And k Let us prove that then in a convex

(k+1)-gon number

diagonals A k+1 =(k+1)(k-2)/2.

Let A 1 A 2 A 3 …A k A k+1 be a convex (k+1)-gon. Let's draw a diagonal A 1 A k in it. To calculate the total number of diagonals of this (k+1)-gon, you need to count the number of diagonals in the k-gon A 1 A 2 ...A k , add k-2 to the resulting number, i.e. the number of diagonals of the (k+1)-gon emanating from the vertex A k+1, and, in addition, the diagonal A 1 A k should be taken into account.

Thus,

 k+1 = k +(k-2)+1=k(k-3)/2+k-1=(k+1)(k-2)/2.

So, A(k)ÞA(k+1). Due to the principle of mathematical induction, the statement is true for any convex n-gon.

Prove that for any n the following statement is true:

1 2 +2 2 +3 2 +…+n 2 =n(n+1)(2n+1)/6.

Solution: 1) Let n=1, then

X 1 =1 2 =1(1+1)(2+1)/6=1.

This means that for n=1 the statement is true.

2) Assume that n=k

X k =k 2 =k(k+1)(2k+1)/6.

3) Consider this statement for n=k+1

X k+1 =(k+1)(k+2)(2k+3)/6.

X k+1 =1 2 +2 2 +3 2 +…+k 2 +(k+1) 2 =k(k+1)(2k+1)/6+ +(k+1) 2 =(k (k+1)(2k+1)+6(k+1) 2)/6=(k+1)(k(2k+1)+

6(k+1))/6=(k+1)(2k 2 +7k+6)/6=(k+1)(2(k+3/2)(k+

2))/6=(k+1)(k+2)(2k+3)/6.

We have proven the equality to be true for n=k+1, therefore, by virtue of the method of mathematical induction, the statement is true for any natural number n.

Prove that for any natural number n the equality is true:

1 3 +2 3 +3 3 +…+n 3 =n 2 (n+1) 2 /4.

Solution: 1) Let n=1.

Then X 1 =1 3 =1 2 (1+1) 2 /4=1.

We see that for n=1 the statement is true.

2) Suppose that the equality is true for n=k

X k =k 2 (k+1) 2 /4.

3) Let us prove the truth of this statement for n=k+1, i.e.

X k+1 =(k+1) 2 (k+2) 2 /4. X k+1 =1 3 +2 3 +…+k 3 +(k+1) 3 =k 2 (k+1) 2 /4+(k+1) 3 =(k 2 (k++1) 2 +4(k+1) 3)/4=(k+1) 2 (k 2 +4k+4)/4=(k+1) 2 (k+2) 2 /4.

From the above proof it is clear that the statement is true for n=k+1, therefore, the equality is true for any natural number n.

Prove that

((2 3 +1)/(2 3 -1))´((3 3 +1)/(3 3 -1))´…´((n 3 +1)/(n 3 -1))= 3n(n+1)/2(n 2 +n+1), where n>2.

Solution: 1) For n=2 the identity looks like: (2 3 +1)/(2 3 -1)=(3´2´3)/2(2 2 +2+1),

those. it's true.

2) Assume that the expression is true for n=k

(2 3 +1)/(2 3 -1)´…´(k 3 +1)/(k 3 -1)=3k(k+1)/2(k 2 +k+1).

3) Let us prove the correctness of the expression for n=k+1.

(((2 3 +1)/(2 3 -1))´…´((k 3 +1)/(k 3 -1)))´(((k+1) 3 +

1)/((k+1) 3 -1))=(3k(k+1)/2(k 2 +k+1))´((k+2)((k+

1) 2 -(k+1)+1)/k((k+1) 2 +(k+1)+1))=3(k+1)(k+2)/2´

´((k+1) 2 +(k+1)+1).

We have proven the equality to be true for n=k+1, therefore, by virtue of the method of mathematical induction, the statement is true for any n>2

Prove that

1 3 -2 3 +3 3 -4 3 +…+(2n-1) 3 -(2n) 3 =-n 2 (4n+3)

for any natural n.

Solution: 1) Let n=1, then

1 3 -2 3 =-1 3 (4+3); -7=-7.

2) Suppose that n=k, then

1 3 -2 3 +3 3 -4 3 +…+(2k-1) 3 -(2k) 3 =-k 2 (4k+3).

3) Let us prove the truth of this statement for n=k+1

(1 3 -2 3 +…+(2k-1) 3 -(2k) 3)+(2k+1) 3 -(2k+2) 3 =-k 2 (4k+3)+

+(2k+1) 3 -(2k+2) 3 =-(k+1) 3 (4(k+1)+3).

The validity of the equality for n=k+1 has also been proven, therefore the statement is true for any natural number n.

Prove the identity is correct

(1 2 /1´3)+(2 2 /3´5)+…+(n 2 /(2n-1)´(2n+1))=n(n+1)/2(2n+1)

for any natural n.

1) For n=1 the identity is true 1 2 /1´3=1(1+1)/2(2+1).

2) Suppose that for n=k

(1 2 /1´3)+…+(k 2 /(2k-1)´(2k+1))=k(k+1)/2(2k+1).

3) Let us prove that the identity is true for n=k+1.

(1 2 /1´3)+…+(k 2 /(2k-1)(2k+1))+(k+1) 2 /(2k+1)(2k+3)=(k(k+ 1)/2(2k+1))+((k+1) 2 /(2k+1)(2k+3))=((k+1)/(2k+1))´((k/2 )+((k+1)/(2k+3)))=(k+1)(k+2)´ (2k+1)/2(2k+1)(2k+3)=(k+1 )(k+2)/2(2(k+1)+1).

From the above proof it is clear that the statement is true for any natural number n.

Prove that (11 n+2 +12 2n+1) is divisible by 133 without a remainder.

Solution: 1) Let n=1, then

11 3 +12 3 =(11+12)(11 2 -132+12 2)=23´133.

But (23´133) is divisible by 133 without a remainder, which means that for n=1 the statement is true; A(1) is true.

2) Suppose that (11 k+2 +12 2k+1) is divisible by 133 without a remainder.

3) Let us prove that in this case

(11 k+3 +12 2k+3) is divisible by 133 without a remainder. Indeed, 11 k+3 +12 2l+3 =11´11 k+2 +12 2´ 12 2k+1 =11´11 k+2 +

+(11+133)´12 2k+1 =11(11 k+2 +12 2k+1)+133´12 2k+1 .

The resulting sum is divided by 133 without a remainder, since its first term is divisible by 133 without a remainder by assumption, and in the second one of the factors is 133. So, A(k)ÞA(k+1). By virtue of the method of mathematical induction, the statement has been proven.

Prove that for any n 7 n -1 is divisible by 6 without a remainder.

Solution: 1) Let n=1, then X 1 =7 1 -1=6 is divided by 6 without a remainder. This means that when n=1 the statement is true.

2) Suppose that for n=k

7 k -1 is divisible by 6 without a remainder.

3) Let us prove that the statement is true for n=k+1.

X k+1 =7 k+1 -1=7´7 k -7+6=7(7 k -1)+6.

The first term is divisible by 6, since 7 k -1 is divisible by 6 by assumption, and the second term is 6. This means 7 n -1 is a multiple of 6 for any natural n. By virtue of the method of mathematical induction, the statement is proven.

Prove that 3 3n-1 +2 4n-3 for an arbitrary natural n is divisible by 11.
Solution: 1) Let n=1, then

X 1 =3 3-1 +2 4-3 =3 2 +2 1 =11 is divided by 11 without a remainder. This means that for n=1 the statement is true.

2) Suppose that for n=k

X k =3 3k-1 +2 4k-3 is divisible by 11 without a remainder.

3) Let us prove that the statement is true for n=k+1.

X k+1 =3 3(k+1)-1 +2 4(k+1)-3 =3 3k+2 +2 4k+1 =3 3´ 3 3k-1 +2 4´ 2 4k-3 =

27´3 3k-1 +16´2 4k-3 =(16+11)´3 3k-1 +16´2 4k-3 =16´3 3k-1 +

11´3 3k-1 +16´2 4k-3 =16(3 3k-1 +2 4k-3)+11´3 3k-1 .

The first term is divisible by 11 without a remainder, since 3 3k-1 +2 4k-3 is divisible by 11 by assumption, the second is divisible by 11, because one of its factors is the number 11. This means that the sum is divisible by 11 without remainder for any natural number n. By virtue of the method of mathematical induction, the statement is proven.

Prove that 11 2n -1 for an arbitrary natural n is divisible by 6 without a remainder.

Solution: 1) Let n=1, then 11 2 -1=120 is divisible by 6 without a remainder. This means that when n=1 the statement is true.

2) Suppose that for n=k

11 2k -1 is divisible by 6 without a remainder.

11 2(k+1) -1=121´11 2k -1=120´11 2k +(11 2k -1).

Both terms are divisible by 6 without a remainder: the first contains a multiple of 6, the number 120, and the second is divisible by 6 without a remainder by assumption. This means that the sum is divisible by 6 without a remainder. By virtue of the method of mathematical induction, the statement is proven.

Prove that 3 3n+3 -26n-27 for an arbitrary natural number n is divisible by 26 2 (676) without a remainder.

Solution: First we prove that 3 3n+3 -1 is divisible by 26 without a remainder.

When n=0

3 3 -1=26 is divided by 26

Let's assume that for n=k

3 3k+3 -1 is divisible by 26

Let us prove that the statement

true for n=k+1.

3 3k+6 -1=27´3 3k+3 -1=26´3 3л+3 +(3 3k+3 -1) – divided by 26

Now let’s carry out the proof of the statement formulated in the problem statement.

1) Obviously, when n=1 the statement is true

3 3+3 -26-27=676

2) Suppose that for n=k

the expression 3 3k+3 -26k-27 is divided by 26 2 without a remainder.

3) Let us prove that the statement is true for n=k+1

3 3k+6 -26(k+1)-27=26(3 3k+3 -1)+(3 3k+3 -26k-27).

Both terms are divisible by 26 2; the first is divisible by 26 2 because we have proven the expression in parentheses is divisible by 26, and the second is divisible by the induction hypothesis. By virtue of the method of mathematical induction, the statement is proven.

Prove that if n>2 and x>0, then the inequality is true

(1+x) n >1+n´x.

Solution: 1) For n=2 the inequality is valid, since

(1+x) 2 =1+2x+x 2 >1+2x.

So A(2) is true.

2) Let us prove that A(k)ÞA(k+1), if k> 2. Assume that A(k) is true, i.e., that the inequality

(1+x) k >1+k´x. (3)

Let us prove that then A(k+1) is also true, i.e., that the inequality

(1+x) k+1 >1+(k+1)´x.

In fact, multiplying both sides of inequality (3) by the positive number 1+x, we obtain

(1+x) k+1 >(1+k´x)(1+x).

Let us consider the right-hand side of the last inequality

stva; we have

(1+k´x)(1+x)=1+(k+1)´x+k´x 2 >1+(k+1)´x.

As a result, we get that

(1+x) k+1 >1+(k+1)´x.

So, A(k)ÞA(k+1). Based on the principle of mathematical induction, it can be argued that Bernoulli’s inequality is true for any

Prove that the inequality is true

(1+a+a 2) m > 1+m´a+(m(m+1)/2)´a 2 for a> 0.

Solution: 1) When m=1

(1+a+a 2) 1 > 1+a+(2/2)´a 2 both sides are equal.

2) Suppose that for m=k

(1+a+a 2) k >1+k´a+(k(k+1)/2)´a 2

3) Let us prove that for m=k+1 the inequality is true

(1+a+a 2) k+1 =(1+a+a 2)(1+a+a 2) k >(1+a+a 2)(1+k´a+

+(k(k+1)/2)´a 2)=1+(k+1)´a+((k(k+1)/2)+k+1)´a 2 +

+((k(k+1)/2)+k)´a 3 +(k(k+1)/2)´a 4 > 1+(k+1)´a+

+((k+1)(k+2)/2)´a 2 .

We have proven the validity of the inequality for m=k+1, therefore, by virtue of the method of mathematical induction, the inequality is valid for any natural m.

Prove that for n>6 the inequality is true

3 n >n´2 n+1 .

Solution: Let's rewrite the inequality in the form

For n=7 we have

3 7 /2 7 =2187/128>14=2´7

the inequality is true.

Let's assume that for n=k

3) Let us prove the validity of the inequality for n=k+1.

3 k+1 /2 k+1 =(3 k /2 k)´(3/2)>2k´(3/2)=3k>2(k+1).

Since k>7, the last inequality is obvious.

By virtue of the method of mathematical induction, the inequality is valid for any natural number n.

Prove that for n>2 the inequality is true

1+(1/2 2)+(1/3 2)+…+(1/n 2)<1,7-(1/n).

Solution: 1) For n=3 the inequality is true

1+(1/2 2)+(1/3 2)=245/180<246/180=1,7-(1/3).

Let's assume that for n=k

1+(1/2 2)+(1/3 2)+…+(1/k 2)=1.7-(1/k).

3) Let us prove the validity of the non-

equality for n=k+1

(1+(1/2 2)+…+(1/k 2))+(1/(k+1) 2)<1,7-(1/k)+(1/(k+1) 2).

Let us prove that 1.7-(1/k)+(1/(k+1) 2)<1,7-(1/k+1)Û

Û(1/(k+1) 2)+(1/k+1)<1/kÛ(k+2)/(k+1) 2 <1/kÛ

Ûk(k+2)<(k+1) 2Û k 2 +2k

The latter is obvious, and therefore

1+(1/2 2)+(1/3 2)+…+(1/(k+1) 2)<1,7-(1/k+1).

By virtue of the method of mathematical induction, the inequality is proven.

Conclusion

In particular, by studying the method of mathematical induction, I increased my knowledge in this area of mathematics, and also learned to solve problems that were previously beyond my power.

These were mainly logical and entertaining tasks, i.e. just those that increase interest in mathematics itself as a science. Solving such problems becomes an entertaining activity and can attract more and more curious people into mathematical labyrinths. In my opinion, this is the basis of any science.

Continuing to study the method of mathematical induction, I will try to learn how to apply it not only in mathematics, but also in solving problems in physics, chemistry and life itself.

MATHEMATICS:

LECTURES, PROBLEMS, SOLUTIONS

Textbook / V.G. Boltyansky, Yu.V. Sidorov, M.I. Shabunin. Potpourri LLC 1996.

ALGEBRA AND BEGINNINGS OF ANALYSIS

Textbook / I.T. Demidov, A.N. Kolmogorov, S.I. Shvartsburg, O.S. Ivashev-Musatov, B.E. Weitz. “Enlightenment” 1975.