Mathematical induction underlies one of the most common methods of mathematical proofs. With its help, you can prove most of the formulas with natural numbers n, for example, the formula for finding the sum of the first terms of the progression S n = 2 a 1 + n - 1 d 2 n, Newton's binomial formula a + b n = C n 0 a n C n 1 a n - 1 b + . . . + C n n - 1 a b n - 1 + C n n b n .

In the first paragraph, we will analyze the basic concepts, then we will consider the basics of the method itself, and then we will tell you how to use it to prove equalities and inequalities.

Yandex.RTB R-A-339285-1

Concepts of induction and deduction

First, let's look at what induction and deduction are in general.

Definition 1

Induction is the transition from the particular to the general, and deduction on the contrary, from the general to the particular.

For example, we have a statement: 254 can be divided into two completely. From it we can draw many conclusions, among which there will be both true and false. For example, the statement that all integers that have the number 4 at the end can be divided by two without a remainder is true, but that any number of three digits is divisible by 2 is false.

In general, it can be said that with the help of inductive reasoning, many conclusions can be drawn from one known or obvious reasoning. Mathematical induction allows us to determine how valid these conclusions are.

Suppose we have a sequence of numbers like 1 1 2 , 1 2 3 , 1 3 4 , 1 4 5 , . . . , 1 n (n + 1) , where n denotes some natural number. In this case, when adding the first elements of the sequence, we get the following:

S 1 \u003d 1 1 2 \u003d 1 2, S 2 \u003d 1 1 2 + 1 2 3 \u003d 2 3, S 3 \u003d 1 1 2 + 1 2 3 + 1 3 4 \u003d 3 4, S 4 = 1 1 2 + 1 2 3 + 1 3 4 + 1 4 5 = 4 5 , . . .

Using induction, we can conclude that S n = n n + 1 . In the third part we will prove this formula.

What is the method of mathematical induction

This method is based on the principle of the same name. It is formulated like this:

Definition 2

A certain statement will be true for a natural value n when 1) it will be true for n = 1 and 2) from the fact that this expression is true for an arbitrary natural value n = k , it follows that it will also be true for n = k + 1 .

The application of the method of mathematical induction is carried out in 3 stages:

1. First, we check the correctness of the original statement in the case of an arbitrary natural value of n (usually the test is done for unity).
2. After that, we check the fidelity at n = k .
3. And then we prove the validity of the statement if n = k + 1 .

How to apply the method of mathematical induction when solving inequalities and equations

Let's take the example we talked about earlier.

Example 1

Prove the formula S n = 1 1 2 + 1 2 3 + . . . + 1 n (n + 1) = n n + 1 .

Solution

As we already know, to apply the method of mathematical induction, three consecutive steps must be performed.

1. First, we check whether this equality will be valid for n equal to one. We get S 1 \u003d 1 1 2 \u003d 1 1 + 1 \u003d 1 2. Everything is correct here.
2. Further, we make the assumption that the formula S k = k k + 1 is correct.
3. In the third step, we need to prove that S k + 1 = k + 1 k + 1 + 1 = k + 1 k + 2 , based on the validity of the previous equality.

We can represent k + 1 as the sum of the first terms of the original sequence and k + 1:

S k + 1 = S k + 1 k + 1 (k + 2)

Since in the second step we got that S k = k k + 1, we can write the following:

S k + 1 = S k + 1 k + 1 (k + 2) .

Now we perform the necessary transformations. We will need to reduce the fraction to a common denominator, reduce like terms, apply the abbreviated multiplication formula and reduce what happened:

S k + 1 = S k + 1 k + 1 (k + 2) = k k + 1 + 1 k + 1 (k + 2) = = k (k + 2) + 1 k + 1 (k + 2) = k 2 + 2 k + 1 k + 1 (k + 2) = (k + 1) 2 k + 1 (k + 2) = k + 1 k + 2

Thus, we have proved the equality in the third point by performing all three steps of the method of mathematical induction.

Answer: the assumption about the formula S n = n n + 1 is correct.

Let's take a more complex problem with trigonometric functions.

Example 2

Give a proof of the identity cos 2 α · cos 4 α · . . . cos 2 n α \u003d sin 2 n + 1 α 2 n sin 2 α.

Solution

As we remember, the first step should be to check the correctness of equality when n is equal to one. To find out, we need to remember the basic trigonometric formulas.

cos 2 1 = cos 2 α sin 2 1 + 1 α 2 1 sin 2 α = sin 4 α 2 sin 2 α = 2 sin 2 α cos 2 α 2 sin 2 α = cos 2 α

Therefore, for n equal to one, the identity will be true.

Now suppose that its validity is preserved for n = k , i.e. it will be true that cos 2 α · cos 4 α · . . . cos 2 k α \u003d sin 2 k + 1 α 2 k sin 2 α.

We prove the equality cos 2 α · cos 4 α · . . . cos 2 k + 1 α = sin 2 k + 2 α 2 k + 1 sin 2 α for the case when n = k + 1, based on the previous assumption.

According to the trigonometric formula,

