Geography
Induction mat formula. Methodological development "method of mathematical induction". Induction and the laws of logic

Induction mat formula. Methodological development "method of mathematical induction". Induction and the laws of logic

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. The work is illustrated with a presentation.

Download:

Preview:

Ministry of Science and Education of the Russian Federation

State educational institution

average comprehensive school № 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, GOU 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 bottom, as a result 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, school curriculum he is given little time. 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 consideration in school practice and 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 of the 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.

Task 2. Consider all possible common 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:

with n = 3 this statement is true;

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 junctionor 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 subjects 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.

Induction base. When n = 1 everything is clear, since a pyramid of one ring can obviously be moved to any rod.
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 one can prove various statements concerning 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.

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.

Induction base. It is obvious that when n = 1 statement is true: since 3 3+3 - 26 - 27 = 676 = 26 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 it 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. We'll find greatest number Fibonacci 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 signs square root, 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 using 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 in White color, and the second in black, and the statement of the problem is correct.

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 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, in several trips to the pointp = 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 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 the 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. Tutorial/ “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

The method of proof that will be discussed in this paragraph is based on one of the axioms of the natural series.

Axiom of induction. Let a sentence be given that depends on a variable P, instead of which you can substitute any natural numbers. Let's denote it A(p). Let also the offer A true for the number 1 and from the fact that A true for number To, follows that A true for number k+ 1. Then offer A true for all natural values P.

Symbolic notation of the axiom:

Here peak- variables over the set of natural numbers. From the axiom of induction we obtain the following rule of inference:

So, in order to prove the truth of the sentence A, you can first prove two statements: the truth of the statement A( 1), as well as a consequence A(k) => A(k+ 1).

Taking into account the above, let us describe the essence method

mathematical induction.

Let it be necessary to prove that the proposition A(n) true for all naturals P. The proof is divided into two stages.

1st stage. Induction base. We take as the value P the number is 1 and check that A( 1) there is a true statement.
2nd stage. Inductive transition. We prove that for any natural number To the implication is true: if A(k), That A(k+ 1).

The inductive transition begins with the words: “Take an arbitrary natural number To, such that A(k)", or “Let for natural number To right A(k).” Instead of the word “let” they often say “suppose that...”.

After these words the letter To denotes a certain fixed object for which the relation holds A(k). Next from A(k) we draw consequences, that is, we build a chain of sentences A(k) 9 R, Pi, ..., P„ = A(k+ 1), where each sentence R, is a true statement or a consequence of previous sentences. The last sentence R" must match A(k+ 1). From this we conclude: from A(k) should A(k+).

Performing an inductive transition can be divided into two actions:

1) Inductive assumption. Here we assume that A To variable n.
2) Based on the assumption, we prove that A true for number?+1.

Example 5.5.1. Let us prove that the number p+p is even for all natural numbers P.

Here A(n) = "p 2 +p- even number". It is required to prove that A - identically true predicate. Let's apply the method of mathematical induction.

Induction base. Let's take l=1. Let's substitute in the expression P+//, we get n 2 +n= I 2 + 1 = 2 is an even number, that is, /1(1) is a true statement.

Let's formulate inductive hypothesis A(k)= "Number k 2 +k - even." You can say this: “Take an arbitrary natural number To such that k 2 +k there is an even number."

Let us derive the statement from here A(kA-)= "Number (k+ 1) 2 +(?+1) - even.”

Let's perform transformations based on the properties of operations:

The first term of the resulting sum is even by assumption, the second is even by definition (since it has the form 2 P). This means the sum is an even number. Offer A(k+ 1) proven.

Using the method of mathematical induction, we conclude: the proposition A(n) true for all naturals P.

Of course, there is no need to enter the notation every time A(p). However, it is still recommended to formulate the inductive assumption and what needs to be deduced from it in a separate line.

Note that the statement from example 5.5.1 can be proven without using the method of mathematical induction. To do this, it is enough to consider two cases: when P even and when P odd.

Many divisibility problems are solved using the method of mathematical induction. Let's look at a more complex example.

Example 5.5.2. Let's prove that the number 15 2i_| +1 is divisible by 8 for all naturals P.

Bacha induction. Let's take /1=1. We have: number 15 2|_| +1 = 15+1 = 16 divided by the number 8.

that for some

