Method of mathematical induction lesson notes. Examples - mathematical induction

METHOD OF MATHEMATICAL INDUCTION

The word induction in Russian means guidance, and conclusions based on observations, experiments, i.e. are called inductive. obtained by inference from the particular to the general.

For example, every day we observe that the Sun rises from the east. Therefore, you can be sure that tomorrow it will appear in the east, and not in the west. We draw this conclusion without resorting to any assumptions about the reason for the movement of the Sun across the sky (moreover, this movement itself turns out to be apparent, since the globe is actually moving). And yet this inductive conclusion correctly describes the observations we will make tomorrow.

The role of inductive conclusions in experimental sciences is very great. They give those provisions from which further conclusions are then drawn through deduction. And although theoretical mechanics is based on Newton’s three laws of motion, these laws themselves were the result of deep thinking through experimental data, in particular Kepler’s laws of planetary motion, which he derived from the processing of many years of observations by the Danish astronomer Tycho Brahe. Observation and induction turn out to be useful in the future for clarifying the assumptions made. After Michelson's experiments on measuring the speed of light in a moving medium, it turned out to be necessary to clarify the laws of physics and create the theory of relativity.

In mathematics, the role of induction is largely that it underlies the chosen axiomatics. After long-term practice showed that a straight path is always shorter than a curved or broken one, it was natural to formulate an axiom: for any three points A, B and C, the inequality

The concept of following, which is the basis of arithmetic, also appeared from observations of the formation of soldiers, ships and other ordered sets.

One should not, however, think that this exhausts the role of induction in mathematics. Of course, we should not experimentally test theorems logically deduced from axioms: if no logical errors were made during the derivation, then they are true insofar as the axioms we accepted are true. But a lot of statements can be deduced from this system of axioms. And the selection of those statements that need to be proven is again suggested by induction. It is this that allows you to separate useful theorems from useless ones, indicates which theorems may turn out to be true, and even helps to outline the path of proof.

The essence of the method of mathematical induction

In many branches of arithmetic, algebra, geometry, and analysis, it is necessary to prove the truth of sentences A(n) depending on a natural variable. The proof of the truth of the proposition A(n) for all values ​​of a variable can often be carried out by the method of mathematical induction, which is based on the following principle.

The proposition A(n) is considered true for all natural values ​​of the variable if the following two conditions are met:

Proposition A(n) is true for n=1.

From the assumption that A(n) is true for n=k (where k is any natural number), it follows that it is true for the next value n=k+1.

This principle is called the principle of mathematical induction. It is usually chosen as one of the axioms defining the natural series of numbers, and is therefore accepted without proof.

The method of mathematical induction means the following method of proof. If you want to prove the truth of a sentence A(n) for all natural n, then, firstly, you should check the truth of the statement A(1) and, secondly, assuming the truth of the statement A(k), try to prove that the statement A(k +1) true. If this can be proven, and the proof remains valid for each natural value of k, then, in accordance with the principle of mathematical induction, the proposition A(n) is recognized as true for all values ​​of n.

The method of mathematical induction is widely used in proving theorems, identities, inequalities, in solving divisibility problems, in solving some geometric and many other problems.

The method of mathematical induction in solving problems on

divisibility

Using the method of mathematical induction, you can prove various statements regarding the divisibility of natural numbers.

The following statement can be proven relatively simply. Let us show how it is obtained using the method of mathematical induction.

Example 1. If n is a natural number, then the number is even.

When n=1 our statement is true: - an even number. Let's assume that it is an even number. Since , a 2k is an even number, then even. So, parity is proven for n=1, parity is deduced from parity .This means that it is even for all natural values ​​of n.

Example 2.Prove the truth of the sentence

A(n)=(the number 5 is a multiple of 19), n is a natural number.

Solution.

The statement A(1)=(a number divisible by 19) is true.

Suppose that for some value n=k

A(k)=(number divisible by 19) is true. Then, since

Obviously, A(k+1) is also true. Indeed, the first term is divisible by 19 due to the assumption that A(k) is true; the second term is also divisible by 19 because it contains a factor of 19. Both conditions of the principle of mathematical induction are satisfied, therefore, the proposition A(n) is true for all values ​​of n.

Application of the method of mathematical induction to

summing series

Example 1.Prove formula

, n is a natural number.

Solution.

When n=1, both sides of the equality turn to one and, therefore, the first condition of the principle of mathematical induction is satisfied.

Let's assume that the formula is correct for n=k, i.e.

.

Let's add to both sides of this equality and transform the right side. Then we get

Thus, from the fact that the formula is true for n=k, it follows that it is also true for n=k+1. This statement is true for any natural value of k. So, the second condition of the principle of mathematical induction is also satisfied. The formula is proven.

Example 2.Prove that the sum of the first n numbers of the natural series is equal to .

Solution.

Let us denote the required amount, i.e. .

When n=1 the hypothesis is true.

Let . Let's show that .

Indeed,

The problem is solved.

Example 3.Prove that the sum of the squares of the first n numbers of the natural series is equal to .

Solution.

Let .

.

Let's pretend that . Then

And finally.

Example 4. Prove that .

Solution.

If , then

Example 5. Prove that

Solution.

When n=1 the hypothesis is obviously true.

Let .

Let's prove that .

Really,

Examples of applying the method of mathematical induction to