sin 2 k + 1 α cos 2 k + 1 α = = 1 2 (sin (2 k + 1 α + 2 k + 1 α) + sin (2 k + 1 α - 2 k + 1 α)) = = 1 2 sin (2 2 k + 1 α) + sin 0 = 1 2 sin 2 k + 2 α

Consequently,

cos 2 α cos 4 α . . . · cos 2 k + 1 α = = cos 2 α · cos 4 α · . . . cos 2 k α cos 2 k + 1 α = = sin 2 k + 1 α 2 k sin 2 α cos 2 k + 1 α = 1 2 sin 2 k + 1 α 2 k sin 2 α = sin 2 k + 2 α 2 k + 1 sin 2 α

An example of solving the problem of proving an inequality using this method is given in the article on the least squares method. Read the paragraph in which the formulas for finding the approximation coefficients are derived.

If you notice a mistake in the text, please highlight it and press Ctrl+Enter

The text of the work is placed without images and formulas.
The full version of the work is available in the "Job Files" tab in PDF format

Introduction

This topic is relevant, since every day people solve various problems in which they use different methods of solving, but there are tasks in which the method of mathematical induction cannot be dispensed with, and in such cases knowledge in this area will be very useful.

I chose this topic for research, because in the school curriculum the method of mathematical induction is given little time, the student learns superficial information that will help him get only a general idea of ​​\u200b\u200bthis method, but self-development will be required to study this theory in depth. It will really be useful to learn more about this topic, as it expands the horizons of a person and helps in solving complex problems.

Objective:

Get acquainted with the method of mathematical induction, systematize knowledge on this topic and apply it in solving mathematical problems and proving theorems, substantiate and clearly show the practical significance of the method of mathematical induction as a necessary factor for solving problems.

Work tasks:

Analyze the literature and summarize knowledge on the topic.

Understand the principles of mathematical induction.

Explore the application of the method of mathematical induction to problem solving.

Formulate conclusions and conclusions on the work done.

Main body of research

Origin history:

Only towards the end of the 19th century did the standard of requirements for logical rigor develop, which to this day remains dominant in the practical work of mathematicians on the development of individual mathematical theories.

Induction is a cognitive procedure by means of which a statement generalizing them is deduced from a comparison of available facts.

In mathematics, the role of induction is largely that it underlies the chosen axiomatics. After a long 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 is satisfied.

The awareness of the method of mathematical induction as a separate important method goes back to Blaise Pascal and Gersonides, although some cases of application are found even in ancient times by Proclus and Euclid. The modern name for the method was introduced by de Morgan in 1838.

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

Induction and deduction

It is known that there are both particular and general statements, and the two given terms are based on the transition from one to the other.

Deduction (from lat. deductio - derivation) - the transition in the process of cognition from general knowledge to private and single. In deduction, general knowledge serves as the starting point of reasoning, and this general knowledge is assumed to be "ready", existing. The peculiarity of deduction is that the truth of its premises guarantees the truth of the conclusion. Therefore, deduction has a great power of persuasion and is widely used not only to prove theorems in mathematics, but also wherever reliable knowledge is needed.

Induction (from Latin inductio - guidance) is a transition in the process of cognition from private knowledge to general In other words, it is a method of research, knowledge, associated with the generalization of the results of observations and experiments. A feature of induction is its probabilistic nature, i.e. given the truth of the initial premises, the conclusion of the induction is only probably true, and in the final result it may turn out to be both true and false.

Complete and incomplete induction

Inductive reasoning is a form of abstract thinking in which thought develops from knowledge of a lesser degree of generality to knowledge of a greater degree of generality, and the conclusion that follows from the premises is predominantly probabilistic.

In the course of research, I found out that induction is divided into two types: complete and incomplete.

A complete induction is called a conclusion in which a general conclusion about a class of objects is made on the basis of the study of all objects of this class.

For example, let it be required to establish that every natural even number n within 6≤ n≤ 18 is representable as the sum of two prime numbers. To do this, we take all such numbers and write out the corresponding expansions:

6=3+3; 8=5+3; 10=7+3; 12=7+5;14=7+7; 16=11+5; 18=13+5;

These equalities show that each of the numbers of interest to us is indeed represented as the sum of two simple terms.

Consider the following example: the sequence yn= n 2 +n+17; Let's write out the first four terms: y 1 =19; y2=23; y3=29; y4=37; Then we can assume that the whole sequence consists of prime numbers. But this is not so, let's take y 16 = 16 2 +16+17=16(16+1)+17=17*17. This is a composite number, which means our assumption is wrong, thus, incomplete induction does not lead to completely reliable conclusions, but allows us to formulate a hypothesis, which later requires mathematical proof or refutation.

Method of mathematical induction

Complete induction has only limited applications in mathematics. Many interesting mathematical statements cover an infinite number of special cases, and we cannot test for all these situations. But how to test for an infinite number of cases? This method was proposed by B. Pascal and J. Bernoulli, this is a method of mathematical induction, which is based on principle of mathematical induction.

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

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

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

Algorithm (it consists of four stages):

1.base(we show that the assertion being proved is true for some simplest special cases ( P = 1));

2.guess(we assume that the assertion is proved for the first to cases); 3 .step(under this assumption we prove the assertion for the case P = to + 1); 4.output (y statement is true for all cases, that is, for all P) .

