True knowledge at all times was based on establishing a pattern and proving its veracity in certain circumstances. For such a long period of existence of logical reasoning, the formulations of the rules were given, and Aristotle even compiled a list of "correct reasoning." Historically, it is customary to divide all inferences into two types - from the concrete to the plural (induction) and vice versa (deduction). It should be noted that the types of evidence from particular to general and from general to particular exist only in interconnection and cannot be interchanged.

Induction in mathematics

The term "induction" (induction) has Latin roots and literally translates as "guidance". Upon closer study, one can distinguish the structure of the word, namely the Latin prefix - in- (denotes directed action inward or being inside) and -duction - introduction. It is worth noting that there are two types - complete and incomplete induction. The full form is characterized by conclusions drawn from the study of all subjects of a certain class.

Incomplete - conclusions applied to all subjects of the class, but made on the basis of the study of only some units.

Complete mathematical induction is a conclusion based on a general conclusion about the entire class of any objects that are functionally related by relations of the natural series of numbers based on knowledge of this functional connection. In this case, the proof process takes place in three stages:

• at the first stage, the correctness of the statement of mathematical induction is proved. Example: f = 1, induction;
• the next stage is based on the assumption that the position is valid for all natural numbers. That is, f=h, this is the inductive assumption;
• at the third stage, the validity of the position for the number f=h+1 is proved, based on the correctness of the position of the previous paragraph - this is an induction transition, or a step of mathematical induction. An example is the so-called if the first bone in the row falls (basis), then all the bones in the row fall (transition).

Both jokingly and seriously

For ease of perception, examples of solutions by the method of mathematical induction are denounced in the form of joke problems. This is the Polite Queue task:

• The rules of conduct forbid a man to take a turn in front of a woman (in such a situation, she is let in front). Based on this statement, if the last one in line is a man, then all the rest are men.

A striking example of the method of mathematical induction is the problem "Dimensionless flight":

• It is required to prove that any number of people fit in the minibus. It is true that one person can fit inside the transport without difficulty (basis). But no matter how full the minibus is, 1 passenger will always fit in it (induction step).

familiar circles

Examples of solving problems and equations by mathematical induction are quite common. As an illustration of this approach, we can consider the following problem.

Condition: h circles are placed on the plane. It is required to prove that, for any arrangement of the figures, the map formed by them can be correctly colored with two colors.

Solution: for h=1 the truth of the statement is obvious, so the proof will be built for the number of circles h+1.

Let us assume that the statement is true for any map, and h + 1 circles are given on the plane. By removing one of the circles from the total, you can get a map correctly colored with two colors (black and white).

When restoring a deleted circle, the color of each area changes to the opposite (in this case, inside the circle). It turns out a map correctly colored in two colors, which was required to be proved.

Examples with natural numbers

The application of the method of mathematical induction is clearly shown below.

Solution examples:

Prove that for any h the equality will be correct:

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

1. Let h=1, then:

R 1 \u003d 1 2 \u003d 1 (1 + 1) (2 + 1) / 6 \u003d 1

It follows from this that for h=1 the statement is correct.

2. Assuming that h=d, the following equation is obtained:

R 1 \u003d d 2 \u003d d (d + 1) (2d + 1) / 6 \u003d 1

3. Assuming that h=d+1, it turns out:

R d+1 =(d+1) (d+2) (2d+3)/6

R d+1 = 1 2 +2 2 +3 2 +…+d 2 +(d+1) 2 = d(d+1)(2d+1)/6+ (d+1) 2 =(d( d+1)(2d+1)+6(d+1) 2)/6=(d+1)(d(2d+1)+6(k+1))/6=

(d+1)(2d 2 +7d+6)/6=(d+1)(2(d+3/2)(d+2))/6=(d+1)(d+2)( 2d+3)/6.

Thus, the validity of the equality for h=d+1 has been proven, so the statement is true for any natural number, which is shown in the solution example by mathematical induction.

A task

Condition: proof is required that for any value of h, the expression 7 h -1 is divisible by 6 without a remainder.

Solution:

1. Let's say h=1, in this case:

R 1 \u003d 7 1 -1 \u003d 6 (i.e. divided by 6 without a remainder)

Therefore, for h=1 the statement is true;

2. Let h=d and 7 d -1 is divisible by 6 without a remainder;

3. The proof of the validity of the statement for h=d+1 is the formula:

R d +1 =7 d +1 -1=7∙7 d -7+6=7(7 d -1)+6

In this case, the first term is divisible by 6 by the assumption of the first paragraph, and the second term is equal to 6. The statement that 7 h -1 is divisible by 6 without a remainder for any natural h is true.

Fallacy of judgment

Often, incorrect reasoning is used in proofs, due to the inaccuracy of the logical constructions used. Basically, this happens when the structure and logic of the proof are violated. An example of incorrect reasoning is the following illustration.

A task

Condition: requires a proof that any pile of stones is not a pile.

Solution:

1. Let's say h=1, in this case there is 1 stone in the pile and the statement is true (basis);

2. Let it be true for h=d that a pile of stones is not a pile (assumption);

3. Let h=d+1, from which it follows that when one more stone is added, the set will not be a heap. The conclusion suggests itself that the assumption is valid for all natural h.

The error lies in the fact that there is no definition of how many stones form a pile. Such an omission is called hasty generalization in the method of mathematical induction. An example shows this clearly.

Induction and the laws of logic

Historically, they always "walk hand in hand." Such scientific disciplines as logic, philosophy describe them in the form of opposites.

From the point of view of the law of logic, reliance on facts is seen in inductive definitions, and the veracity of the premises does not determine the correctness of the resulting statement. Often conclusions are obtained with a certain degree of probability and plausibility, which, of course, must be verified and confirmed by additional research. An example of induction in logic would be the statement:

Drought in Estonia, drought in Latvia, drought in Lithuania.

Estonia, Latvia and Lithuania are the Baltic states. Drought in all Baltic states.