natural number To the number 15 2 * ’+1 is divisible by 8.

Let's prove what then is the number A= 15 2(VN +1 divides 8.

Let's convert the number A:

By assumption, the number 15 2A1 +1 is divisible by 8, which means that the entire first term is divisible by 8. The second term 224 = 8-28 is also divisible by 8. Thus, the number A how the difference of two numbers that are multiples of 8 is divided by 8. The inductive transition is justified.

Based on the method of mathematical induction, we conclude that for all natural P the number 15 2 "-1 -*-1 is divisible by 8.

Let us make some comments on the solved problem.

The proven statement can be formulated a little differently: “The number 15”+1 is divisible by 8 for any odd natural / and.”

Secondly, from the proven general statement one can draw a particular conclusion, the proof of which can be given as a separate problem: the number 15 2015 +1 is divisible by 8. Therefore, sometimes it is useful to generalize the problem by denoting a specific value with a letter, and then apply the method mathematical induction.

In the very general understanding the term “induction” means that based on particular examples one makes general conclusions. For example, having considered some examples of sums of even numbers 2+4=6, 2+8=10, 4+6=10, 8+12=20, 16+22=38, we conclude that the sum of any two even numbers is even number.

In general, such induction can lead to incorrect conclusions. Let us give an example of such incorrect reasoning.

Example 5.5.3. Consider the number A= /g+i+41 for natural /?.

Let's find the values A for some values P.

Let n= I. Then a = 43 is a prime number.

Let /7=2. Then A= 4+2+41 = 47 - prime.

Let l=3. Then A= 9+3+41 = 53 - prime.

Let /7=4. Then A= 16+4+41 = 61 - prime.

Take as values P numbers following the four, such as 5, 6, 7, and make sure that the number A will be simple.

We conclude: “For all natural /? number A will be simple."

The result was false statement. Let's give a counterexample: /7=41. Make sure that for this P number A will be composite.

The term “mathematical induction” has a narrower meaning, since the use of this method always allows one to obtain a correct conclusion.

Example 5.5.4. Based on inductive reasoning, we obtain the formula for the general term arithmetic progression. Let us recall that the arithmetic profession is called number sequence, each term of which differs from the previous one by the same number, called the progression difference. In order to uniquely specify an arithmetic profession, you need to indicate its first member A and difference d.

So, by definition a n+ = a n + d, at n> 1.

IN school course Mathematicians, as a rule, the formula of the general term of the arithmetic profession is established on the basis of particular examples, that is, by induction.

If /7=1, THEN WITH 7| = I|, THAT is I| = tf|+df(l -1).

If /7=2, then I am 2 = a+d, that is A= I|+*/(2-1).

If /7=3, then i 3 = i 2 + = (a+d)+d = a+2d, that is, I 3 = I|+(3-1).

If /7=4, then i 4 = i 3 +*/ = ( a+2d)+d= R1+3, etc.

The given particular examples allow us to put forward a hypothesis: the formula of the general term has the form A" = a+(n-)d for everyone /7>1.

Let us prove this formula by mathematical induction.

Induction base verified in previous discussions.

Let To - such a number at which I* - a+(k-)d (inductive assumption).

Let's prove, that I*+! = a+((k+)-)d, that is, I*+1 = a x +kd.

By definition I*+1 = ab+d. a to= i | +(k-1 )d, Means, ac+= i i +(A:-1)^/+c/ = i | +(A-1+1 )d= i +kd, which was what needed to be proven (to justify the inductive transition).

Now the formula i„ = a+(n-)d proven for any natural number /;.

Let some sequence i ь i 2, i,„... (not

necessarily arithmetic or geometric progression). Problems often arise where it is necessary to summarize the first P terms of this sequence, that is, specify the sum I|+I 2 +...+I and a formula that allows you to find the values of this sum without calculating the terms of the sequence.

Example 5.5.5. Let us prove that the sum of the first P natural numbers is equal to

/?(/7 + 1)

Let us denote the sum 1+2+...+/7 by S n . Let's find the values S n for some /7.

Note: in order to find the sum S 4, you can use the previously calculated value 5 3, since 5 4 = 5 3 +4.

p(p +1)

If we substitute the considered values /? in term --- then

we obtain, respectively, the same sums 1, 3, 6, 10. These observations

. _ p(p + 1)