Note that not all problems can be solved by the method of mathematical induction, but only problems parameterized by some variable. This variable is called the induction variable.

Application of the method of mathematical induction

Let's apply all this theory in practice and find out in which problems this method is used.

Problems for the proof of inequalities.

Example 1 Prove the Bernoulli inequality (1+x)n≥1+n x, x>-1, n € N.

1) For n=1, the inequality is true, since 1+х≥1+х

2) Assume that the inequality is true for some n=k, i.e.

(1+x) k ≥1+k x.

Multiplying both sides of the inequality by a positive number 1+x, we get

(1+x) k+1 ≥(1+kx)(1+ x) =1+(k+1) x + kx 2

Considering that kx 2 ≥0, we arrive at the inequality

(1+x) k+1 ≥1+(k+1) x.

Thus, the assumption that Bernoulli's inequality is true for n=k implies that it is true for n=k+1. Based on the method of mathematical induction, it can be argued that Bernoulli's inequality is valid for any n ∈ N.

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

Let us prove using the method of mathematical induction.

Denote the left side of the inequality by.

1), therefore, for n=2 the inequality is true.

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

Comparing and, we have, i.e. .

For any natural k, the right side of the last equality is positive. That's why. But, therefore, and. We proved the validity of the inequality for n=k+1, therefore, by virtue of the method of mathematical induction, the inequality is true for any natural n>1.

Problems for the proof of identities.

Example 1 Prove that for any natural n the equality is true:

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

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=kX 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 n.

Example 2 Prove that for any natural n the equality

1) Check that this identity is true for n = 1.; - right.

2) Let the identity be true for n = k as well, i.e.

3) Let us prove that this identity is also true for n = k + 1, i.e.;

Because equality is true for n=k and n=k+1, then it is true for any natural n.

Summation tasks.

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

Solution: 1) We have n=1=1 2 . Therefore, the statement is true for n=1, i.e. A(1) is true.

2) Let us prove that А(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 assertion 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 the assumption A(n) is true for any n N.

Example 2 Prove the formula, n is a natural number.

Solution: When n=1, both parts of the equality turn into one and, therefore, the first condition of the principle of mathematical induction is satisfied.

Assume that the formula is true 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 true for n=k+1, then this statement is true for any natural n.

divisibility tasks.

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

Solution: 1) Let n=1, then

11 3 +12 3 \u003d (11 + 12) (11 2 -132 + 12 2) \u003d 23 × 133.

(23 × 133) is divisible by 133 without a remainder, so for n=1 the statement 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 2n+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 divisible 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), then based on the method of mathematical induction, the statement is true for any natural n.

Example 2 Prove that 3 3n-1 +2 4n-3 for an arbitrary positive integer 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 divisible by 11 without a remainder. Hence, for n=1 the statement is true.

2) Assume that for n=k

X k \u003d 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. Hence, the sum is also divisible by 11 without a remainder for any natural n.

Tasks from real life.

Example 1 Prove that the sum Sn of interior angles of any convex polygon is ( P- 2)π, where P is the number of sides of this polygon: Sn = ( P- 2)π (1).

This statement does not make sense for all natural P, but only for P > 3, since the minimum number of angles in a triangle is 3.

1) When P= 3 our statement takes the form: S 3 = π. But the sum of the interior angles of any triangle is indeed π. Therefore, when P= 3 formula (1) is true.

2) Let this formula be true for n =k, that is, S k = (k- 2)π, where k > 3. Let us prove that in this case the formula also holds: S k+ 1 = (k- 1) π.

Let A 1 A 2 ... A k A k+ 1 - arbitrary convex ( k+ 1) -gon (Fig. 338).

By connecting points A 1 and A k , we get convex k-gon A 1 A 2 ... A k — 1A k . Obviously, the sum of the angles ( k+ 1) -gon A 1 A 2 ... A k A k+ 1 equals the sum of the angles k-gon A 1 A 2 ... A k plus the sum of the angles of triangle A 1 A k A k+ one . But the sum of the angles k-gon A 1 A 2 ... A k is assumed to be ( k- 2)π, and the sum of the angles of the triangle A 1 A k A k+ 1 is equal to pi. That's why

S k+ 1=S k + π = ( k- 2)π + π = ( k- 1) π.

So, both conditions of the principle of mathematical induction are satisfied, and therefore formula (1) is true for any natural P > 3.

Example 2 There is a staircase, all the steps of which are the same. It is required to indicate the minimum number of positions that would guarantee the possibility of "climbing" any step by number.

Everyone agrees that there should be a condition. We must be able to climb the first step. Next, they must be able to climb from the first step to the second. Then in the second - on the third, etc. to the nth step. Of course, in the aggregate, "n" statements guarantee nm that we will be able to get to the n-th step.

Let's now look at the 2, 3,…., n positions and compare them with each other. It is easy to see that they all have the same structure: if we got to the k step, then we can climb the (k + 1) step. From here, such an axiom for the validity of statements that depend on "n" becomes natural: if the sentence A (n), in which n is a natural number, is satisfied with n=1 and from the fact that it is satisfied with n=k (where k is any natural number), it follows that it also holds for n=k+1, then Assumption A(n) holds for any natural number n.