From the example, we can conclude that new information or truth cannot be obtained using the method of induction. All that can be counted on is some possible veracity of the conclusions. Moreover, the truth of the premises does not guarantee the same conclusions. However, this fact does not mean that induction vegetates in the backyard of deduction: a huge number of provisions and scientific laws are substantiated using the method of induction. Mathematics, biology and other sciences can serve as an example. This is mainly due to the method of complete induction, but in some cases partial is also applicable.

The venerable age of induction allowed it to penetrate into almost all spheres of human activity - this is science, economics, and everyday conclusions.

Induction in the scientific environment

The method of induction requires a scrupulous attitude, since too much depends on the number of particulars of the whole studied: what more studied, the more reliable the result. Based on this feature, the scientific laws obtained by the method of induction are tested for a sufficiently long time at the level of probabilistic assumptions in order to isolate and study all possible structural elements, connections and influences.

In science, the inductive conclusion is based on significant features, with the exception random positions. This fact is important in connection with the specific scientific knowledge. This is clearly seen in the examples of induction in science.

There are two types of induction in the scientific world (in connection with the method of study):

1. induction-selection (or selection);
2. induction - exclusion (elimination).

The first type is distinguished by methodical (scrutinous) sampling of a class (subclasses) from its different areas.

An example of this type of induction is as follows: silver (or silver salts) purifies water. The conclusion is based on long-term observations (a kind of selection of confirmations and refutations - selection).

The second type of induction is based on conclusions establishing causality and excluding circumstances that do not meet its properties, namely, universality, observance of the temporal sequence, necessity and unambiguity.

Induction and deduction from the standpoint of philosophy

If you look at the historical retrospective, the term "induction" was first mentioned by Socrates. Aristotle described examples of induction in philosophy in a more approximate terminological dictionary, but the question of incomplete induction remains open. After the persecution of the Aristotelian syllogism, the inductive method began to be recognized as fruitful and the only possible one in natural science. Bacon is considered the father of induction as an independent special method, but he failed to separate, as his contemporaries demanded, induction from the deductive method.

Further development of induction was carried out by J. Mill, who considered the induction theory from the standpoint of four main methods: agreement, difference, residues and corresponding changes. It is not surprising that today the listed methods, when considered in detail, are deductive.

Awareness of the failure of the theories of Bacon and Mill led scientists to study probabilistic basis induction. However, even here there were some extremes: attempts were made to reduce the induction to the theory of probability, with all the ensuing consequences.

Induction gets a vote of confidence in practical application in certain subject areas and thanks to the metric accuracy of the inductive basis. An example of induction and deduction in philosophy is the Law gravity. At the date of discovery of the law, Newton was able to verify it with an accuracy of 4 percent. And when checking after more than two hundred years, the correctness was confirmed with an accuracy of 0.0001 percent, although the check was carried out by the same inductive generalizations.

Modern philosophy pays more attention to deduction, which is dictated by a logical desire to derive new knowledge (or truth) from what is already known, without resorting to experience, intuition, but using "pure" reasoning. When referring to true premises in the deductive method, in all cases, the output is a true statement.

This very important characteristic should not overshadow the value of the inductive method. Since induction, based on the achievements of experience, also becomes a means of its processing (including generalization and systematization).

Application of induction in economics

Induction and deduction have long been used as methods of studying the economy and predicting its development.

The range of use of the induction method is quite wide: the study of the fulfillment of forecast indicators (profit, depreciation, etc.) and a general assessment of the state of the enterprise; formation of an effective enterprise promotion policy based on facts and their relationships.

The same method of induction is used in Shewhart's charts, where, under the assumption that processes are divided into controlled and unmanaged, it is stated that the framework of the controlled process is inactive.

It should be noted that scientific laws are substantiated and confirmed using the method of induction, and since economics is a science that often uses mathematical analysis, risk theory and statistical data, it is not surprising that induction is included in the list of main methods.

The following situation can serve as an example of induction and deduction in economics. An increase in the price of food (from the consumer basket) and essential goods pushes the consumer to think about the emerging high cost in the state (induction). At the same time, from the fact of high cost with the help of mathematical methods it is possible to derive indicators of price growth for individual goods or categories of goods (deduction).

Most often, management personnel, managers, and economists turn to the induction method. In order to be able to predict the development of an enterprise, market behavior, and the consequences of competition with sufficient truthfulness, an inductive-deductive approach to the analysis and processing of information is necessary.

An illustrative example of induction in economics, referring to fallacious judgments:

• the company's profit decreased by 30%;
  a competitor has expanded its product line;
  nothing else has changed;
• the production policy of a competing company caused a profit cut of 30%;
• therefore, the same production policy needs to be implemented.

The example is a colorful illustration of how the inept use of the method of induction contributes to the ruin of an enterprise.

Deduction and induction in psychology

Since there is a method, then, logically, there is also a properly organized thinking (for using the method). Psychology as a science that studies mental processes, their formation, development, relationships, interactions, pays attention to "deductive" thinking as one of the forms of manifestation of deduction and induction. Unfortunately, on the pages of psychology on the Internet, there is practically no justification for the integrity of the deductive-inductive method. Although professional psychologists are more likely to encounter manifestations of induction, or rather, erroneous conclusions.

An example of induction in psychology, as an illustration of erroneous judgments, is the statement: my mother is a deceiver, therefore, all women are deceivers. There are even more “erroneous” examples of induction from life:

• a student is not capable of anything if he received a deuce in mathematics;
• he is a fool;
• he is smart;
• I can do everything;

And many other value judgments based on absolutely random and sometimes insignificant messages.

It should be noted: when the fallacy of a person's judgments reaches the point of absurdity, a front of work appears for the psychotherapist. One example of induction at a specialist appointment:

“The patient is absolutely sure that the red color carries only danger for him in any manifestations. As a result, a person has excluded this color scheme from his life - as far as possible. At home opportunities for comfortable living a lot of. You can refuse all red items or replace them with analogues made in a different color scheme. But in public places, at work, in the store - it is impossible. Getting into a situation of stress, the patient each time experiences a “tide” of completely different emotional states which may pose a danger to others."

This example of induction, and unconsciously, is called "fixed ideas." If this happens to a mentally healthy person, we can talk about a lack of organization mental activity. The elementary development of deductive thinking can become a way to get rid of obsessive states. In other cases, psychiatrists work with such patients.