proof of inequalities

Example 1.Prove that for any natural number n>1

.

Solution.

Let us denote the left side of the inequality by .

Therefore, for n=2 the inequality is true.

Let for some k. Let us prove that then and . We have , .

Comparing and , we have , i.e. .

For any positive integer k, the right-hand side of the last equality is positive. That's why . But that means also.

Example 2.Find the error in the reasoning.

Statement. For any natural number n the inequality is true.

Proof.

. (1)

Let us prove that then the inequality is also valid for n=k+1, i.e.

.

Indeed, no less than 2 for any natural k. Let's add to the left side of inequality (1) and to the right side 2. We get a fair inequality, or . The statement has been proven.

Example 3.Prove that , where >-1, , n is a natural number greater than 1.

Solution.

For n=2 the inequality is true, since .

Let the inequality be true for n=k, where k is some natural number, i.e.

. (1)

Let us show that then the inequality is also valid for n=k+1, i.e.

. (2)

Indeed, by condition, , therefore the inequality is true

, (3)

obtained from inequality (1) by multiplying each part by . Let us rewrite inequality (3) as follows: . Discarding the positive term on the right side of the last inequality, we obtain fair inequality (2).

Example 4. Prove that

(1)

where , , n is a natural number greater than 1.

Solution.

For n=2 inequality (1) takes the form

. (2)

Since , then the inequality is true

. (3)

By adding to each part of inequality (3) we obtain inequality (2).

This proves that for n=2 inequality (1) is true.

Let inequality (1) be true for n=k, where k is some natural number, i.e.

. (4)

Let us prove that then inequality (1) must also be true for n=k+1, i.e.

(5)

Let's multiply both sides of inequality (4) by a+b. Since, by condition, , we obtain the following fair inequality:

. (6)

In order to prove the validity of inequality (5), it is enough to show that

, (7)

or, what is the same,

. (8)

Inequality (8) is equivalent to inequality

. (9)

If , then , and on the left side of inequality (9) we have the product of two positive numbers. If , then , and on the left side of inequality (9) we have the product of two negative numbers. In both cases, inequality (9) is true.

This proves that the validity of inequality (1) for n=k implies its validity for n=k+1.

Method of mathematical induction applied to others

tasks

The most natural application of the method of mathematical induction in geometry, close to the use of this method in number theory and algebra, is its application to solving geometric calculation problems. Let's look at a few examples.

Example 1.Calculate the side of a regular square inscribed in a circle of radius R.

Solution.

When n=2 correct 2 n - a square is a square; his side. Further, according to the doubling formula

we find that the side of a regular octagon , side of a regular hexagon , side of a regular thirty-two triangle . We can therefore assume that the side of the correct inscribed 2 n - square for any equal

. (1)

Let us assume that the side of a regular inscribed square is expressed by formula (1). In this case, according to the doubling formula

,

whence it follows that formula (1) is valid for all n.

Example 2.How many triangles can an n-gon (not necessarily convex) be divided into by its disjoint diagonals?

Solution.

For a triangle, this number is equal to one (not a single diagonal can be drawn in a triangle); for a quadrilateral this number is obviously two.

Suppose we already know that every k-gon, where k 1 A 2 ...A n into triangles.

A n

A 1 A 2

Let A 1 A k be one of the diagonals of this partition; it divides the n-gon A 1 A 2 ...A n into the k-gon A 1 A 2 ...A k and the (n-k+2)-gon A 1 A k A k+1 ...A n . Due to the assumption made, the total number of triangles in the partition will be equal to

(k-2)+[(n-k+2)-2]=n-2;

Thus, our statement is proven for all n.

Example 3.State the rule for calculating the number P(n) of ways in which a convex n-gon can be divided into triangles by disjoint diagonals.

Solution.

For a triangle, this number is obviously equal to one: P(3)=1.

Let us assume that we have already determined the numbers P(k) for all k 1 A 2 ...A n . Whenever it is divided into triangles, side A 1 A 2 will be a side of one of the partition triangles, the third vertex of this triangle can coincide with each of the points A 3, A 4, …, A n . The number of ways to partition an n-gon in which this vertex coincides with point A 3 , is equal to the number of ways of dividing the (n-1)-gon A into triangles 1 A 3 A 4 …A n , i.e. equals P(n-1). The number of partitioning methods in which this vertex coincides with A 4 , is equal to the number of ways to partition the (n-2)-gon A 1 A 4 A 5 …A n , i.e. equals P(n-2)=P(n-2)P(3); number of partitioning methods in which it coincides with A 5 , is equal to P(n-3)P(4), since each of the partitions of the (n-3)-gon A 1 A 5 ...A n can be combined with each of the partitions of the quadrilateral A 2 A 3 A 4 A 5 , etc. Thus, we arrive at the following relationship:

Р(n)=P(n-1)+P(n-2)P(3)+P(n-3)P(4)+…+P(3)P(n-2)+P(n -1).

Using this formula we consistently obtain:

P(4)=P(3)+P(3)=2,

P(5)=P(4)+P(3)P(3)+P(4)+5,

P(6)=P(5)+P(4)P(3)+P(3)P(4)+P(5)=14

etc.

You can also solve problems with graphs using the method of mathematical induction.