Application

Tasks using the method of mathematical induction when entering universities.

Note that when entering higher educational institutions, there are also tasks that are solved by this method. Let's take a look at them concrete examples.

Example 1 Prove that any natural P fair equality

1) When n=1 we get the correct equality Sin.

2) Having made the inductive assumption that for n= k equality is true, consider the sum on the left side of the equality, for n =k+1;

3) Using the reduction formulas, we transform the expression:

Then, by virtue of the method of mathematical induction, the equality is true for any natural n.

Example 2 Prove that for any natural n the value of the expression 4n +15n-1 is a multiple of 9.

1) With n=1: 2 2 +15-1=18 - multiple of 9 (because 18:9=2)

2) Let equality hold for n=k: 4k +15k-1 is a multiple of 9.

3) Let us prove that the equality holds for the next number n=k+1

4k+1 +15(k+1)-1=4k+1 +15k+15-1=4.4k +60k-4-45k+18=4(4k +15k-1)-9(5k- 2)

4(4k +15k-1) - multiple of 9;

9(5k-2) - multiple of 9;

Consequently, the entire expression 4(4 k +15k-1)-9(5k-2) is a multiple of 9, which was to be proved.

Example 3 Prove that for any natural number P condition is met: 1∙2∙3+2∙3∙4+…+ n(n+1)(n+2)=.

1) Check that this formula is true for n=1: Left side = 1∙2∙3=6.

Right part = . 6 = 6; true at n=1.

2) Assume that this formula is true for n =k:

1∙2∙3+2∙3∙4+…+k(k+1)(k+2)=. S k =.

3) Let us prove that this formula is true for n =k+1:

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

S k+1 =.

Proof:

So, this condition is true in two cases and proved that it is true for n =k+1, therefore it is true for any natural number P.

Conclusion

To summarize, in the process of research, I found out what induction is, which is complete or incomplete, got acquainted with the method of mathematical induction based on the principle of mathematical induction, considered many problems using this method.

I also learned a lot of new information, different from what is included in the school curriculum. While studying the method of mathematical induction, I used various literature, Internet resources, and also consulted with a teacher.

Conclusion: Having generalized and systematized knowledge on mathematical induction, I became convinced of the need for knowledge on this topic in reality. A positive quality of the method of mathematical induction is its wide application in solving problems: in the field of algebra, geometry and real mathematics. Also, this knowledge increases interest in mathematics as a science.

I am sure that the skills acquired during the work will help me in the future.

​ Bibliography

Sominsky I.S. Method of mathematical induction. Popular lectures on mathematics, issue 3-M.: Nauka, 1974.

L. I. Golovina, I. M. Yaglom. Induction in geometry. - Fizmatgiz, 1961. - T. 21. - 100 p. — (Popular lectures on mathematics).

Dorofeev G.V., Potapov M.K., Rozov N.Kh. Mathematics manual for applicants to universities (Selected questions of elementary mathematics) - Ed. 5th, revised, 1976 - 638s.

A. Shen. Mathematical induction. - MTsNMO, 2004. - 36 p.

M.L. Galitsky, A.M. Goldman, L.I. Zvavich Collection of problems in algebra: textbook for 8-9 cells. with a deep the study of mathematics 7th ed. - M .: Education, 2001. - 271 p.

Yu.N. - M .: Pro-sve-shche-nie, 2002.

Wikipedia is the free encyclopedia.

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

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

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

The proof by the method of mathematical induction is carried out as follows. First, the assertion to be proved is checked for n=1, i.e., the truth of the statement A(1) is established. This part of the proof is called the induction basis. This is followed by a part of the proof called the induction step. In this part, the validity of the statement for n=k+1 is proved under the assumption that the statement is true for n=k (induction assumption), i.e. prove that A(k) ~ 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 assertion 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) X A(k+1). Based on the principle of mathematical induction, we conclude that the assumption A(n) is true for any n О N

Prove that

1 + x + x 2 + x 3 + ... + x n \u003d (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 true; 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+х+х 2 +x 3 +…+х 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 n(n-3)/2

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

A 3 \u003d 3 (3-3) / 2 \u003d 0 diagonals; A 2 A(3) true

2) Suppose that in any convex k-gon has A 1 sya A k \u003d k (k-3) / 2 diagonals. A k Let's 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 А 1 А 2 А 3 …A k A k+1 -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 a (k+1)-gon emanating from the vertex А k+1 , and, in addition, one should take into account the diagonal А 1 А k

In this way,

G k+1 =G 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 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 \u003d 1 2 \u003d 1 (1 + 1) (2 + 1) / 6 \u003d 1

2) Assume that n=k

X k \u003d k 2 \u003d k (k + 1) (2k + 1) / 6

3) Consider this statement for n=k+1

Xk+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 proved the validity of the equality for n=k+1, therefore, by virtue of the method of mathematical induction, the statement is true for any natural n

Prove that for any natural 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) Assume that the equality is true for n=k

X k \u003d 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