The above examples of induction indicate that "ignorance of the law does not exempt from the consequences (erroneous judgments)."

Psychologists, working on the topic of deductive thinking, have compiled a list of recommendations designed to help people master this method.

The first step is problem solving. As can be seen, the form of induction used in mathematics can be considered "classical", and the use of this method contributes to the "discipline" of the mind.

The next condition for the development of deductive thinking is the expansion of horizons (those who think clearly, clearly state). This recommendation directs the "suffering" to the treasuries of science and information (libraries, websites, educational initiatives, travel, etc.).

Separately, mention should be made of the so-called "psychological induction". This term, although infrequently, can be found on the Internet. All sources do not give at least a brief definition of this term, but refer to "examples from life", while passing off either suggestion, some forms of mental illness, or extreme states of the human psyche as a new type of induction. From all of the above, it is clear that an attempt to derive a “new term” based on false (often untrue) premises dooms the experimenter to receive an erroneous (or hasty) statement.

It should be noted that the reference to the 1960 experiments (without indicating the venue, the names of the experimenters, the sample of subjects, and most importantly, the purpose of the experiment) looks, to put it mildly, unconvincing, and the statement that the brain perceives information bypassing all the organs of perception (the phrase “experienced” in this case would fit in more organically), makes one think about the gullibility and uncriticality of the author of the statement.

Instead of a conclusion

The queen of sciences - mathematics, not in vain uses all possible reserves of the method of induction and deduction. The considered examples allow us to conclude that the superficial and inept (thoughtless, as they say) application of even the most accurate and reliable methods always leads to erroneous results.

In the mass consciousness, the deduction method is associated with the famous Sherlock Holmes, who in his logical constructions often uses examples of induction, using deduction in necessary situations.

The article considered examples of the application of these methods in various sciences and spheres of human life.

MBOU Lyceum "Technical and Economic"

METHOD OF MATHEMATICAL INDUCTION

METHOD OF MATHEMATICAL INDUCTION.

EXPLANATORY NOTE

Methodical development"The method of mathematical induction" was compiled for students of the 10th grade of the mathematical profile.

Primary goals: to acquaint students with the method of mathematical induction and teach how to apply it in solving various problems.

In the methodological development, questions of elementary mathematics are considered: divisibility problems, proof of identities, proof of inequalities, problems of varying degrees of complexity are proposed, including problems offered at olympiads.

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. Name method of mathematical induction deceptively - in fact, this method is deductive and gives a rigorous proof of the statements guessed by induction. The method of mathematical induction helps to identify links between different sections of mathematics, helps to develop the mathematical culture of the student.

Definition of the method of mathematical induction. Complete and incomplete induction. Proof of inequalities. Proof of identities. Solving divisibility problems. Solving various problems on the topic "Method of mathematical induction".

LITERATURE FOR THE TEACHER

1. M.L. Galitsky. Deep Learning course of algebra and mathematical analysis. - M. Enlightenment. 1986.

2. L.I. Zvavich. Algebra and the beginnings of analysis. Didactic materials. M. Drofa. 2001.

3. N.Ya. Vilenkin. Algebra and mathematical analysis. M Enlightenment. 1995.

4. Yu.V. Mikheev. Method of mathematical induction. NGU.1995.

LITERATURE FOR STUDENTS

1. N.Ya. Vilenkin. Algebra and mathematical analysis. M Enlightenment. 1995.

2. Yu.V. Mikheev. Method of mathematical induction. NGU.1995.

KEYWORDS

Induction, axiom, principle of mathematical induction, complete induction, incomplete induction, assertion, identity, inequality, divisibility.

DIDACTIC APPENDIX TO THE TOPIC

"METHOD OF MATHEMATICAL INDUCTION".

Lesson #1

Definition of the method of mathematical induction.

The method of mathematical induction is one of the highly effective methods for finding new results and proving the truth of the assumptions put forward. Although this method is not new in mathematics, interest in it does not wane. For the first time in a clear presentation, the method of mathematical induction was applied in the 17th century by the outstanding French scientist Blaise Pascal in proving the properties of a number triangle, which has since been named after him. However, the idea of ​​mathematical induction was known to the ancient Greeks. The method of mathematical induction is based on the principle of mathematical induction, which is accepted as an axiom. We will consider the idea of ​​mathematical induction with examples.

Example #1.

The square is divided by a segment into two parts, then one of the resulting parts is divided into two parts, and so on. Determine how many parts the square is divided into P steps?

Solution.

After the first step, we, by condition, get 2 parts. In the second step, we leave one part unchanged, and divide the second into 2 parts and get 3 parts. In the third step, we leave 2 parts unchanged, and divide the third into two parts and get 4 parts. In the fourth step, we leave 3 parts unchanged, and divide the last part into two parts and get 5 parts. In the fifth step, we will get 6 parts. The suggestion is made that through P steps we get (n+1) part. But this proposition needs to be proven. Let's assume that through to steps the square is divided into (k+1) part. Then on (k+1) step we to parts will be left unchanged, and (k+1) divide the part into two parts and get (k+2) parts. You notice that you can argue like this for as long as you like, ad infinitum. That is, our assumption is that P steps square will be divided into (n+1) part, becomes proven.

Example #2.

My grandmother had a granddaughter who was very fond of jam, and especially the one in a liter jar. But the grandmother did not allow him to touch. And the granddaughters decided to deceive their grandmother. He decided to eat every day 1/10 liter from this jar and top it up with water, mixing thoroughly. After how many days will grandmother discover the deception if the jam remains the same in appearance when diluted with water by half?

Solution.

Find how much pure jam will remain in the jar after P days. After the first day, the mixture will remain in the jar, consisting of 9/10 jam and 1/10 water. After two days, 1/10 of the mixture of water and jam will disappear from the jar and remain (1 liter of the mixture contains 9/10 liters of jam, 1/10 liters of the mixture contains 9/100 liters of jam)

9/10 - 9/100=81/100=(9/10) 2 liters of jam. On the third day, 1/10 liter of a mixture consisting of 81/100 jam and 19/100 water will disappear from the jar. In 1 liter of the mixture there are 81/100 liters of jam, in 1/10 liters of the mixture 81/1000 liters of jam. 81/100 – 81/1000=