Let there be a network of lines on the plane that connect some points and have no other points. We will call such a network of lines a map, given points as its vertices, segments of curves between two adjacent vertices - the boundaries of the map, parts of the plane into which it is divided by borders - the countries of the map.

Let some map be given on the plane. We will say that it is correctly colored if each of its countries is painted with a certain color, and any two countries that have a common border are painted with different colors.

Example 4.There are n circles on the plane. Prove that for any arrangement of these circles, the map they form can be correctly colored with two colors.

Solution.

For n=1 our statement is obvious.

Let us assume that our statement is true for any map formed by n circles, and let there be n+1 circles on the plane. By removing one of these circles, we get a map that, by virtue of the assumption made, can be correctly colored with two colors, for example, black and white.

Savelyeva Ekaterina

The paper discusses the application of the method of mathematical induction in solving divisibility problems and summing series. Examples of applying the method of mathematical induction to proving inequalities and solving geometric problems are considered. The work is illustrated with a presentation.

Download:

Preview:

Ministry of Science and Education of the Russian Federation

State educational institution

secondary school No. 618

Course: algebra and beginnings of analysis

Topic of project work

“The method of mathematical induction and its application to problem solving”

Work completed: Savelyeva E, 11B class

Supervisor : Makarova T.P., mathematics teacher, secondary school No. 618

1. Introduction.

2.Method of mathematical induction in solving divisibility problems.

3. Application of the method of mathematical induction to the summation of series.

4. Examples of applying the method of mathematical induction to the proof of inequalities.

5. Application of the method of mathematical induction to solving geometric problems.

6. 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. But it is so important to be able to think inductively. The application of this principle in solving problems and proving theorems is on a par with the consideration in school practice of other mathematical principles: excluded middle, inclusion-exclusion, Dirichlet, etc. This abstract contains problems from different branches of mathematics, in which the main tool is the use method of mathematical induction. Speaking about the importance of this method, A.N. Kolmogorov noted that “understanding and ability to apply the principle of mathematical induction is a good criterion of maturity, which is absolutely necessary for a mathematician.” The method of induction in its broad sense consists in the transition from particular observations to a universal, general pattern or general formulation. In this interpretation, the method is, of course, the main method of conducting research in any experimental natural science.

human activity. The method (principle) of mathematical induction in its simplest form is used when it is necessary to prove a certain statement for all natural numbers.

Task 1. In his article “How I became a mathematician” A.N. Kolmogorov writes: “I learned the joy of a mathematical “discovery” early, having noticed a pattern at the age of five or six

1 =1 2 ,

1 + 3 = 2 2 ,

1 + 3 + 5 = 3 2,

1 + 3 + 5 + 7 = 4 2 and so on.

The school published the magazine "Spring Swallows". In it my discovery was published...”

We don’t know what kind of evidence was given in this journal, but it all started with private observations. The hypothesis itself, which probably arose after the discovery of these partial equalities, is that the formula

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

true for any given number n = 1, 2, 3, ...

To prove this hypothesis, it is enough to establish two facts. Firstly, for n = 1 (and even for n = 2, 3, 4) the desired statement is true. Secondly, suppose that the statement is true for p = k, and we will make sure that then it is also true for n = k + 1:

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

This means that the statement being proved is true for all values n: for n = 1 it is true (this has been verified), and due to the second fact - for n = 2, whence for n = 3 (due to the same, second fact), etc.

Problem 2. Consider all possible ordinary fractions with numerator 1 and any (positive integer)

(nominal) denominator: Prove that for any p> 3 we can represent the unit as a sum P various fractions of this type.

Solution, Let us first check this statement for n = 3; we have:

Therefore, the basic statement is satisfied

Let us now assume that the statement we are interested in is true for some number To, and prove that it is also true for the number following it To + 1. In other words, suppose that there is a representation

in which k terms and all denominators are different. Let us prove that then we can obtain a representation of unity as a sum from To + 1 fractions of the required type. We will assume that the fractions are decreasing, that is, the denominators (in the representation of the unit by the sum To terms) increase from left to right so that T - the largest of the denominators. We will get the representation we need in the form of a sum(To + 1)th fraction, if we split one fraction, for example the last one, into two. This can be done because

And therefore

In addition, all fractions remained different, since T was the largest denominator, and t + 1 > t, and

t(t + 1) > t.

Thus, we have established:

1. with n = 3 this statement is true;

1. if the statement we are interested in is true for To,
   then it is also true for k + 1.

On this basis, we can claim that the statement in question is true for all natural numbers, starting from three. Moreover, the above proof also implies an algorithm for finding the required partition of unity. (What algorithm is this? Imagine the number 1 as the sum of 4, 5, 7 terms on its own.)

In solving the previous two problems, two steps were taken. The first step is called basis induction, second -inductive transitionor step of induction. The second step is the most important, and it involves making an assumption (the statement is true when n = k) and conclusion (the statement is true when n = k + 1). The parameter n itself is called induction parameter.This logical scheme (technique), which allows us to conclude that the statement in question is true for all natural numbers (or for all, starting from some), since both the basis and the transition are valid, is calledthe principle of mathematical induction, on which The method of mathematical induction is based.The term “induction” itself comes from the Latin word induction (guidance), which means the transition from single knowledge about individual objects of a given class to a general conclusion about all objects of a given class, which is one of the main methods of cognition.