suggest that the formula S„=--- can be used when

any //. Let us prove this hypothesis using the method of mathematical induction.

Induction base verified. Let's do it inductive transition.

Suppose that the formula is true for some natural number

, k(k + 1)

k, then the network is the sum of the first To natural numbers is equal to ----.

Let's prove that the sum of the first (?+1) natural numbers is equal to

(* + !)(* + 2)

Let's express?*+1 through S k . To do this, in the sum S*+i we group the first To terms, and write the last term separately:

By inductive hypothesis S k = So to find

the sum of the first (?+1) natural numbers is sufficient to the already calculated

. „ k(k + 1) _ .. ..

the sum of the first To numbers equal to ---, add one term (k+1).

The inductive transition is justified. Thus, the hypothesis put forward at the beginning is proven.

We have given a proof of the formula S n = n^n+ method

mathematical induction. Of course, there is other evidence. For example, you can write the amount S, in ascending order of terms, and then in descending order of terms:

The sum of the terms in one column is constant (in one sum, each next term decreases by 1, and in the other increases by 1) and is equal to (/r + 1). Therefore, adding up the resulting sums, we will have P terms equal to (u+1). So double the amount S„ equal to n(n+ 1).

The proven formula can be obtained as special case formulas for the sum of the first P terms of an arithmetic progression.

Let's return to the method of mathematical induction. Note that the first stage of the method of mathematical induction (base of induction) is always necessary. Missing this step may lead to an incorrect conclusion.

Example 5.5.6. Let us “prove” the sentence: “The number 7"+1 is divisible by 3 for any natural number i.”

“Suppose that for some natural value To the number 7*+1 is divisible by 3. Let us prove that the number 7 x +1 is divisible by 3. Perform the transformations:

The number 6 is obviously divisible by 3. The number 1 to + is divisible by 3 by inductive hypothesis, which means that the number 7-(7* + 1) is also divisible by 3. Therefore, the difference of numbers divisible by 3 will also be divisible by 3.

The proposition has been proven.”

The proof of the original proposition is incorrect, even though the inductive leap is performed correctly. Indeed, when n= I we have the number 8, with n=2 - the number is 50, ..., and none of these numbers is divisible by 3.

Let us make an important note about the notation of a natural number when performing an inductive transition. When formulating a proposal A(n) letter P we denoted a variable, instead of which any natural numbers can be substituted. When formulating the inductive hypothesis, we denoted the value of the variable by the letter To. However, very often instead of a new letter To use the same letter as the variable. This does not in any way affect the structure of reasoning when performing an inductive transition.

Let's look at a few more examples of problems that can be solved using the method of mathematical induction.

Example 5.5.7. Let's find the value of the sum

Variable in the task P does not appear. However, consider the sequence of terms:

Let's denote S, = a+a 2 +...+a„. We'll find S„ for some P. If /1= 1, then S, =a, =-.

If n= 2. then S, = A, + A? = - + - = - = -.

If /?=3, then S-, = a,+a 7+ i, = - + - + - = - + - = - = -.

3 1 - 3 2 6 12 3 12 12 4

You can calculate the values yourself S„ at /7 = 4; 5. Arises

natural assumption: S n= -- for any natural /7. Let's prove

This is the method of mathematical induction.

Induction base checked above.

Let's do it inductive junction, denoting an arbitrarily taken

variable value P with the same letter, that is, we will prove that from the equality

0 /7 _ /7 +1

S n= - equality follows S, =-.

/7+1 /7 + 2

Suppose that equality is true S= - P -.

Let's sum it up S„+ first P terms:

Applying the inductive hypothesis, we get:

Reducing the fraction by (/7+1), we have the equality S n +1 - , L

The inductive transition is justified.

This proves that the sum of the first P terms