It can be seen from the above proof that the statement is true for n=k+1, therefore, the equality is true for any natural 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 is true
• 2) Assume that the expression is true for n=k
• (2 3 +1) / (2 3 -1) ґ ... ґ (k 3 +1) / (k 3 -1) \u003d 3k (k + 1) / 2 (k 2 + k + 1)
• 3) We will 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 proved the validity of the equality 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) Assume that n=k, then
• 1 3 -2 3 +3 3 -4 3 +…+(2k-1) 3 -(2k) 3 =-k 2 (4k+3)
• 3) We will 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 is also proved, therefore the statement is true for any natural n.

Prove the validity of the identity

(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) Assume that for n=k
• (1 2 /1 ґ 3)+…+(k 2 /(2k-1) ґ (2k+1))=k(k+1)/2(2k+1)
• 3) We 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)

It can be seen from the above proof that the assertion is true for any positive integer 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, so for n=1 the statement is true; A(1) is true.

• 2) Assume 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 2k+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 divisible 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) Yu A (k + 1). By virtue of the method of mathematical induction, the assertion is proved

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

• 1) Let n=1, then X 1 \u003d 7 1 -1 \u003d 6 is divided by 6 without a remainder. So for n=1 the statement is true
• 2) Suppose that for n \u003d 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 \u003d 7 k + 1 -1 \u003d 7 ґ 7 k -7 + 6 \u003d 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. So 7 n -1 is a multiple of 6 for any natural n. By virtue of the method of mathematical induction, the assertion is proved.

Prove that 3 3n-1 +2 4n-3 for an arbitrary positive integer n is divisible by 11.

1) Let n=1, then

X 1 \u003d 3 3-1 +2 4-3 \u003d 3 2 +2 1 \u003d 11 is divided by 11 without a remainder.

So 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) We 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. Hence, the sum is also divisible by 11 without a remainder for any natural n. By virtue of the method of mathematical induction, the assertion is proved.

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

• 1) Let n=1, then 11 2 -1=120 is divisible by 6 without a remainder. So for n=1 the statement is true
• 2) Suppose that for n=k 1 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 number 120, and the second is divisible by 6 without a remainder by assumption. So the sum is divisible by 6 without a remainder. By virtue of the method of mathematical induction, the assertion is proved.

Prove that 3 3n+3 -26n-27 for an arbitrary positive integer 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 divisible 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 3k+3 +(3 3k+3 -1) - is divisible by 26

Let us now prove the assertion formulated in the condition of the problem

• 1) It is obvious that 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 divisible by 26 2 without a remainder
• 3) Let's 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 proved that the expression in the brackets is divisible by 26, and the second is divisible by the inductive hypothesis. By virtue of the method of mathematical induction, the assertion is proved

Prove that if n>2 and х>0, then the inequality (1+х) n >1+n ґ х

• 1) For n=2, the inequality is true, 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+х) 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 a positive number 1+x, we obtain

(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+х) 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 valid for any n> 2

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

Solution: 1) For m=1

• (1+a+a 2) 1 > 1+a+(2/2) ґ a 2 both parts are equal
• 2) Assume 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 non-equality 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 proved the validity of the inequality for m=k+1, therefore, due to the method of mathematical induction, the inequality is valid for any natural m

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

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 validity of the inequality for n=k+1
• 3k+1 /2k+1 =(3k /2k) ґ (3/2)>2k ґ (3/2)=3k>2(k+1)

Since k>7, the last inequality is obvious.

Due to the method of mathematical induction, the inequality is valid for any natural n

Prove that for n>2 the inequality

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 Ы

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

Induction is a method of obtaining a general statement from particular observations. In the case when a mathematical statement concerns a finite number of objects, it can be proved by checking for each object. For example, the statement: “Every two-digit even number is the sum of two prime numbers,” follows from a series of equalities that are quite realistic to establish:

10=5+5 12=5+7 14=7+7 16=5+11 . . . 92=3+89 94=5+89 96=7+89 98=19+79.

The method of proof, in which a statement is verified for a finite number of cases, exhausting all possibilities, is called complete induction. This method is relatively rarely applicable, since mathematical statements, as a rule, concern not finite, but infinite sets of objects. For example, the statement about even two-digit numbers proved above by complete induction is only a special case of the theorem: "Any even number is the sum of two prime numbers." This theorem has not yet been proven or refuted.

Mathematical induction is a method of proving a certain statement for any natural n based on the principle of mathematical induction: “If a statement is true for n=1 and from its validity for n=k it follows that this statement is true for n=k+1, then it is true for all n ". The method of proof by mathematical induction is as follows:

1) base of induction: prove or directly verify the validity of the statement for n=1 (sometimes n=0 or n=n 0);

2) induction step (transition): they assume the validity of the statement for some natural n=k and, based on this assumption, prove the validity of the statement for n=k+1.

Problems with solutions

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

Denote A(n)=3 2n+1 +2 n+2 .

base of induction. If n=1, then A(1)=3 3 +2 3 =35 and obviously divisible by 7.

Induction hypothesis. Let A(k) be divisible by 7.

inductive transition. Let us prove that A(k+1) is divisible by 7, that is, the validity of the statement of the problem for n=k.

А(k+1)=3 2(k+1)+1 +2 (k+1)+2 =3 2k+1 3 2 +2 k+2 2 1 =3 2k+1 9+2 k+2 2=