The principle of mathematical induction, precisely in the familiar form of two steps, first appeared in 1654 in Blaise Pascal’s “Treatise on the Arithmetic Triangle,” in which a simple way to calculate the number of combinations (binomial coefficients) was proved by induction. D. Polya quotes B. Pascal in the book with minor changes given in square brackets:

“Although the proposal in question [the explicit formula for binomial coefficients] contains countless special cases, I will give a very short proof for it, based on two lemmas.

The first lemma states that the assumption is true for the reason - this is obvious. [At P = 1 explicit formula is valid...]

The second lemma states the following: if our assumption is true for an arbitrary basis [for an arbitrary r], then it will be true for the following reason [for n + 1].

From these two lemmas it necessarily follows that the proposition is valid for all values P. Indeed, by virtue of the first lemma it is true for P = 1; therefore, by virtue of the second lemma, it is true for P = 2; therefore, again by virtue of the second lemma, it is valid for n = 3 and so on ad infinitum.”

Problem 3. The Towers of Hanoi puzzle consists of three rods. On one of the rods there is a pyramid (Fig. 1), consisting of several rings of different diameters, decreasing from bottom to top

Fig 1

This pyramid must be moved to one of the other rods, moving only one ring each time and not placing the larger ring on the smaller one. Is it possible to do this?

Solution. So, we need to answer the question: is it possible to move a pyramid consisting of P rings of different diameters, from one rod to another, following the rules of the game? Now we have, as they say, parametrized the problem (a natural number has been introduced into consideration P), and it can be solved by mathematical induction.

1. Induction base. When n = 1 everything is clear, since a pyramid of one ring can obviously be moved to any rod.
2. Induction step. Let's assume that we can move any pyramids with the number of rings p = k.
   Let us prove that then we can move the pyra midka from n = k + 1.

Pyramid from to rings lying on the largest(To + 1)-th ring, we can, according to the assumption, move it to any other rod. Let's do it. motionless(To + The 1)th ring will not prevent us from carrying out the movement algorithm, since it is the largest. After moving To rings, let's move this biggest one(To + 1)th ring on the remaining rod. And then again we apply the movement algorithm known to us by inductive assumption To rings, and move them to the rod with the one lying below(To + 1)th ring. Thus, if we know how to move pyramids with To rings, then we know how to move the pyramids and with To + 1 rings. Therefore, according to the principle of mathematical induction, it is always possible to move the pyramid consisting of n rings, where n > 1.

Method of mathematical induction in solving divisibility problems.

Using the method of mathematical induction, you can prove various statements regarding the divisibility of natural numbers.

Problem 4 . If n is a natural number, then the number is even.

When n=1 our statement is true: - an even number. Let's assume that it is an even number. Since a 2k is an even number, then it is even. So, parity is proven for n=1, parity is deduced from parity. This means that it is even for all natural values ​​of n.

Problem 3. Prove that the number Z 3 + 3 - 26n - 27 with arbitrary natural n is divisible by 26 2 without a remainder.

Solution. Let us first prove by induction the auxiliary statement that 3 3n+3 — 1 is divisible by 26 without a remainder when n > 0.

1. Induction base. For n = 0 we have: 3 3 - 1 = 26—divisible by 26.

Induction step. Let's assume that 3 3n+3 - 1 is divided by 26 when n = k, and Let us prove that in this case the statement will be true for n = k + 1. Since 3

then from the inductive hypothesis we conclude that the number 3 3k + 6 - 1 is divisible by 26.

Now we will prove the statement formulated in the problem statement. And again by induction.

1. Induction base. It is obvious that when n = 1 statement is true: since 3 3+3 - 26 - 27 = 676 = 26 2 .
2. Induction step. Let's assume that when p = k
   expression 3 3k + 3 - 26k - 27 is divided by 26 2 without remainder, and prove that the statement is true for n = k + 1,
   that is, that number

divisible by 26 2 without a trace. In the last sum, both terms are divisible by 26 2 . The first is because we have proven that the expression in parentheses is divisible by 26; the second is by the induction hypothesis. By virtue of the principle of mathematical induction, the desired statement is completely proven.

Application of the method of mathematical induction to the summation of series.

Task 5. Prove formula

N is a natural number.

Solution.

When n=1, both sides of the equality turn to one and, therefore, the first condition of the principle of mathematical induction is satisfied.

Let's assume that the formula is correct for n=k, i.e.

Let's add to both sides of this equality and transform the right side. Then we get

Thus, from the fact that the formula is true for n=k, it follows that it is also true for n=k+1. This statement is true for any natural value of k. So, the second condition of the principle of mathematical induction is also satisfied. The formula is proven.

Task 6. Two numbers are written on the board: 1,1. By entering their sum between the numbers, we get the numbers 1, 2, 1. Repeating this operation again, we get the numbers 1, 3, 2, 3, 1. After three operations, the numbers will be 1, 4, 3, 5, 2, 5, 3, 4, 1. What will be the sum of all the numbers on the board after 100 operations?

Solution. Do everything 100 operations would be a very labor-intensive and time-consuming task. This means we need to try to find some general formula for the sum S numbers after n operations. Let's look at the table:

Have you noticed any pattern here? If not, you can take one more step: after four operations there will be numbers

