Application of the method of mathematical induction to solving problems on the divisibility of natural numbers. The method of mathematical induction and its application to problem solving

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

Introduction

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

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

Goal of the work:

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

Job objectives:

Analyze the literature and summarize knowledge on this topic.

Understand the principle of the method of mathematical induction.

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

Formulate conclusions and conclusions about the work done.

Main part of the study

History:

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

Induction is a cognitive procedure through which a statement generalizing them is derived from a comparison of existing facts.

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

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

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 logically develop his thoughts, which means that nature itself destined him to think inductively.

Induction and deduction

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

Deduction (from Latin deductio - deduction) - a 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-made,” existing. The peculiarity of deduction is that the truth of its premises guarantees the truth of the conclusion. Therefore, deduction has enormous persuasive power 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 and cognition associated with generalizing the results of observations and experiments. A feature of induction is its probabilistic nature, i.e. If the initial premises are true, the conclusion of induction is only probably true and in the final result it can turn out to be either true or false.

Complete and incomplete induction

Inductive inference 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 arising from the premises is predominantly probabilistic in nature.

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

Complete induction is an inference in which a general conclusion about a class of objects is made based on the study of all objects of this class.

For example, let it be necessary to establish that every even natural number n within the range 6≤ n≤ 18 can be represented as the sum of two prime numbers. To do this, 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 we are interested in is indeed represented as the sum of two simple terms.

Consider the following example: sequence yn= n 2 +n+17; Let's write out the first four terms: y 1 =19; y 2 =23; y 3 =29; y 4 =37; Then we can assume that the entire 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 incorrect, thus, incomplete induction does not lead to completely reliable conclusions, but allows us to formulate a hypothesis, which subsequently 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 are not able to test for all these situations. But how can we 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 a sentence A(n), depending on a natural number n, is true for n=1 and from the fact that it is true for n=k (where k is any natural number), it follows that it is also true for the next number n=k +1, then assumption A(n) is true for any natural number n.

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

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

Algorithm (it consists of four stages):

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

2.assumption(we assume that the statement has been proven for the first To cases); 3 .step(under this assumption we prove the statement for the case P = To + 1); 4.output (at the statement is true for all cases, that is, for all P) .

Note that the method of mathematical induction can not solve all problems, but only problems parameterized by a certain variable. This variable is called the induction variable.

Application of the method of mathematical induction

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

Problems to prove inequalities.

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

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

2) Suppose 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

Taking into account that kx 2 ≥0, we arrive at the inequality

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

Thus, from the assumption that Bernoulli's inequality is true for n=k, it follows 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's prove it using the method of mathematical induction.

Let us denote the left side of the inequality by.

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

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

Comparing and, we have, i.e. .

For any positive integer k, the right-hand side of the last equality is positive. That's why. But that means and. We have proven the validity of the inequality for n=k+1, therefore, by virtue of the method of mathematical induction, the inequality is valid for any natural number n>1.

Problems to prove identities.

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

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

Example 2. Prove that for any natural n the equality is true

1) Let us check that this identity is true for n = 1.; - right.

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

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

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

Summation problems.

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

In fact, 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 the 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, then this statement is true for any natural number n.

Divisibility problems.

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

(23×133) is divisible by 133 without a remainder, which means that 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 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), 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 natural number 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. 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 a remainder for any natural number n.

Problems from real life.

Example 1. Prove that the sum Sn of interior angles of any convex polygon is equal to ( P- 2)π, where P— 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 correct.

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 holds: S k+ 1 = (k- 1)π.

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

Connecting points A 1 and A k , we get convex k-gon A 1 A 2 ... A k — 1 A k . Obviously, the sum of the angles ( k+ 1) -gon A 1 A 2 ... A k A k+ 1 is equal to the sum of the angles k-gon A 1 A 2 ... A k plus the sum of the angles of a triangle A 1 A k A k+ 1 . But the sum of the angles k-gon A 1 A 2 ... A k by assumption equal to ( k- 2)π, and the sum of the angles of the triangle A 1 A k A k+ 1 is equal to π. 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 steps of which are the same. It is required to indicate the minimum number of positions that would guarantee the ability to “climb” onto any step by number.

Everyone agrees that there must be a condition. We must be able to climb to the first step. Next, they must be able to climb from the 1st step to the second. Then to the second - to the third, etc. to the nth step. Of course, in totality, “n” statements guarantee that we will be able to get to the nth step.