729/1000=(9/10) 3 liters of jam will be left after 3 days, and the rest will be taken up by water. A pattern emerges. Through P days left in the bank (9/10) P l jam. But again, this is just our guess.

Let to is an arbitrary natural number. Let's assume that through to days in the bank will remain (9/10) to l jam. Let's see what will be in the bank in another day, that is, in (k+1) day. Will disappear from the bank 1/10l a mixture of (9/10) to l jam and water. AT 1l mixture is (9/10) to l jam, in 1/10l mixtures (9/10) k+1 l jam. Now we can safely say that through P days left in the bank (9/10) P l jam. In 6 days the bank will have 531444/1000000l jams, after 7 days - 4782969/10000000l jam, that is, less than half.

Answer: after 7 days, the grandmother will discover the deception.

Let us try to single out the most basic in the solutions of the considered problems. We began to solve each of them by considering separate or, as they say, special cases. Then, based on our observations, we made some assumptions P(n), depending on the natural P.

the assertion was checked, that is, proved P(1), P(2), P(3);

suggested that P(n) valid for n=k and deduced that then it will be valid for the next n, n=k+1.

And then they argued something like this: P(1) right, P(2) right, P(3) right, P(4) right... that's right P(n).

The principle of mathematical induction.

Statement P(n), depending on the natural P, is valid for all natural P, if

1) the validity of the assertion for n=1;

2) from the assumption of the validity of the statement P(n) at n=k should

justice P(n) at n=k+1.

In mathematics, the principle of mathematical induction is chosen, as a rule, as one of the axioms that define the natural series of numbers, and, therefore, is accepted without proof. The method of proof by the principle of mathematical induction is usually called the method of mathematical induction. Note that this method is widely used in proving theorems, identities, inequalities in solving divisibility problems and many other problems.

Lesson #2

Complete and incomplete induction.

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." The method of proof in which we test a statement for a finite number of cases is called complete mathematical induction. This method is used relatively rarely, since statements are most often considered on infinite sets. For example, the theorem "Any even number is equal to the sum of two prime numbers" has neither been proven nor refuted so far. Even if we tested this theorem for the first billion, it would not bring us one step closer to proving it.

AT natural sciences apply incomplete induction, checking the experiment several times, transferring the result to all cases.

Example #3

Guess using incomplete induction formula for the sum of cubes of natural numbers.

Solution.

1 3 =1; 1 3 +2 3 =(1+2) 2 ; 1 3 +2 3 +3 3 =(1+2+3) 2 ; 1 3 +2 3 +3 3 +4 3 =(1+2+3+4) 2 ;

1 3 +2 3 +3 3 +4 3 +5 3 =(1+2+3+4+5) 2 ; …; 1 3 +2 3 +…+n 3 =(1+2+…+n) 2 .

Proof.

Let it be true for n=k.

Let's prove that is true for n=k+1.

Conclusion: the formula for the sum of cubes of natural numbers is true for any natural P.

Example #4

Consider the equalities and guess what general law these examples lead to.

Solution.

1=0+1

2+3+4=1+8

5+6+7+8+9=8+27

10+11+12+13+14+15+16=27+64

17+18+19+20+21+22+23+24+25=64+125

……………………………………………………………..

Example #5

Write as a sum the following expressions:

1)
2)
3)
; 4)
.

Greek letter "sigma".

Example #6.

Write the following sums using the sign
:

2)

Example #7.

Write the following expressions as products:

1)

3)
4)

Example #8.

Write down the following works using the sign

(capital Greek letter "pi")

1)
2)

Example #9.

Computing the value of a polynomial f ( n )= n 2 + n +11 , at n=1,2,3,4.5,6,7 it can be assumed that for any naturalP number f ( n ) simple.

Is this assumption correct?

Solution.

If each summand is divisible by a number, then the sum is divisible by that number,
is not a prime number for any natural numberP.

The analysis of a finite number of cases plays an important role in mathematics: without giving a proof of one or another statement, it helps to guess the correct formulation of this statement, if it is not yet known. This is how Goldbach, a member of the St. Petersburg Academy of Sciences, came to the conjecture that any natural number, starting from two, is the sum of no more than three primes.

Lesson #3

The method of mathematical induction allows us to prove various identities.

Example #10. Let us prove that for all P the identity

Solution.

Let's put

We need to prove that

Let us prove that Then from the truth of the identity

the truth of the identity follows

By the principle of mathematical induction, the truth of the identity for all P.

Example #11.

Let's prove the identity

Proof.

term-by-term equalities.

;
. So this identity is true for allP .

Lesson number 4.

Proof of identities by mathematical induction.

Example #12. Let's prove the identity

Proof.

Applying the principle of mathematical induction, we proved that the equality is true for all P.

Example #13. Let's prove the identity

Proof.

Applying the principle of mathematical induction, we proved that the statement is true for any natural P.

Example #14. Let's prove the identity

Proof.

Example #15. Let's prove the identity

1) n=1;

2) for n=k equality

3) prove that the equality holds for n=k+1:

Conclusion: the identity is valid for any natural P.

Example #16. Let's prove the identity

Proof.

If a n=1 , then

Let the identity hold for n=k.

Let us prove that the identity holds for n=k+1.

Then the identity is valid for any natural P.

Lesson number 5.

Proof of identities by mathematical induction.

Example #17. Let's prove the identity

Proof.

If a n=2 , then we get the correct equality:

Let the equality be true forn=k:

Let us prove the validity of the assertion for n=k+1.

According to the principle of mathematical induction, the identity is proved.

Example #18. Let's prove the identity
for n≥2.

At n=2 this identity can be rewritten in a very simple form

and obviously true.

Let at n=k really

.

Let us prove the validity of the assertion forn=k+1, that is, the equality is satisfied: .

So, we have proved that the identity is true for any natural n≥2.

Example #19. Let's prove the identity

At n=1 we get the correct equality:

Let's assume that at n=k we also get the correct equality:

Let us prove that the validity of the equality is observed for n=k+1:

Then the identity is valid for any natural P.

Lesson number 6.

Solving divisibility problems.

Example #20. Prove by mathematical induction that

divided by 6 without a trace.

Proof.

At n=1 there is a division into6 without a trace,
.

Let at n=k expression
multiple6.

Let us prove that when n=k+1 expression
multiple6 .

Each term is a multiple 6 , so the sum is a multiple of 6 .

Example number 21.
on the5 without a trace.

Proof.

At n=1 expression is divisible
.

Let at n=k expression
also divided into5 without a trace.

At n=k+1 divided by 5 .

Example #22. Prove the divisibility of an expression
on the16.

Proof.

At n=1 multiple 16 .

Let at n=k
multiple16.

At n=k+1

All terms are divisible by 16: the first is obviously the second by assumption, and the third has an even number in brackets.

Example #23. Prove divisibility
on the676.

Proof.

Let us first prove that
divided by
.

At n=0
.

Let at n=k
divided by26 .

Then at n=k+1 divided by 26 .

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

At n=1 divided by 676.

At n=k it is true that
divided by26 2 .

At n=k+1 .

Both terms are divisible by 676 ; the first is because we have proved the divisibility by 26 expression in brackets, and the second is divisible by the inductive hypothesis.

Lesson number 7.

Solving divisibility problems.

Example number 24.

Prove that
divided by5 without a trace.

Proof.

At n=1
divided by5.

At n=k
divided by5 without a trace.

At n=k+1 each term is divisible by5 without a trace.

Example #25.

Prove that
divided by6 without a trace.

Proof.

At n=1
divided by6 without a trace.

Let at n=k
divided by6 without a trace.

At n=k+1 divided by 6 no remainder, since each term is divisible by6 without a remainder: the first term, by the inductive assumption, the second, obviously, the third, because
even number.

Example #26.

Prove that
when dividing by9 gives the remainder 1 .

Proof.

Let's prove that
divided by9 .

At n=1
divided by 9 . Let at n=k
divided by9 .

At n=k+1 divided by 9 .

Example number 27.

Prove that is divisible by15 without a trace.

Proof.

At n=1 divided by 15 .

Let at n=k divided by 15 without a trace.

At n=k+1

The first term is a multiple15 by the induction hypothesis, the second term is a multiple of15 – obviously, the third term is a multiple of15 , because
multiple5 (proved in example No. 21), the fourth and fifth terms are also multiples5 , which is obvious, then the sum is a multiple of15 .

Lesson number 8-9.

Proof of inequalities by mathematical induction

Example #28.
.

At n=1 we have
- right.

Let at n=k
is a true inequality.

At n=k+1

Then the inequality is valid for any natural P.

Example #29. Prove that the inequality is true
for any P.

At n=1 we get the correct inequality 4 >1.

Let at n=k the inequality
.

Let us prove that when n=k+1 the inequality

For any natural to inequality is observed.

If a
at
then

Example #30.

for any natural P and any

Let n=1
, right.

Let us assume that the inequality holds for n=k:
.

At n=k+1

Example number 31. Prove the validity of the inequality

for any natural P.

Let us first prove that for any natural t the inequality

Multiply both sides of the inequality by
. We obtain an equivalent inequality or
;
; - this inequality holds for any natural t.

At n=1 original inequality is true
;
;
.

Let the inequality hold for n=k:
.

At n=k+1

Lesson number 10.

Solving problems on the topic

Method of mathematical induction.

Example #32. Prove Bernoulli's inequality.

If a
, then for all natural valuesP the inequality

Proof.

At n=1 the inequality being proved takes the form
and obviously right. Let's assume it's true forn=k , that is, what
.

Since according to the condition
, then
, and therefore the inequality does not change its meaning when both its parts are multiplied by
:

Because
, then we get that

.

So the inequality is true for n=1, and from its truth at n=k it follows that it is true and n=k+1. Hence, by mathematical induction, it holds for all natural P.

For example,

Example number 33. Find all natural valuesP , for which the inequality

Solution.

At n=1 the inequality is right. At n=2 inequality is also true.

At n=3 the inequality is no longer satisfied. Only when n=6 the inequality holds, so that for the induction basis we can take n=6.

Assume that the inequality is true for some natural to:

Consider the inequality

The last inequality holds if
Test on the topic n=1 is given recurrently: n≥5 , where P- -natural number.

Savelyeva Ekaterina

The paper considers the application of the method of mathematical induction in solving divisibility problems, to the summation of series. Examples of the application of the method of mathematical induction to the proof of inequalities and to the solution of geometric problems are considered. The work is illustrated with a presentation.

Download:

Preview:

Ministry of Science and Education of the Russian Federation

State educational institution

average comprehensive school № 618

Course: Algebra and Beginnings of Analysis

Project work topic

"Method of mathematical induction and its application to problem solving"

Work completed: Savelyeva E, 11B class

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

1. Introduction.

2.Method of mathematical induction in solving divisibility problems.

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

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

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

6. List of used literature.

Introduction

Deductive and inductive methods are the basis of any mathematical research. The deductive method of reasoning is reasoning from the general to the particular, i.e. reasoning, the starting point of which is the general result, and the final point is the particular result. Induction is applied when passing from particular results to general ones, i.e. is the opposite of the deductive method. The method of mathematical induction can be compared with progress. We start from the lowest, as a result logical thinking we come to the highest. Man has always striven for progress, for the ability to develop his thought logically, which means that nature itself has destined him to think inductively. Although the field of application of the method of mathematical induction has grown, in school curriculum he is given little time. But it is so important to be able to think inductively. The application of this principle in solving problems and proving theorems is on a par with the consideration in school practice of other mathematical principles: the excluded middle, inclusion-exclusion, Dirichlet, etc. This essay contains problems from different branches of mathematics, in which the main tool is the use method of mathematical induction. Speaking about the importance of this method, A.N. Kolmogorov noted that "the understanding and ability to apply the principle of mathematical induction is a good criterion for maturity, which is absolutely necessary for a mathematician." The method of induction in its broadest sense consists in the transition from private observations to a universal, general pattern or general formulation. In this interpretation, the method is, of course, the main technique for conducting research in any experimental natural science.

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

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