1, 5, 4, 7, 3, 8, 5, 7, 2, 7, 5, 8, 3, 7, 4, 5, 1,

the sum of which S 4 is equal to 82.

In fact, you can not write down the numbers, but immediately say how the sum will change after adding new numbers. Let the sum be equal to 5. What will it become when new numbers are added? Let's divide each new number into the sum of the two old ones. For example, from 1, 3, 2, 3, 1 we go to 1,

1 + 3, 3, 3 + 2, 2, 2 + 3, 3, 3 + 1, 1.

That is, each old number (except for the two extreme units) is now included in the sum three times, so the new sum is equal to 3S - 2 (subtract 2 to take into account the missing units). Therefore S 5 = 3S 4 - 2 = 244, and in general

What is the general formula? If it were not for the subtraction of two units, then each time the sum would increase three times, as in powers of three (1, 3, 9, 27, 81, 243, ...). And our numbers, as we can now see, are one more. Thus, it can be assumed that

Let us now try to prove this by induction.

Induction base. See table (for n = 0, 1, 2, 3).

Induction step. Let's pretend that

Let us then prove that S k + 1 = Z k + 1 + 1.

Really,

So, our formula is proven. It shows that after one hundred operations the sum of all numbers on the board will be equal to 3 100 + 1.

Let's look at one great example of applying the principle of mathematical induction, in which you first need to introduce two natural parameters and then carry out induction on their sum.

Task 7. Prove that if= 2, x 2 = 3 and for any natural p> 3 the relation holds

x p = 3x p - 1 - 2x p - 2,

That

2 p - 1 + 1, p = 1, 2, 3, ...

Solution. Note that in this problem the original sequence of numbers(x p) is determined by induction, since the terms of our sequence, except for the first two, are specified inductively, that is, through the previous ones. So given sequences are called recurrent, and in our case, this sequence is determined (by specifying its first two terms) in a unique way.

Induction base. It consists of checking two statements: when n = 1 and n = 2.V In both cases the statement is true by condition.

Induction step. Let's assume that for n = k - 1 and n = k the statement is fulfilled, that is

Let us then prove the validity of the statement for n = k + 1. We have:

x 1 = 3(2 + 1) - 2(2 + 1) = 2+1, which is what needed to be proven.

Task 8. Prove that any natural number can be represented as the sum of several different terms of the recurrent sequence of Fibonacci numbers:

for k > 2.

Solution. Let n - natural number. We will carry out induction on P.

Induction base. When n = Statement 1 is true since one itself is a Fibonacci number.

Induction step. Suppose that all natural numbers less than some number P, can be represented as the sum of several different terms of the Fibonacci sequence. Let's find the largest Fibonacci number Ft, not superior P; thus, F t p and F t +1 > p.

Because the

By the induction hypothesis, the number n- F t can be represented as the sum 5 of several different terms of the Fibonacci sequence, and from the last inequality it follows that all terms of the Fibonacci sequence involved in the sum 8 are less F t . Therefore, the expansion of the number n = 8 + F t satisfies the conditions of the problem.

Examples of applying the method of mathematical induction to proving inequalities.

Task 9. (Bernoulli's inequality.)Prove that when x > -1, x 0, and for integer n > 2 the inequality is true

(1 + x) n > 1 + xn.

Solution. We will again carry out the proof by induction.

1. Base of induction. Let us verify the validity of the inequality for n = 2. Indeed,

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

2. Induction step. Let's assume that for the number p = k the statement is true, that is

(1 + x) k > 1 + xk,

Where k > 2. Let's prove it for n = k + 1. We have: (1 + x) k + 1 = (1 + x) k (1 + x)>(1 + kx)(1 + x) =

1 + (k + 1)x + kx 2 > 1 + (k + 1)x.

So, based on the principle of mathematical induction, we can claim that Bernoulli’s inequality is true for any n > 2.

In the context of problems solved using the method of mathematical induction, the general law that needs to be proved is not always clearly formulated. Sometimes it is necessary, by observing particular cases, to first discover (guess) what general law they lead to, and only then prove the stated hypothesis by the method of mathematical induction. In addition, the induction variable can be masked, and before solving the problem, it is necessary to determine on what parameter the induction will be carried out. As examples, consider the following tasks.

Problem 10. Prove that

under any natural n > 1.

Solution, Let's try to prove this inequality using the method of mathematical induction.

The induction basis can be easily verified:1+

By the induction hypothesis

and it remains for us to prove that

If we use the inductive hypothesis, we will argue that

Although this equality is in fact true, it does not give us a solution to the problem.

Let's try to prove a stronger statement than required in the original problem. Namely, we will prove that

It may seem that proving this statement by induction is a hopeless matter.

However, when n = 1 we have: the statement is true. To justify the inductive step, let us assume that

and then we will prove that

Really,

Thus, we have proven a stronger statement, from which the statement contained in the statement of the problem immediately follows.

The instructive thing here is that although we had to prove a stronger statement than required in the problem, we could use a stronger assumption in the inductive step. This explains that the straightforward application of the principle of mathematical induction does not always lead to the goal.

The situation that arose when solving the problem was calledinventor's paradox.The paradox itself is that more complex plans can be implemented with greater success if they are based on a deeper understanding of the essence of the matter.

Problem 11. Prove that 2 m + n - 2 m for any natural type.

Solution. Here we have two parameters. Therefore, you can try to carry out the so-calleddouble induction(induction within induction).

We will conduct inductive reasoning on P.

1. The induction base according to paragraph. When n = 1 need to check that 2 t ~ 1 > t. To prove this inequality we use induction on T.

A) Induction base according to the so-called When t = 1 executed
equality, which is acceptable.