3 2k+1 9+2 k+2 (9–7)=(3 2k+1 +2 k+2) 9–7 2 k+2 =9 A(k)–7 2 k +2 .

The last number is divisible by 7, since it is the difference of two integers divisible by 7. Therefore, 3 2n+1 +2 n+2 is divisible by 7 for any natural n.

2. Prove that for any positive integer n the number 2 3 n +1 is divisible by 3 n+1 and is not divisible by 3 n+2 .

Let's introduce the notation: a i =2 3 i +1.

For n=1 we have, and 1 =2 3 +1=9. So, a 1 is divisible by 3 2 and not divisible by 3 3 .

Let for n=k the number a k is divisible by 3 k+1 and not divisible by 3 k+2 , i.e. a k =2 3 k +1=3 k+1 m, where m is not divisible by 3. Then

and k+1 =2 3 k+1 +1=(2 3 k) 3 +1=(2 3 k +1)(2 3 k 2 –2 3 k +1)=3 k+1 m m ((2 3 k +1) 2 –3 2 3 k)=3 k+1 m ((3 k+1 m) 2 –3 2 3 k)=

3 k+2 m (3 2k+1 m 2 –2 3 k).

Obviously, a k+1 is divisible by 3 k+2 and is not divisible by 3 k+3 .

Therefore, the assertion is proved for any natural n.

3. It is known that x+1/x is an integer. Prove that х n +1/х n is also an integer for any integer n.

Let's introduce the notation: a i \u003d x i +1 / x i and immediately note that a i \u003d a -i, so we will continue to talk about natural indices.

Note: and 1 is an integer by condition; a 2 is an integer, since a 2 \u003d (a 1) 2 -2; and 0=2.

Assume that a k is an integer for any positive integer k not exceeding n. Then a 1 ·a n is an integer, but a 1 ·a n =a n+1 +a n–1 and a n+1 =a 1 ·a n –a n–1. However, and n–1 is an integer by the induction hypothesis. Hence, а n+1 is also an integer. Therefore, х n +1/х n is an integer for any integer n, which was to be proved.

4. Prove that for any positive integer n greater than 1, the double inequality

5. Prove that for natural n > 1 and |x|

(1–x)n +(1+x)n

For n=2 the inequality is true. Really,

(1–x) 2 + (1 + x) 2 \u003d 2 + 2 x 2

If the inequality is true for n=k, then for n=k+1 we have

(1–x)k+1 +(1+x)k+1

The inequality is proved for any natural number n > 1.

6. There are n circles on the plane. Prove that for any arrangement of these circles, the map formed by them can be correctly colored with two colors.

Let's use the method of mathematical induction.

For n=1 the assertion is obvious.

Assume that the statement is true for any map formed by n circles, and let n + 1 circles be given on the plane. Removing one of these circles, we get a map that, by virtue of the assumption made, can be correctly colored with two colors (see the first figure below).

We then restore the discarded circle and on one side of it, for example inside, change the color of each area to the opposite (see the second picture). It is easy to see that in this case we get a map correctly colored with two colors, but only now with n + 1 circles, which was to be proved.

7. We will call a convex polygon “beautiful” if the following conditions are met:

1) each of its vertices is painted in one of three colors;

2) any two neighboring vertices are painted in different colors;

3) at least one vertex of the polygon is colored in each of the three colors.

Prove that any beautiful n-gon can be cut by non-intersecting diagonals into "beautiful" triangles.

Let's use the method of mathematical induction.

base of induction. For the least possible n=3, the statement of the problem is obvious: the vertices of the "beautiful" triangle are painted in three different colors and no cuts are needed.

Induction hypothesis. Let us assume that the statement of the problem is true for any "beautiful" n-gon.

induction step. Consider an arbitrary "beautiful" (n + 1)-gon and prove, using the induction hypothesis, that it can be cut by some diagonals into "beautiful" triangles. Denote by А 1 , А 2 , А 3 , … А n , А n+1 – successive vertices of the (n+1)-gon. If only one vertex of the (n + 1)-gon is colored in any of the three colors, then by connecting this vertex with diagonals to all vertices not adjacent to it, we obtain the necessary partition of the (n + 1)-gon into “beautiful” triangles.

If at least two vertices of an (n + 1)-gon are painted in each of the three colors, then we denote the color of the vertex A 1 by the number 1, and the color of the vertex A 2 by the number 2. Let k be the smallest number such that the vertex A k is colored in the third color. It is clear that k > 2. Let us cut off the triangle А k–2 А k–1 А k from the (n+1)-gon with the diagonal А k–2 А k . In accordance with the choice of the number k, all the vertices of this triangle are painted in three different colors, that is, this triangle is "beautiful". The convex n-gon A 1 A 2 ... A k–2 A k A k+1 ... A n+1 , which remains, will also, due to the inductive assumption, be “beautiful”, which means it is divided into “beautiful” triangles, which and needed to be proven.

8. Prove that in a convex n-gon it is impossible to choose more than n diagonals so that any two of them have a common point.

Let's carry out the proof by the method of mathematical induction.