1 =1 2 ,

1 + 3 = 2 2 ,

1 + 3 + 5 \u003d W 2,

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

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

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

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

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

To prove this conjecture, it suffices to establish two facts. First, for n = 1 (and even for n = 2, 3, 4) the desired statement is true. Second, suppose that the statement is true for n = k, and verify that then it is also true for n = k + 1:

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

Hence, the assertion being proved is true for all values n: for n = 1 it is true (this has been verified), and by virtue of the second fact, for n = 2, whence for n = 3 (due to the same second fact), etc.

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

denominator: Prove that for any n> 3 can be represented as a sum P various fractions of this kind.

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

Therefore, the basic assertion is satisfied

Suppose now that the statement of interest to us is true for some number to, and prove that it is also true for the number following it to + 1. In other words, suppose there is a representation

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

And therefore

In addition, all fractions remain different, since t was the biggest denominator, and t + 1 > t, and

m(t + 1) > m.

Thus, we have established:

1. for n = 3 this statement is true;

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

On this basis, we can assert that the statement under consideration is true for all natural numbers, starting from three. Moreover, the above proof also implies an algorithm for finding the desired partition of unity. (What algorithm is this? Imagine the number 1 as the sum of 4, 5, 7 terms yourself.)

In solving the previous two problems, two steps were taken. The first step is called basis induction, the secondinductive transitionor an induction step. The second step is the most important, and it involves an assumption (the statement is true for n = k) and conclusion (the statement is true for n = k + 1). The parameter p itself is called induction parameter.This logical scheme (device), which makes it possible to conclude that the statement under consideration is true for all natural numbers (or for all, starting from some), since both the basis and the transition are valid, is calledthe principle of mathematical induction, on which and the method of mathematical induction is based.The term "induction" itself comes from the Latin word inductio (guidance), which means the transition from a single knowledge of individual items of this class to a general conclusion about all objects of this class, which is one of the main methods of cognition.

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

“Despite the fact that the proposition under consideration [an explicit formula for binomial coefficients] contains an infinite number of special cases, I will give a very short proof for it, based on two lemmas.

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

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

These two lemmas necessarily imply the validity of the proposition for all values P. Indeed, by virtue of the first lemma, it is valid for P = 1; therefore, by virtue of the second lemma, it is valid for P = 2; therefore, again by virtue of the second lemma, it is valid for n = 3 and so on ad infinitum.

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

Fig 1

This pyramid must be transferred to one of the other rods, transferring only one ring each time and not placing the larger ring on the smaller one. Can it be done?

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

1. base of induction. For n = 1, everything is clear, since a pyramid of one ring can obviously be moved to any rod.
2. step of induction. Suppose that we can move any pyramids with the number of rings p = k.
   Let us prove that then we can also move the pyramid mid from n = k + 1.

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

The method of mathematical induction in solving divisibility problems.

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

Task 4 . 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, so is it. So, parity is proved for n=1, parity is deduced from parity. Hence, even for all natural values ​​of n.

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

Solution. Let us first prove by induction an auxiliary assertion that 3 3n+3 1 is divisible by 26 with no remainder n > 0.

1. base of induction. For n = 0 we have: Z 3 - 1 \u003d 26 - divided by 26.

step of induction. Suppose 3 3n + 3 - 1 is divisible by 26 when n = k, and Let us prove that in this case the assertion will be true for n = k + 1. Since 3

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

Let us now prove the assertion formulated in the condition of the problem. And again by induction.

1. base of induction. It is obvious that at n = 1 statement is true: since 3 3+3 - 26 - 27 = 676 = 26 2 .
2. step of induction. Let's assume that at n = k
   expression 3 3k + 3 - 26k - 27 is divisible by 26 2 without remainder, and prove that the assertion is true for n = k + 1,
   i.e. that number

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

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

Task 5. Prove 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.

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

Solution. Do all 100 operations would be very time consuming and time consuming. So, we need to try to find some general formula for the sum S numbers after n operations. Let's look at the table:

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

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

whose sum S 4 is 82.

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

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

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

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

Let us now try to prove this by induction.

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

step of induction. Let's pretend that

Let us prove then that S to + 1 \u003d Z to + 1 + 1.

Really,

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

Consider one remarkable example of the application of the principle of mathematical induction, in which you first need to introduce two natural parameters and then carry out induction on their sum.

A task 7. Prove that if= 2, x 2 = 3 and for every natural n> 3

x n \u003d Zx n - 1 - 2x n - 2,

then

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

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

base of induction. It consists of checking two assertions: n=1 and n=2.B In both cases, the assertion is true by assumption.

step of induction. Let's assume that for n = k - 1 and n = k assertion is made, that is

Let us then prove the assertion for n = k + 1. We have:

x 1 = 3(2 + 1) - 2(2 + 1) = 2 + 1, which was to be proved.

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

for k > 2.

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

base of induction. For n = 1 statement is true, since the unit is itself a Fibonacci number.

step of induction. Assume that all natural numbers less than some number P, can be represented as the sum of several different terms of the Fibonacci sequence. Find the largest Fibonacci number F t , not exceeding P; so F t n and F t +1 > n.

Because the

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

Examples of application of the method of mathematical induction to the proof of inequalities.

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

(1 + x) n > 1 + xn.

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

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

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

2. Step of induction. Let's assume that for the number n = k the statement is true, that is

(1 + x) k > 1 + xk,

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

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

So, based on the principle of mathematical induction, it can be argued that Bernoulli's inequality is valid for any n > 2.

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

Problem 10. Prove that

for any natural n > 1.

Solution, Let's try to prove this inequality by mathematical induction.

The induction basis is easily verified:1+

By the inductive hypothesis

and it remains for us to prove that

Using the inductive hypothesis, we will assert that

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

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

It may seem that proving this assertion by induction is hopeless.

However, at p = 1 we have: the statement is true. To justify the inductive step, suppose that

and then we will prove that

Really,

Thus, we have proved a stronger assertion, from which the assertion contained in the condition of the problem immediately follows.

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

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

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

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

We will carry out inductive reasoning on P.