b) The induction step according to so-calledLet's assume that when t = k the statement is true, that is 2 k ~ 1 > k. Then up to
let us say that the statement will be true also for t = k + 1.
We have:

with natural to.

So the inequality 2 performed in any natural T.

2. Induction step according to item.Let's choose and fix some natural number T. Let's assume that when n = I the statement is true (for a fixed t), that is, 2 t +1 ~ 2 > t1, and we will prove that then the statement will be true also for n = l + 1.
We have:

for any natural type.

Therefore, based on the principle of mathematical induction (by P) the statement of the problem is true for any P and for any fixed T. Thus, this inequality holds for any natural type.

Problem 12. Let m, n and k are natural numbers, and t > p. Which of the two numbers is greater:

In every expression To square root signs, t and p alternate.

Solution. Let us first prove some auxiliary statement.

Lemma. For any natural t and p (t > p) and non-negative (not necessarily whole) X inequality is true

Proof. Consider the inequality

This inequality is true since both factors on the left side are positive. Expanding the brackets and transforming, we get:

Taking the square root of both sides of the last inequality, we obtain the statement of the lemma. So, the lemma is proven.

Let us now move on to solving the problem. Let us denote the first of these numbers by A, and the second - through b k. Let us prove that a under any natural To. We will carry out the proof using the method of mathematical induction separately for even and odd To.

Induction base. When k = 1 we have inequality