1 1 1 /7 ^
- +-+...+- is equal to -. Now let's go back to the original
1-2 2-3 /?(// +1) /7 + 1

task. To solve it, it is enough to take as a value P number 99.

Then the sum -!- + -!- + -!- + ...+ --- will be equal to the number 0.99.

1-2 2-3 3-4 99100

Try to calculate this amount in a different way.

Example 5.5.8. Let us prove that the derivative of the sum of any finite number of differentiable functions is equal to the sum of the derivatives of these functions.

Let the variable /? denotes the number of these functions. In the case where only one function is given, the sum is understood to be precisely this function. Therefore, if /7 = 1, then the statement is obviously true: /" = /".

Suppose that the statement is true for a set of P functions (here again instead of the letter To letter taken P), that is, the derivative of the sum P functions is equal to the sum of the derivatives.

Let's prove that the derivative of the sum (i+1) of functions is equal to the sum of the derivatives. Let us take an arbitrary set consisting of n+ differentiable function: /1,/2, . Let's imagine the sum of these functions

as g+f„+ 1, where g=f +/g + ... +/ t - sum P functions. By the inductive hypothesis, the derivative of the function g equal to the sum of derivatives: g" = ft +ft + ... +ft. Therefore, the following chain of equalities holds:

The inductive transition is complete.

Thus, the original proposition is proven for any finite number of functions.

In some cases it is necessary to prove the truth of a sentence A(n) for all natural selves, starting from some value With. The proof by mathematical induction in such cases is carried out according to the following scheme.

Induction base. We prove that the proposal A true for value P, equal With.

Inductive transition. 1) We assume that the offer A true for some value To variable /?, which is greater than or equal to With.

2) We prove that the proposal A true for /? equal to

Note again that instead of the letter To variable designation is often left P. In this case, the inductive transition begins with the words: “Suppose that for some value p>s right A(p). Let us prove that then it is true A(n+ 1)".

Example 5.5.9. Let us prove that for all natural n> 5 the inequality 2” > and 2 is true.

Induction base. Let n= 5. Then 2 5 =32, 5 2 =25. Inequality 32>25 is true.

Inductive transition. Suppose that inequality 2 holds P >p 2 for some natural number n> 5. Let's prove, which then 2" +| > (n+1) 2 .

According to the properties of degrees 2” +| = 2-2". Since 2">I 2 (by inductive assumption), then 2-2">2I 2 (I).

Let's prove that 2 n 2 greater than (i+1) 2 . This can be done in different ways. It is enough to solve the quadratic inequality 2x 2 >(x+) 2 in abundance real numbers and see that all natural numbers greater than or equal to 5 are its solutions.

We will proceed as follows. Let's find the difference numbers 2 n 2 and (i+1) 2:

Since > 5, then i+1 > 6, which means (i+1) 2 > 36. Therefore, the difference is greater than 0. So, 2i 2 > (i+1) 2 (2).

Based on the properties of the inequalities from (I) and (2), it follows that 2*2" > (i+1) 2, which was what needed to be proven to justify the inductive transition.

Based on the method of mathematical induction, we conclude that the inequality 2" > i 2 is true for any natural numbers i.

Let's consider another form of the method of mathematical induction. The difference lies in the inductive transition. To implement it, you need to complete two steps:

1) assume that the proposal A(n) true for all values of the variable i less than a certain number R;
2) from the put forward assumption, conclude that the proposal A(n) also true for numbers R.

Thus, the inductive transition requires proof of the corollary: [(Ui?) A(p)] => A(p). Note that the corollary can be rewritten as: [(Up^p) A(p)] => A(p+ 1).

In the original formulation of the method of mathematical induction when proving a proposition A(p) we relied only on the “previous” sentence A(p- 1). The formulation of the method given here allows us to derive A(p), considering that all proposals A(p), where am I less R, are true.

Example 5.5.10. Let us prove the theorem: “The sum of the interior angles of any i-gon is equal to 180°(i-2).”

For a convex polygon, the theorem is easy to prove if you divide it into triangles by diagonals drawn from one vertex. However, for a non-convex polygon such a procedure may not be possible.

Let us prove the theorem for an arbitrary polygon using mathematical induction. Let us assume that the following statement is known, which, strictly speaking, requires a separate proof: “In any //-gon there is a diagonal that lies entirely in its interior part.”

Instead of the variable // you can substitute any natural numbers that are greater than or equal to 3. For n=b The theorem is true because in a triangle the sum of the angles is 180°.

Let us take some /7-gon (p> 4) and assume that the sum of the angles of any //-gon, where // p, is equal to 180°(//-2). Let us prove that the sum of the angles of the //-gon is equal to 180°(//-2).

Let us draw the diagonal of the //-gon lying inside it. It will split the //-gon into two polygons. Let one of them have To sides, the other - to 2 sides Then k+k 2 -2 = p, since the resulting polygons have common side a drawn diagonal that is not a side of the original //-gon.