Let's now look at the 2, 3,..., n position and compare them with each other. It is easy to see that they all have the same structure: if we have reached the k step, then we can climb up to the (k+1) step. Hence, the following axiom becomes natural for the validity of statements depending on “n”: if a sentence A(n), in which n is a natural number, holds for n=1 and from the fact that it holds for n=k (where k is any natural number), it follows that it holds for n=k+1, then assumption A(n) holds for any natural number n.

Application

Problems using the method of mathematical induction when entering universities.

Note that when entering higher educational institutions, there are also problems that can be solved by this method. Let's look at them using specific examples.

Example 1. Prove that any natural P equality is true

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

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

3) Using reduction formulas, we transform the expression:

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

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

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

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

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

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

4(4 k +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 is what needed to be proven.

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

1) Let's check that this formula is correct when n=1: Left side = 1∙2∙3=6.

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

2) Suppose 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 has been proven to be 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 can be complete or incomplete, got acquainted with the method of mathematical induction based on the principle of mathematical induction, and 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. This knowledge also increases interest in mathematics as a science.

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

Bibliography

Sominsky I.S. Method of mathematical induction. Popular lectures on mathematics, issue 3-M.: Science, 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. A manual on mathematics for those entering universities (Selected questions of elementary mathematics) - 5th edition, revised, 1976 - 638 pp.

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

M.L. Galitsky, A.M. Goldman, L.I. Zvavich Collection of problems in algebra: textbook for grades 8-9. with depth studying mathematics 7th ed. - M.: Prosveshchenie, 2001. - 271 p.

Ma-ka-ry-chev Yu.N., Min-dyuk N.G Additional chapters for the school textbook of al-geb-ry 9th grade. - M.: Pro-sve-shche-nie, 2002.

Wikipedia is a free encyclopedia.

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

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

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

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)

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.

Mathematical induction is the basis of one of the most common methods of mathematical proof. 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 consider the basics of the method itself, and then 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 a transition from the particular to the general, and deduction on the contrary – from the general to the specific.

For example, we have a statement: 254 can be divided by two. From it we can draw many conclusions, including both true and false. For example, the statement that all integers that end with the number 4 can be divided by two without a remainder is true, but the statement 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 a single known or obvious reasoning. Mathematical induction allows us to determine how valid these conclusions are.

Let's say 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 = 1 1 2 = 1 2, S 2 = 1 1 2 + 1 2 3 = 2 3, S 3 = 1 1 2 + 1 2 3 + 1 3 4 = 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 valid for an arbitrary natural value n = k, it follows that it will be true for n = k + 1 .

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

First, we check the validity of the original statement in the case of an arbitrary natural value of n (usually the check is done for unity).
After this we check for validity when n = k.
And then we prove the validity of the statement if n = k + 1.

How to use the method of mathematical induction to solve 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 sequential steps must be performed.

First, we check whether this equality will be valid for n equal to one. We get S 1 = 1 1 · 2 = 1 1 + 1 = 1 2 . Everything is correct here.
Next, we make the assumption that the formula S k = k k + 1 is correct.
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 action we received 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 similar terms, apply the abbreviated multiplication formula and reduce what we get:

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 proven the equality in the third point by completing 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 α = sin 2 n + 1 α 2 n sin 2 α .

Solution

As we remember, the first step should be to check the validity of the equality when n equals 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 let’s assume that its validity remains true for n = k, i.e. it will be true that cos 2 α · cos 4 α · . . . · cos 2 k α = 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, taking the previous assumption as a basis.

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 α

Hence,

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 α

We gave an example of solving a problem to prove an inequality using this method in the article about the least squares method. Read the paragraph where formulas for finding approximation coefficients are derived.

If you notice an error in the text, please highlight it and press Ctrl+Enter

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

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

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

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

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

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

Rice. 1. Scheme for solving the problem

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

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

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

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

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

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

Proof:

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

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

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

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

Proof:

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

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

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

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

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

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

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

Proof:

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

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

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

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

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

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

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

Literature:

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

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

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

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

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

Lecture 6. Method of mathematical induction.

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

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

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

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

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

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

6.1. The principle of mathematical induction.

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

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

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

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

1) statement for n=m not fair,

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

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

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

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

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

Solution.

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

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

Indeed,

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

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

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

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

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

We use our assumption and get

. ■ 

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

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

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

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

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

That is (1+
.■ 

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

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

 Example6.4. Find the amount
.

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

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

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

Indeed,

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

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

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

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

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

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

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

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

Because
and at
there is inequality

at
,

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

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

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

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

Q.E.D. ■ 

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

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

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

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

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

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