y[t > y/n , fair due to the fact that t > p. When k = 2 the required is obtained from the proven lemma by substitution x = 0.

Induction step. Suppose, for some k inequality a > b k fair. Let's prove that

From the induction assumption and square root monotonicity we have:

On the other hand, from the proven lemma it follows that

Combining the last two inequalities, we get:

According to the principle of mathematical induction, the statement is proven.

Problem 13. (Cauchy's inequality.)Prove that for any positive numbers..., a p inequality is true

Solution. For n = 2 the inequality

we will assume that the arithmetic mean and the geometric mean (for two numbers) are known. Let n= 2, k = 1, 2, 3, ... and first perform induction on To. The basis of this induction takes place by now assuming that the required inequality has already been established for n = 2, let's prove it for P = 2 . We have (applying the inequality for two numbers):

Therefore, by the inductive hypothesis

Thus, by induction on k we have proven the inequality for all p 9 being a power of two.

To prove the inequality for other values P Let us use “downward induction”, that is, we will prove that if the inequality holds for arbitrary non-negative P numbers, then it is also true for(P - 1st day. To verify this, we note that, according to the assumption made for P numbers the inequality holds

that is, a g + a 2 + ... + a n _ x > (n - 1)A. Dividing both parts into P - 1, we obtain the required inequality.

So, first we established that the inequality holds for an infinite number of possible values P, and then showed that if the inequality holds for P numbers, then it is also true for(P - 1) numbers. From this we now conclude that Cauty's inequality holds for the set of P any non-negative numbers for any n = 2, 3, 4, ...

Problem 14. (D. Uspensky.) For any triangle ABC whose angles = CAB, = CBA are commensurate, there are inequalities

Solution. Angles and are commensurable, and this (by definition) means that these angles have a common measure, for which = p, = (p, q are coprime natural numbers).

Let's use the method of mathematical induction and carry it out through the sum p = p + q natural coprime numbers..

Induction base. For p + q = 2 we have: p = 1 and q = 1. Then triangle ABC is isosceles, and the necessary inequalities are obvious: they follow from the triangle inequality

Induction step. Let us now assume that the necessary inequalities are established for p + q = 2, 3, ..., k - 1, where k > 2. Let us prove that the inequalities are also valid for p + q = k.

Let ABC - a given triangle that has> 2. Then sides AC and BC cannot be equal: let AC > BC. Let us now construct, as in Figure 2, an isosceles triangle ABC; we have:

AC = DC and AD = AB + BD, therefore,

2AC > AB + BD (1)

Consider now the triangle BDC, whose angles are also commensurate:

DСВ = (q - р), ВDC = p.

Rice. 2

For this triangle the inductive hypothesis holds, and therefore

(2)

Adding (1) and (2), we have:

2AC+BD>

and therefore

From the same triangle VBS by the induction hypothesis we conclude that

Taking into account the previous inequality, we conclude that

Thus, the inductive transition is obtained, and the statement of the problem follows from the principle of mathematical induction.

Comment. The statement of the problem remains valid even in the case when the angles a and p are not commensurate. In the basis of consideration in the general case, we already have to apply another important mathematical principle - the principle of continuity.

Problem 15. Several straight lines divide the plane into parts. Prove that you can color these parts white

and black colors so that adjacent parts that have a common border segment are of different colors (as in Figure 3 with n = 4).

pic 3

Solution. Let us use induction on the number of lines. So let P - the number of lines dividing our plane into parts, n > 1.

Induction base. If there is only one straight line(P = 1), then it divides the plane into two half-planes, one of which can be colored white and the second black, and the statement of the problem is true.

Induction step. To make the proof of the inductive transition more clear, consider the process of adding one new line. If we draw a second straight line(P= 2), then we get four parts that can be colored as needed by painting the opposite corners the same color. Let's see what happens if we draw a third straight line. It will divide some of the “old” parts, while new sections of the border will appear, on both sides of which the color is the same (Fig. 4).

Rice. 4

Let's proceed as follows:On the one sidefrom the new straight line we will change the colors - we will make white black and vice versa; at the same time, we do not repaint those parts that lie on the other side of this straight line (Fig. 5). Then this new coloring will satisfy the necessary requirements: on one side of the line it was already alternating (but with different colors), and on the other side it was what was needed. In order for the parts that have a common border belonging to the drawn line to be painted in different colors, we repainted the parts only on one side of this drawn straight line.

Fig.5

Let us now prove the inductive transition. Let us assume that for somep = kthe statement of the problem is true, that is, all parts of the plane into which it is divided by theseTostraight, you can paint them white and black so that adjacent parts are of different colors. Let us prove that then there exists such a coloring forP= To+ 1 direct. Let us proceed similarly to the case of transition from two lines to three. Let's draw on the planeTostraight Then, by the induction hypothesis, the resulting “map” can be colored in the desired way. Let's now carry out(To+ 1)th straight line and on one side of it we change the colors to the opposite ones. So now(To+ 1)-th straight line separates areas of different colors everywhere, while the “old” parts, as we have already seen, remain correctly colored. According to the principle of mathematical induction, the problem is solved.

Task16. On the edge of the desert there is a large supply of gasoline and a car that, when fully refueled, can travel 50 kilometers. There are unlimited quantities of canisters into which you can pour gasoline from your car’s gas tank and leave it for storage anywhere in the desert. Prove that a car can travel any integer distance greater than 50 kilometers. You are not allowed to carry gasoline cans; you can carry empty ones in any quantity.

Solution.Let's try to prove by induction onP,that the car can drive awayPkilometers from the edge of the desert. AtP= 50 is known. All that remains is to carry out the induction step and explain how to get therep = k+ 1 kilometers if it is known thatp = kYou can drive kilometers.

However, here we encounter a difficulty: after we have passedTokilometers, there may not be enough gasoline even for the return journey (not to mention storage). And in this case, the solution is to strengthen the statement being proven (the inventor's paradox). We will prove that you can not only drivePkilometers, but also to make an arbitrarily large supply of gasoline at a point at a distancePkilometers from the edge of the desert, arriving at this point after the end of transportation.

Induction base.Let a unit of gasoline be the amount of gasoline required to travel one kilometer. Then a trip of 1 kilometer and back requires two units of gasoline, so we can leave 48 units of gasoline in a storage facility a kilometer away from the edge and return for a new portion. Thus, over several trips to the storage facility, we can make a stock of any size that we need. At the same time, to create 48 units of reserve, we consume 50 units of gasoline.

Induction step.Let's assume that at a distanceP= Tofrom the edge of the desert you can stock up on any amount of gasoline. Let us prove that then it is possible to create a storage facility at a distancep = k+ 1 kilometers with any reserve of gasoline specified in advance and end up at this storage facility at the end of the transportation. Because at the pointP= Tothere is an unlimited supply of gasoline, then (according to the induction base) we can reach a point in several tripsp = k+ 1 do at pointP= To4- 1 stock of any size that is required.

The truth of a more general statement than in the problem statement now follows from the principle of mathematical induction.

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 strength.

Mostly these were 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.

Literature

1.Vulenkin INDUCTION. Combinatorics. Manual FOR teachers. M., Enlightenment,

1976.-48 p.

2. Golovina L.I., Yaglom I.M. Induction in geometry. - M.: State. published liter. - 1956 - S.I00. A manual on mathematics for those entering universities / Ed. Yakovleva G.N. The science. -1981. - P.47-51.

3.Golovina L.I., Yaglom I.M. Induction in geometry. —
M.: Nauka, 1961. - (Popular lectures on mathematics.)

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

5.R. Courant, G. Robbins "What is mathematics?" Chapter 1, § 2

6.Popa D. Mathematics and plausible reasoning. - M,: Nauka, 1975.

7.Popa D. Mathematical discovery. - M.: Nauka, 1976.

8. Rubanov I.S. How to teach the method of mathematical induction / Mathematics school. - Nl. - 1996. - P.14-20.

9. Sominsky I.S., Golovina L.I., Yaglom IM. On the method of mathematical induction. - M.: Nauka, 1977. - (Popular lectures on mathematics.)

10.Solominsky I.S. Method of mathematical induction. - M.: Science.

63s.

11.Solominsky I.S., Golovina L.I., Yaglom I.M. About mathematical induction. - M.: Science. - 1967. - P.7-59.

12.http://w.wikimedia.org/wiki

13.htt12:/ /www.refeshtcollestiop.ru/40 124.html

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

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

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

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

Really,

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

Consequently, the original equality holds for any natural n.

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

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,

Example 2. Prove inequalities

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

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

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

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:

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

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

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.

Bibliographic description: Badanin A. S., Sizova M. Yu. Application of the method of mathematical induction to solving problems on the divisibility of natural numbers // Young scientist. 2015. No. 2. P. 84-86..04.2019).

In mathematics Olympiads there are often quite difficult problems to prove the divisibility of natural numbers. Schoolchildren face a problem: how to find a universal mathematical method that allows them to solve such problems?

It turns out that most problems in proving divisibility can be solved by the method of mathematical induction, but school textbooks pay very little attention to this method; most often a brief theoretical description is given and several problems are analyzed.

We find the method of mathematical induction in number theory. At the dawn of number theory, mathematicians discovered many facts inductively: L. Euler and K. Gauss sometimes considered thousands of examples before noticing a numerical pattern and believing in it. But at the same time they understood how deceptive hypotheses that have passed the “final” test can be. To inductively move from a statement verified for a finite subset to a similar statement for the entire infinite set, a proof is required. This method was proposed by Blaise Pascal, who found a general algorithm for finding signs of divisibility of any integer by any other integer (treatise “On the nature of the divisibility of numbers”).

The method of mathematical induction is used to prove by reasoning the truth of a certain statement for all natural numbers or the truth of a statement starting from a certain number n.

Solving problems to prove the truth of a certain statement using the method of mathematical induction consists of four stages (Fig. 1):

Rice. 1. Scheme for solving the problem

1. Induction basis . They check the validity of the statement for the smallest natural number for which the statement makes sense.

2. Inductive hypothesis . We assume that the statement is true for some value of k.

3. Induction transition . We prove that the statement is true for k+1.

4. Conclusion . If such a proof was completed, then, based on the principle of mathematical induction, it can be argued that the statement is true for any natural number n.

Let us consider the application of the method of mathematical induction to solving problems of proving the divisibility of natural numbers.

Example 1. Prove that the number 5 is a multiple of 19, where n is a natural number.

Proof:

1) Let's check that this formula is correct for n = 1: the number =19 is a multiple of 19.

2) Let this formula be true for n = k, i.e. the number is a multiple of 19.

It is a multiple of 19. Indeed, the first term is divisible by 19 due to assumption (2); the second term is also divisible by 19 because it contains a factor of 19.

Example 2. Prove that the sum of the cubes of three consecutive natural numbers is divisible by 9.

Proof:

Let us prove the statement: “For any natural number n, the expression n 3 +(n+1) 3 +(n+2) 3 is a multiple of 9.

1) Let's check that this formula is correct for n = 1: 1 3 +2 3 +3 3 =1+8+27=36 multiples of 9.

2) Let this formula be true for n = k, i.e. k 3 +(k+1) 3 +(k+2) 3 is a multiple of 9.