Let us prove a more general statement: in a convex n-gon, it is impossible to choose more than n sides and diagonals so that any two of them have a common point. For n = 3 the assertion is obvious. Let us assume that this assertion is true for an arbitrary n-gon and, using this, prove its validity for an arbitrary (n + 1)-gon.

Assume that for an (n + 1)-gon this statement is not true. If no more than two chosen sides or diagonals emerge from each vertex of an (n+1)-gon, then there are at most n+1 of them chosen. Therefore, at least three chosen sides or diagonals AB, AC, AD emerge from some vertex A. Let AC lie between AB and AD. Since any side or diagonal that comes out of C other than CA cannot cross AB and AD at the same time, only one chosen diagonal CA comes out of C.

Discarding the point C along with the diagonal CA, we get a convex n-gon in which more than n sides and diagonals are chosen, any two of which have a common point. Thus, we arrive at a contradiction with the assumption that the assertion is true for an arbitrary convex n-gon.

So, for an (n + 1)-gon, the statement is true. In accordance with the principle of mathematical induction, the statement is true for any convex n-gon.

9. There are n lines drawn in the plane, no two of which are parallel and no three pass through the same point. Into how many parts do these lines divide the plane.

With the help of elementary drawings, it is easy to make sure that one straight line divides the plane into 2 parts, two straight lines into 4 parts, three straight lines into 7 parts, and four straight lines into 11 parts.

Denote by N(n) the number of parts into which n lines divide the plane. It can be seen that

N(2)=N(1)+2=2+2,

N(3)=N(2)+3=2+2+3,

N(4)=N(3)+4=2+2+3+4.

It is natural to assume that

N(n)=N(n–1)+n=2+2+3+4+5+…+n,

or, as is easy to establish, using the formula for the sum of the first n terms of an arithmetic progression,

N(n)=1+n(n+1)/2.

Let us prove the validity of this formula by the method of mathematical induction.

For n=1, the formula has already been verified.

Having made the inductive assumption, consider k + 1 lines satisfying the condition of the problem. We arbitrarily select k straight lines from them. By the inductive hypothesis, they partition the plane into 1+ k(k+1)/2 parts. The remaining (k + 1)-th line will be divided by selected k lines into k + 1 parts and, therefore, will pass through the (k + 1)-th part into which the plane has already been divided, and each of these parts will be divided into 2 parts, that is, k+1 more parts will be added. So,

N(k+1)=N(k)+k+1=1+ k(k+1)/2+k+1=1+(k+1)(k+2)/2,

Q.E.D.

10. In the expression x 1: x 2: ...: x n, brackets are placed to indicate the order of actions and the result is written as a fraction:

(in this case, each of the letters x 1, x 2, ..., x n is either in the numerator of the fraction or in the denominator). How many different expressions can be obtained in this way with all possible ways of arranging brackets?

First of all, it is clear that in the resulting fraction x 1 will be in the numerator. It is almost equally obvious that x 2 will be in the denominator for any arrangement of brackets (the division sign before x 2 refers either to x 2 itself, or to any expression containing x 2 in the numerator).

It can be assumed that all other letters x 3 , x 4 , ... , x n can be located in the numerator or denominator in a completely arbitrary way. It follows that in total you can get 2 n-2 fractions: each of the n-2 letters x 3, x 4, ..., x n can be independently of the others in the numerator or denominator.

Let us prove this assertion by induction.

With n=3, you can get 2 fractions:

so the statement is true.

We assume that it is valid for n=k and prove it for n=k+1.

Let the expression x 1: x 2: ...: x k, after some arrangement of brackets, be written as a fraction Q. If x k: x k+1 is substituted into this expression instead of x k, then x k will be in the same place as it was in fractions Q, and x k + 1 will not be where x k stood (if x k was in the denominator, then x k + 1 will be in the numerator and vice versa).

Now let's prove that we can add x k+1 to the same place as x k . In the fraction Q, after placing the brackets, there will necessarily be an expression of the form q:x k, where q is the letter x k–1 or some expression in brackets. Replacing q: x k with the expression (q: x k): x k + 1 = q: (x k x k + 1), we obviously get the same fraction Q, where instead of x k is x k x k+1 .

Thus, the number of possible fractions in the case of n=k+1 is 2 times greater than in the case of n=k and is equal to 2 k–2 ·2=2 (k+1)–2 . Thus the assertion is proved.

Answer: 2 n-2 fractions.

Problems without solutions

1. Prove that for any natural n:

a) the number 5 n -3 n + 2n is divisible by 4;

b) the number n 3 +11n is divisible by 6;

c) the number 7 n +3n–1 is divisible by 9;

d) the number 6 2n +19 n –2 n+1 is divisible by 17;

e) the number 7 n+1 +8 2n–1 is divisible by 19;

f) the number 2 2n–1 –9n 2 +21n–14 is divisible by 27.

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

3. Prove the inequality |sin nx| n|sinx| for any natural n.

4. Find natural numbers a, b, c that are not divisible by 10 and such that for any natural n the numbers a n + b n and c n have the same last two digits.

5. Prove that if n points do not lie on the same line, then among the lines that connect them, there are at least n different ones.

METHOD OF MATHEMATICAL INDUCTION