1. Base of induction according to p. For n = 1 need to check that 2 t ~ 1 > t. To prove this inequality, we use induction on t.

a) Base of induction by vol. For t = 1 in progress
equality, which is acceptable.

b) Step of induction according to t.Let's assume that at t = k statement is true, that is 2 k ~ 1 > k. Then up
Let us say that the assertion is true even if m = k + 1.
We have:

at natural k.

Thus, the inequality 2 performed for any natural t.

2. Step of induction according to itemChoose and fix some natural number t. Let's assume that at n = I the statement is true (for a fixed t), i.e. 2 t +1 ~ 2 > t1, and prove that then the assertion will be true for n = l + 1.
We have:

for any natural type of.

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

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

In every expression to signs square root, t and n alternate.

Solution. Let us first prove some auxiliary assertion.

Lemma. For any natural t and n (t > n) and non-negative (not necessarily integer) X the inequality

Proof. Consider the inequality

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

Taking the square root of both parts of the last inequality, we obtain the assertion of the lemma. So the lemma is proved.

Now let's move on to solving the problem. Let's denote the first of these numbers by a, and the second through b to . Let's prove that a for any natural to. The proof will be carried out by the method of mathematical induction separately for even and odd to.

base of induction. For k = 1 we have the inequality

y[t > y/n , which is valid due to the fact that m > n. = 2, the desired result is obtained from the proved lemma by substituting x = 0.

step of induction. Suppose, for some to the inequality a >b to fair. Let's prove that

From the assumption of induction and the monotonicity of the square root, we have:

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

Combining the last two inequalities, we get:

According to the principle of mathematical induction, the assertion is proved.

Task 13. (Cauchy's inequality.)Prove that for any positive numbers..., a p the inequality

Solution. For n = 2 the inequality

the arithmetic mean and the geometric mean (for two numbers) will be considered known. Let n= 2, k = 1, 2, 3, ... and first carry out induction on to. The basis of this induction holds. Assuming now that the desired inequality has already been established for n = 2 , we will prove it for P = 2 . We have (using the inequality for two numbers):

Therefore, by the induction hypothesis

Thus, by induction on k, we have proved the inequality for all p 9 which are powers of two.

To prove the inequality for other values P we will use the "induction down", that is, we will prove that if the inequality is satisfied for arbitrary non-negative P numbers, it is also valid for(P - 1)th number. To verify this, we note that, according to the assumption made, for P numbers, the inequality

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

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

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

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

Let us use the method of mathematical induction and draw it over the sum n = p + q natural coprime numbers..

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

step of induction. Suppose now that the desired inequalities are established for p + q = 2, 3, ..., k - 1, where k > 2. Let us prove that the inequalities are also valid for p + q = k.

Let ABC is a given triangle with> 2. Then the sides AC and BC cannot be equal: let AC > BC. Now let's build, as in Figure 2, an isosceles triangle ABC; we have:

AC \u003d DC and AD \u003d AB + BD, therefore,

2AC > AB + BD (1)

Consider now the triangle VDC, whose angles are also comparable:

DCB = (q - p), BDC = p.

Rice. 2

This triangle satisfies the inductive hypothesis, and therefore

(2)

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

2AC+BD>

and therefore

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

Considering the previous inequality, we conclude that

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

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

Problem 15. Several straight lines divide the plane into parts. Prove that it is possible to color these parts white

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

pic 3

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

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

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

Rice. four

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

Fig.5

Let us now prove the inductive step. Suppose that for somen = kthe statement of the problem is valid, that is, all parts of the plane into which it is divided by thesetostraight, you can paint in white and black so that the neighboring parts are of different colors. Let us prove that then there exists such a coloring forP= to+ 1 straight. Let us proceed similarly to the case of transition from two straight lines to three. Let's spend on the planetodirect. Then, by the inductive assumption, the resulting "map" can be colored in the desired way. Let's spend now(to+ 1)-th straight line and on one side of it we change the colors to the opposite ones. So now(toThe + 1)-th straight line everywhere separates sections of different colors, while the "old" parts, as we have already seen, remain correctly colored. According to the principle of mathematical induction, the problem is solved.

A task16. On the edge of the desert there is a large supply of gasoline and a car that, with a full gas station, can travel 50 kilometers. In unlimited quantities, there are canisters into which you can drain gasoline from the gas tank of the car and leave it for storage anywhere in the desert. Prove that the car can travel any integer distance greater than 50 kilometers. It is not allowed to carry cans of gasoline, empty cans can be carried in any quantity.

Solution.Let's try to prove it by induction onP,that the car can drivePkilometers from the edge of the desert. AtP= 50 is known. It remains to carry out the step of induction and explain how to get theren = k+ 1 km if knownn = kkilometers can be driven.

However, here we encounter a difficulty: after we have passedtokilometers, gasoline may not even be enough for the return trip (not to mention storage). And in this case, the way out is to strengthen the assertion being proved (the inventor's paradox). We will prove that it is possible not only to drivePkilometers, but also to make an arbitrarily large supply of gasoline at a point at a distancePkilometers from the edge of the desert, being at this point after the end of transportation.

base of induction.Let a unit of gasoline be the amount of gasoline required to complete one kilometer of travel. Then a 1 kilometer trip and back requires two units of gasoline, so we can leave 48 units of gasoline in storage a kilometer from the edge and return for more. Thus, for several trips to the storage, we can make a stock of an arbitrary size that we need. At the same time, in order to create 48 units of stock, we spend 50 units of gasoline.

step of induction.Let's assume that at a distanceP= tofrom the edge of the desert you can store any amount of gasoline. Let us prove that then it is possible to create a repository at a distancen = k+ 1 km with any predetermined supply of gasoline and be at this storage at the end of the transportation. Because at the pointP= tothere is an unlimited supply of gasoline, then (according to the induction base) we can, in several trips to the pointn = k+ 1 to make a pointP= to4- 1 stock of any size you need.

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

Conclusion

In particular, having studied the method of mathematical induction, I improved my knowledge in this area of ​​mathematics, and also learned how to solve problems that were previously beyond my power.

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

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

Literature

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

1976.-48 p.

2. Golovina L.I., Yaglom I.M. Induction in geometry. - M.: Gosud. publisher lit. - 1956 - S.I00. A manual on mathematics for applicants to universities / Ed. Yakovleva G.N. The science. -1981. - P.47-51.

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

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

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

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

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

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

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

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

63s.

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

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

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

Lesson #50

Lesson topic : Method of mathematical induction.

The purpose of the lesson: Meet tothe essence of the method of mathematical induction, learn how to apply this method in solving problems of proof, continue the development of computational skills, continue the formation of mathematical literacy.

During the classes.

Organizing time. Setting lesson goals

Activation of basic knowledge.

Definition of a geometric progression, formulas for the n-th member of a geometric progression.

Repeat the formula for the sum of the first n terms of an arithmetic progression.

Repeat the formula for the sum of an infinitely decreasing geometric progression

3. Learning new material

When solving many problems, when proving the validity of mathematical sentences, as well as when deriving a formula, reasoning is often used, which is calledmethod of mathematical induction.

You, for example, used such reasoning when deriving the formulanth term, as well as when deriving the formula for the sum of the firstnmembers of arithmetic and geometric progressions.

The essence of this method is as follows: if it is necessary to establish the validity of a certain statement in which a natural number appearsn, then:

1) it is checked that the intended statement holds for a particular valuen(for example forn=1).

2) it is assumed that the statement is true for some arbitrary valuen = k , and it is proved that in this case it is also valid forn = k + 1. From here it is concluded that the assertion is true for any valuen, for its justice was discovered atn=1, and by what has been proved, it is also true forn= 2, and since it is valid forn= 2, then it is also valid forn= 3 etc.

Now let's look at examples of using this method.

Example 1. Let us prove that for any naturalnthere is an equality

The formula is correct forn= 1 because:

Let us assume that the formula is true forn = k .

Let us prove that in this case it is true forn = k+ 1, i.e.

Direct verification showed that the formula is true forn =1; therefore, it will also be valid forn= 2, and therefore forn= 3, therefore, forn = 4 and in general for any naturaln.

4. Problem solving

№249(a)

In this problem, it is required to prove the formulan – thterm of an arithmetic progression by mathematical induction

Atn=1 we have a 1 =a 1.

Assume that this formula is true forkth term, i.e., the equality a k = a 1 + d( k-1)

Let us prove that in this case this formula is also true for (k+1)th member. Really,

a k +1 = a 1 + d( k+1-1) = a 1 + dk

On the other hand, by definition, arif. prog. a k +1 = a k + d

Since the left parts of the last two expressions are = and the right parts are equal:

a k + d= a 1 + dkor a k = a 1 + d( k-1)

The resulting correct equality allows us to assert that the formulanth term of an arithmetic progression is suitable for any naturaln

№ 255

Let's prove that the number 11 n+1 +12 2 n -1 for all natural valuesndivide by 133

Atn=1 we have 11 1+1 +12 2*1-1 =133, 133 divided by 133

Let's assume that atn= ksum 11 k +1 +12 2 k -1 divide by 133

Let us prove that this sum is divisible by 133 forn= k+1, i.e. eleven k +2 +12 2 k +1 divide by 133

11 k+2 +12 2k+1 =11*11 k +1 +144*12 k-1 =11*11 k +1 +11*12 2k-1 +133*12 2k-1 =11(11 k+1 +12 2k-1 )+133*12 2k-1

Each term of the resulting sum is divisible by 133. Therefore, 11 k +2 +12 2 k +1 also divide by 133.

5. Reflection

6. Statement D / z

§15 decide no.251

Introduction

Main part

1. Complete and incomplete induction

2. The principle of mathematical induction

3. Method of mathematical induction

4. Solution of examples

5. Equalities

6. Division of numbers

7. Inequalities

Conclusion

List of used literature

Introduction

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

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

Although the field of application of the method of mathematical induction has grown, little time is devoted to it in the school curriculum. Well, say that a useful person will be brought by those two or three lessons for which he hears five words of theory, solves five primitive problems, and, as a result, gets a five for knowing nothing.

But this is so important - to be able to think inductively.

Main part

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

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

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

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

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

So the complete induction is that general statement is proved separately in each of a finite number of possible cases.

Sometimes the overall result can be predicted after considering not all, but enough a large number special cases (the so-called incomplete induction).

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

Let, for example, it is required to find the sum of the first n consecutive odd numbers. Consider special cases:

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

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

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

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

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

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

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

Let it be necessary to prove the validity of a certain statement for any natural number n (for example, it is necessary to prove that the sum of the first n odd numbers is equal to n 2). A direct verification of this statement for each value of n is impossible, since the set of natural numbers is infinite. To prove this statement, first check its validity for n=1. Then it is proved that for any natural value of k, the validity of the statement under consideration for n=k implies its validity for n=k+1 as well.

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

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

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

The principle of mathematical induction.

If sentence A( n ) depending on the natural number n , true for n =1 and from the fact that it is true for n=k (where k -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 sentence A( n ) is true for n=p and if A( k ) Þ BUT( k+1) for anyone k>p, then sentence A( n) true for anyone 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 (the inductive assumption), i.e. prove that A(k)ÞA(k+1).

EXAMPLE 1

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

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

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 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 Assumption A(n) is true for any nОN.

EXAMPLE 2

Prove that

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

Solution: 1) For n=1 we get

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

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

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

1 + x + x 2 + x 3 + ... + x k \u003d (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.

EXAMPLE 3

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

And 3 is correct, because in a triangle

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

A 2 A(3) is true.

2) Suppose that in any

convex k-gon has-

A 1 sya A k \u003d k (k-3) / 2 diagonals.

A k Let us prove that then in a convex

(k+1)-gon number

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

Let А 1 А 2 А 3 …A k A k+1 -convex (k+1)-angle. Let's draw a diagonal A 1 A k in it. To count total number diagonals of this (k + 1)-gon, you need to count the number of diagonals in the k-gon A 1 A 2 ...A k , add 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.

In this way,

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

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

EXAMPLE 4

Prove that for any n the 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.

Hence, for n=1 the statement is true.

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.

EXAMPLE 5

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