3) Let us prove that the formula is also true for n = k + 1, i.e. (k+1) 3 +(k+2) 3 +(k+3) 3 is a multiple of 9. (k+1) 3 +( k+2) 3 +(k+3) 3 =(k+1) 3 +(k+2) 3 + k 3 + 9k 2 +27 k+ 27=(k 3 +(k+1) 3 +(k +2) 3)+9(k 2 +3k+ 3).

The resulting expression contains two terms, each of which is divisible by 9, so the sum is divisible by 9.

4) Both conditions of the principle of mathematical induction are satisfied, therefore, the sentence is true for all values ​​of n.

Example 3. Prove that for any natural number n, the number 3 2n+1 +2 n+2 is divisible by 7.

Proof:

1) Let's check that this formula is correct for n = 1: 3 2*1+1 +2 1+2 = 3 3 +2 3 =35, 35 is a multiple of 7.

2) Let this formula be true for n = k, i.e. 3 2 k +1 +2 k +2 is divided by 7.

3) Let us prove that the formula is also true for n = k + 1, i.e.

3 2(k +1)+1 +2 (k +1)+2 =3 2 k +1 ·3 2 +2 k +2 ·2 1 =3 2 k +1 ·9+2 k +2 ·2 =3 2 k +1 ·9+2 k +2 ·(9–7)=(3 2 k +1 +2 k +2)·9–7·2 k +2 .T. k. (3 2 k +1 +2 k +2) 9 is divided by 7 and 7 2 k +2 is divided by 7, then their difference is divided by 7.

4) Both conditions of the principle of mathematical induction are satisfied, therefore, the sentence is true for all values ​​of n.

Many proof problems in the theory of divisibility of natural numbers can be conveniently solved using the method of mathematical induction; one can even say that solving problems with this method is completely algorithmic; it is enough to perform 4 basic steps. But this method cannot be called universal, since there are also disadvantages: firstly, it can only be proven on a set of natural numbers, and secondly, it can only be proven for one variable.

For the development of logical thinking and mathematical culture, this method is a necessary tool, because the great Russian mathematician A. N. Kolmogorov said: “Understanding and the ability to correctly apply the principle of mathematical induction is a good criterion of logical maturity, which is absolutely necessary for a mathematician.”

Literature:

1. Vilenkin N. Ya. Induction. Combinatorics. - M.: Education, 1976. - 48 p.

2. Genkin L. On mathematical induction. - M., 1962. - 36 p.

3. Solominsky I. S. Method of mathematical induction. - M.: Nauka, 1974. - 63 p.

4. Sharygin I.F. Optional course in mathematics: Problem solving: Textbook for 10th grade. school average - M.: Education, 1989. - 252 p.

5. Shen A. Mathematical induction. - M.: MTsNMO, 2007. - 32 p.