The word induction in Russian means guidance, and inductive is called conclusions based on observations, experiments, i.e. 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 cause of 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 derivation correctly describes the observations that we will make tomorrow.

The role of inductive inferences in the experimental sciences is very great. They give those provisions, from which further conclusions are then made by deduction. And although theoretical mechanics is based on Newton's three laws of motion, these laws themselves were the result of a deep thinking through of experimental data, in particular, Kepler's laws of planetary motion, derived by him during the processing of long-term observations by the Danish astronomer Tycho Brahe. Observation and induction turn out to be useful in the future to refine 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 a theory of relativity.

In mathematics, the role of induction is largely that it underlies the chosen axiomatics. After a long 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 underlying notion of arithmetic to follow also emerged from observing the formation of soldiers, ships, and other ordered sets.

However, one should not think that this is the end of the role of induction in mathematics. Of course, we should not experimentally verify theorems that are logically deduced from axioms: if no logical errors were made in the derivation, then they are true insofar as the axioms we have 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 proved is again suggested by induction. It is she who allows us to separate useful theorems from useless ones, indicates which theorems may turn out to be true, and even helps to outline the path of the proof.

The essence of the method of mathematical induction

In many sections of arithmetic, algebra, geometry, analysis, one has to prove the truth of sentences A(n) that depend on a natural variable. The proof of the truth of the sentence A(n) for all values ​​of the variable can often be carried out by the method of mathematical induction, which is based on the following principle.

The sentence 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 hence accepted without proof.

The method of mathematical induction is understood as the following method of proof. If it is required to prove the truth of the proposition A(n) for all natural n, then, firstly, one should check the truth of the proposition A(1) and, secondly, assuming the truth of the proposition A(k), try to prove that the proposition A(k +1) true. If this can be proved, and the proof remains valid for every 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, one can prove various statements regarding the divisibility of natural numbers.

The following assertion can be proved relatively easily. 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.

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

Example 2Prove the truth of the sentence

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

Solution.

The statement A(1)=(number is a multiple of 19) is true.

Suppose that for some value n=k

A(k)=(number is a multiple of 19) is true. Then, since

Obviously, A(k+1) is also true. Indeed, the first term is divisible by 19 by virtue of the assumption that A(k) is true; the second term is also divisible by 19, because it contains the factor 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

series summation

Example 1Prove the formula

, n is a natural number.

Solution.

For n=1, both parts of the equality turn into one and, therefore, the first condition of the principle of mathematical induction is satisfied.

Assume that the formula is true 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 true for n=k+1 as well. 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 has been proven.

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

Solution.

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

For n=1, the hypothesis is true.

Let . Let us show that .

Indeed,

Problem solved.

Example 3Prove 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.

For 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 1Prove that for any natural number n>1

.

Solution.

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 natural k, the right side of the last equality is positive. That's why . But , therefore, and .

Example 2Find an error in reasoning.

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

Proof.

. (1)

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

.

Indeed, at least 2 for any natural k. Let's add inequality (1) to the left side, and 2 to the right side. We get a fair inequality , or . The assertion has been proven.

Example 3Prove 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 assumption, , therefore, the inequality

, (3)

obtained from inequality (1) by multiplying each part of it by . Let's rewrite inequality (3) as follows: . Discarding the positive term on the right side of the last inequality, we obtain the valid 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

. (3)

Adding to each part of inequality (3) by , we obtain inequality (2).

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

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

. (4)

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

(5)

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

. (6)

To prove inequality (5), it suffices to show that

, (7)

or, which is the same,

. (8)

Inequality (8) is equivalent to the 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 valid.

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

Method of mathematical induction as 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 the application to the solution of geometric computational problems. Let's look at a few examples.

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

Solution.

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

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

. (1)

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

,

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

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

Solution.

For a triangle, this number is equal to one (no diagonals can be drawn in a triangle); for a quadrilateral this number is obviously equal to 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 А 1 А k be one of the diagonals of this partition; it divides the n-gon А 1 А 2 …А n into the k-gon A 1 A 2 …A k and the (n-k+2)-gon А 1 А k A k+1 …A n . By virtue of the assumption made, the total number of partition triangles will be equal to

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

thus our assertion is proved for all n.

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

Solution.

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

Suppose we have already determined the numbers P(k) for all k 1 A 2 ... A n . For any partition of it into triangles, the side A 1 A 2 will be the side of one of the partition triangles, the third vertex of this triangle can coincide with each of the points A 3 , А 4 , …,А 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 to triangulate the (n-1)-gon A 1 A 3 A 4 ... A n , i.e. equals P(n-1). The number of partitioning ways 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); the number of partitioning ways 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 relation:

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

Using this formula, we successively 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.

Also, using the method of mathematical induction, you can solve problems with graphs.

Let a network of lines be given on the plane, connecting some points with each other and having no other points. We will call such a network of lines a map, the given points are its vertices, the segments of curves between two adjacent vertices - the borders of the map, the parts of the plane into which it is divided by the 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 in a certain color, and any two countries that share a common border are painted in different colors.

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

Solution.

For n=1 our assertion is obvious.

Suppose that our statement is true for any map formed by n circles, and let n + 1 circles be given 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.