Both numbers To And to 2 less //. Let us apply the inductive assumption to the resulting polygons: the sum of the angles of the A]-gon is equal to 180°-(?i-2), and the sum of the angles? 2 -gon is equal to 180°-(Ar 2 -2). Then the sum of the angles of the //-gon will be equal to the sum of these numbers:

180°*(Ar|-2)-n 180°(Ar2-2) = 180 o (Ar,-bAr 2 -2-2) = 180°-(//-2).

The inductive transition is justified. Based on the method of mathematical induction, the theorem is proven for any //-gon (//>3).

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.

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) 1 A(k+1)

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

1) We have n=1=1 2 . Therefore, the statement is true for n=1, i.e. A(1) 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) 1 A(k+1). Based on the principle of mathematical induction, we conclude that assumption A(n) is true for any n O N

Prove that

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

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) true

2) Let k be any natural number and let the formula be true for n=k,
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) 1 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 n(n-3)/2

Solution: 1) For n=3 the statement is true, because in the triangle

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

2) Suppose that in every convex k-gon there are A 1 x A k =k(k-3)/2 diagonals. A k Let us prove that then in a convex A k+1 (k+1)-gon the number of 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 count total number 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 to the resulting number k-2, 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,

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

So, A(k) 1 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

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), i.e. 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 validity 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 number 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 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) 1 A(k+1). By virtue of the method of mathematical induction, the statement is proven

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

1) Let n=1, then X 1 =7 1 -1=6 is divided by 6 without a remainder. This means that for n=1 the statement is true
2) Suppose that when n=k 7 k -1 is divided 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 number 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 number n is divisible by 11.

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 when n=k X k =3 3k-1 +2 4k-3 is divided 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 a 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 number n is divisible by 6 without a remainder

1) Let n=1, then 11 2 -1=120 is divisible by 6 without a remainder. This means that for n=1 the statement is true
2) Suppose that when n=k 1 2k -1 is divided 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, 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

Let us first prove that 3 3n+3 -1 is divisible by 26 without a remainder

1. When n=0
3 3 -1=26 is divided by 26
2. Suppose that for n=k
3 3k+3 -1 is divisible by 26
3. Let us prove that the statement is 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 prove the statement formulated in the problem statement

1) Obviously, for 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 (1+x) n >1+n ґ x is true

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

Indeed, multiplying both sides of inequality (3) by positive number 1+x, we get

(1+x) k+1 >(1+k ґ x)(1+x)

Consider the right side of the last inequality; 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) 1 A(k+1). Based on the principle of mathematical induction, it can be argued that Bernoulli’s inequality is valid for any n> 2

Prove that the inequality (1+a+a 2) m > 1+m ґ a+(m(m+1)/2) ґ a 2 for a> 0 is true

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 inequality to be true for m=k+1, therefore, by virtue of the method of mathematical induction, the inequality is valid for any natural number m

Prove that for n>6 the inequality 3 n >n ґ 2 n+1 is true

Let us rewrite the inequality in the form (3/2) n >2n

1. For n=7 we have 3 7 /2 7 =2187/128>14=2 ґ 7 the inequality is true
2. Suppose that for n=k (3/2) k >2k
3) Let us prove 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)

1) For n=3 the inequality is true
1+(1/2 2)+(1/3 2)=245/180
2. Suppose 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 inequality for n=k+1
(1+(1/2 2)+…+(1/k 2))+(1/(k+1) 2)

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

S (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.

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

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

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.

Introduction

Main part

1. Complete and incomplete induction

2. Principle of mathematical induction

3. Method of mathematical induction

4. Solving examples

5. Equalities

6. Dividing numbers

7. Inequalities

Conclusion

List of used literature

Introduction

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

Main part

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

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.

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.

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 proposal A(n), depending on the natural numbern, true forn=1 and from the fact that it is true forn=k(Wherek-any natural number), it follows that it is true for the next numbern=k+1, then assumption A(n) true for any natural numbern.

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 proposal A(n) true forn=pand if A(k) Þ A(k+1)for anyonek>p,then sentence A(n)true for anyonen>p.

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

EXAMPLE 2

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.

EXAMPLE 3

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.

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.

EXAMPLE 4

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.

EXAMPLE 5

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