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 close 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 like logic, philosophy describes them as opposites.

From the point of view of the law of logic, inductive definitions are based on facts, 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 of random positions. This fact important due to the nature 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 inconsistency of the theories of Bacon and Mill led scientists to investigate the probabilistic basis of 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.

The induction receives a vote of confidence when practical application in certain subject areas and thanks to the metric accuracy of the inductive base. An example of induction and deduction in philosophy can be considered the law of universal gravitation. 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 overall score 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 justified 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. In the home environment, there are many opportunities for comfortable living. You can refuse all red items or replace them with analogues made in a different color scheme. But in in public places, at work, in the store - it's 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 way to get rid of obsessive states can become an elementary development of deductive thinking. 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 as the new kind induction either suggestion, or some forms of mental illness, or extreme states of the human psyche. From all of the above, it is clear that an attempt to deduce " new term”, relying 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.

AT mass consciousness the method of deduction 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.

Mathematical induction underlies one of the most common methods of mathematical proofs. It can be used to prove most formulas with natural numbers n, for example, the formula for finding the sum of the first terms of the progression S n \u003d 2 a 1 + n - 1 d 2 n, Newton's binomial formula a + b n \u003d C n 0 a n C n 1 a n - 1 b + . . . + C n n - 1 a b n - 1 + C n n b n .

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

Concepts of induction and deduction

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

Definition 1

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

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

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

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

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

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

What is the method of mathematical induction

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

Definition 2

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

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

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

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

Let's take the example we talked about earlier.

Example 1

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

Solution

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

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

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

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

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

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

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

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

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

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

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

Example 2

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

Solution

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

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

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

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

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

According to the trigonometric formula,

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

Consequently,

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

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

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

MBOU Lyceum "Technical and Economic"

METHOD OF MATHEMATICAL INDUCTION

METHOD OF MATHEMATICAL INDUCTION.

EXPLANATORY NOTE

The methodological development "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.

AT 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 contributes to the identification of connections between various 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 highly efficient method search for new results and proof of the truth of the proposed assumptions. 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-valued 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 the following expressions as a sum:

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.

Parsing a finite number of cases plays important role in mathematics: without giving a proof of this or that statement, it helps to guess the correct formulation of this statement, if it is still unknown. 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 at most three prime numbers.

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.

Ministry of Education of the Saratov Region

Saratov State Socio-Economic University

Regional competition of mathematical and computer work schoolchildren

"Vector of the Future - 2007"

«Method of mathematical induction.

Its application to solving algebraic problems"

(section "mathematics")

creative work

10"A" class students

MOU "Gymnasium No. 1"

Oktyabrsky district of Saratov

Harutyunyan Gayane.

Work manager:

mathematic teacher

Grishina Irina Vladimirovna

Saratov

2007

Introduction…………………………………………………………………………………3

The principle of mathematical induction and its

proof…………………………………………………………………………..4

Examples of problem solving…………………………………………………………………..9

Conclusion……………………………………………………………………………..16

Literature…………………………………………………………………………………17

Introduction.

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 strived for progress, for the ability to develop his thought logically, which means that nature itself has destined him to think inductively and reinforce his thought with evidence carried out according to all the rules of logic.
At present, the field of application of the method of mathematical induction has grown, but in school curriculum Unfortunately, he doesn't have much time. But this is so important - to be able to think inductively.

The principle of mathematical induction and its proof

Let us turn to the essence of the method of mathematical induction. Let's consider various statements. They can be subdivided into general and particular ones. Let us give examples of general statements.

All Russian citizens have the right to education.

In any parallelogram, the diagonals at the point of intersection are bisected.

All numbers ending in zero are divisible by 5.

Relevant examples of private statements:

Petrov has the right to education.

In parallelogram ABCD, the diagonals at the point of intersection are bisected.

140 is divisible by 5.

The transition from general statements to particular ones is called deduction (from the Latin deductio - conclusion according to the rules of logic).

Consider an example of deductive inference.

All Russian citizens have the right to education. (one)

Petrov is a citizen of Russia. (2)

Petrov has the right to education. (3)

From the general assertion (1) with the help of (2) the particular assertion (3) is obtained.

The reverse transition from particular statements to general statements is called induction (from the Latin induction - guidance).

Induction can lead to both correct and incorrect conclusions.

Let's explain this with two examples.

140 is divisible by 5. (1)

All numbers ending in zero are divisible by 5. (2)

140 is divisible by 5. (1)

All three-digit numbers are divisible by 5. (2)

From the particular statement (1) the general statement (2) is obtained. Statement (2) is true.

The second example shows how a general statement (3) can be obtained from a particular statement (1) , moreover, statement (3) is not true.

Let us ask ourselves the question of how to use induction in mathematics in order to obtain only correct conclusions. Let's consider some examples of induction, which is unacceptable in mathematics.

Example 1.

Consider a square trinomial of the following form Р(x)= x 2 + x + 41, which Leonard Euler paid attention to.

P(0) = 41, P(1) = 43, P(2) = 47, P(3) = 53, P(4) = 61, P(5) = 71, P(6) = 83, P (7) = 97, P(8) = 113, P(9)=131, P(10) = 151.

We see that every time the value of the trinomial is a prime number. Based on the results obtained, we assert that when substituting into the trinomial under consideration, instead of x Any non-negative integer always results in a prime number.

However, the conclusion drawn cannot be considered reliable. What's the matter? The fact is that in the reasoning, general statements are made about any x only on the basis that this statement turned out to be true for some values ​​of x.

Indeed, upon closer examination of the trinomial P(x), the numbers P(0), P(1), ..., P(39) are prime numbers, but P(40) = 41 2 is a composite number. And quite clearly: P(41) = 41 2 +41+41 is a multiple of 41.

In this example, we met with a statement that is true in 40 special cases and yet turned out to be unfair in general.

Let's look at a few more examples.

Example 2

In the 17th century V.G. Leibniz proved that for any natural n, numbers of the form n 3 - n are multiples of 3, n 5 - n are multiples of 5, n 7 - n are multiples of 7. Based on this, he suggested that for any odd k and natural n, the number n k - n multiple of k, but soon he himself noticed that 2 9 -2=510, which, obviously, is not divisible by 9.

The considered examples allow us to draw an important conclusion: a statement can be true in a number of special cases and at the same time unjust in general.

The question naturally arises: there is a statement that is true in several special cases; it is impossible to consider all special cases; how do you know if this statement is true at all?

This question can sometimes be solved by applying a special method of reasoning called the method of mathematical induction. This method is based on principle of mathematical induction, concluded in the following: the statement is true for any natural n if:

it is valid for n = 1;

from the validity of the statement for some arbitrary natural n =k , it follows that it is true for n = k +1.

Proof.

Assume the opposite, that is, let the statement be true not for every natural n. Then there is a natural number m such that

the statement for n =m is not true,

for all n

It is obvious that m >1, since the assertion is true for n =1 (condition 1). Therefore, m -1 is a natural number. For a natural number m -1 the statement is true, but for the next natural number m it is not true. This contradicts condition 2. The resulting contradiction shows that the assumption is wrong. Therefore, the assertion is true for any natural n, h.e.d.

A proof based on the principle of mathematical induction is called a proof by the method of mathematical induction. Such a proof should consist of two parts, from the proof of two independent theorems.

Theorem 1. The statement is true for n =1.

Theorem 2. The statement is true for n =k +1 if it is true for n=k, where k is an arbitrary natural number.

If both these theorems are proved, then, based on the principle of mathematical induction, the statement is true for any
natural n .

It must be emphasized that the proof by mathematical induction certainly requires the proof of both Theorems 1 and 2. Neglect of Theorem 2 leads to incorrect conclusions (examples 1-2). Let us show by an example how necessary the proof of Theorem 1 is.

Example 3. "Theorem": every natural number is equal to the natural number following it.

The proof will be carried out by the method of mathematical induction.

Suppose that k =k +1 (1).

Let us prove that k +1=k +2 (2). To do this, add 1 to each part of "equality" (1). We get "equality" (2). It turns out that if the statement is true for n =k , then it is also true for n =k +1., etc.

An obvious "consequence" from the "theorem": all natural numbers are equal.

The error lies in the fact that Theorem 1, which is necessary for applying the principle of mathematical induction, has not been proved and is not true, but only the second theorem has been proved.

Theorems 1 and 2 are of particular importance.

Theorem 1 creates the basis for induction. Theorem 2 gives the right to unlimited automatic expansion of this base, the right to move from this particular case to the next, from n to n + 1.

If Theorem 1 has not been proven, but Theorem 2 has been proved, then, therefore, the basis for induction has not been created, and then it makes no sense to apply Theorem 2, since there is, in fact, nothing to expand.

If Theorem 2 has not been proved, and only Theorem 1 has been proved, then, although the base for conducting the induction has been created, the right to expand this base is absent.

Remarks.

Sometimes the second part of the proof is based on the validity of the statement not only for n =k, but also for n =k -1. In this case, the statement in the first part must be tested for the next two values ​​of n .

Sometimes the statement is proved not for any natural n , but for n > m , where m is some integer. In this case, in the first part of the proof, the assertion is verified for n =m +1, and if necessary, for several subsequent values ​​of n.

Summing up what has been said, we have: the method of mathematical induction allows, in search of a general law, to test the hypotheses that arise in this case, discard the false ones and assert the true ones.

Everyone knows the role of the processes of generalizing the results of individual observations and experiments (ie, induction) for the empirical, experimental sciences. Mathematics, on the other hand, has long been considered a classic example of the implementation of purely deductive methods, since it is always explicitly or implicitly assumed that all mathematical propositions (except those accepted as initial ones - axioms) are proved, and specific applications of these propositions are derived from proofs suitable for general cases (deduction).

What does induction mean in mathematics? Should it be understood as a not quite reliable method, and how to look for a criterion for the reliability of such inductive methods? Or the certainty of mathematical conclusions of the same nature as experimental generalizations of the experimental sciences, such that it would not be bad to “verify” any proven fact? In reality, this is not the case.

Induction (guidance) on a hypothesis plays a very important but purely heuristic role in mathematics: it allows one to guess what the solution should be. But mathematical propositions are established only deductively. And the method of mathematical induction is a purely deductive method of proof. Indeed, the proof carried out by this method consists of two parts:

the so-called "basis" - a deductive proof of the desired sentence for one (or several) natural numbers;

an inductive step consisting in a deductive proof of a general statement. The theorem is precisely proved for all natural numbers. From the basis proved, for example, for the number 0, we get, by the induction step, the proof for the number 1, then in the same way for 2, for 3 ... - and so the statement can be justified for any natural number.

In other words, the name "mathematical induction" is due to the fact that this method is simply associated in our minds with traditional inductive reasoning (after all, the basis is really proved only for a particular case); the inductive step, in contrast to the plausibility criteria of inductive reasoning based on experience in the natural and social sciences, is a general statement that does not need any particular premise and is proved according to the strict canons of deductive reasoning. Therefore, mathematical induction is called "complete" or "perfect", since it is a deductive, completely reliable method of proof.

Examples of problem solutions

Induction in algebra

Consider several examples of algebraic problems, as well as the proof of various inequalities that can be solved using the method of mathematical induction.

Task 1. Guess the formula for the sum and prove it.

BUT( n )= 2  1 2 + 3 2 2 + …..+(n +1) n 2 .

Solution.

1. Let's transform the expression for the sum А(n):

A(n)= 2  1 2 + 3  2 2 + ….+ (n+1) n 2 = (1+1) 1 2 + (2+1) 2 2 + …. + (n+1) n 2 = =1  1 2 + 2  2 2 + …+n  n 2 + 1 2 + 2 2 +… +n 2 =1 3 + 2 3 +… +n 3 +1 2 + 2 2 +… +n 2 = В(n) + C(n), where B(n) = 1 3 + 2 3 + …..+ n 3 , C(n)= 1 2 + 2 2 + …+ n 2 .

2. Consider the sums C (n) and B (n).

a) C( n ) = 1 2 + 2 2 +…+ n 2 . One of the frequently encountered problems on the method of mathematical induction is to prove that for any natural n , the equality

1 2 + 2 2 +…+ n 2 = (1)

Assume that (1) is true for all n  N.

b ) B(n) = 1 3 + 2 3 + …..+ n 3 . Let's observe how the values ​​of B (n) change depending on n.

B(1) = 1 3 = 1 .

B(2) = 1 3 + 2 3 = 9 = 3 2 = (1 + 2) 2

B(3) = 1 3 + 2 3 + 3 3 = 36 =

Thus, it can be assumed that
B (n) = (1 + 2 + ….+ n) 2 =
(2)

c) As a result, for the sum А(n) we get

BUT( n ) ==

= (*)

3. Let us prove the obtained formula (*) by the method of mathematical induction.

a) check the equality (*) for n = 1.

A(1) = 2  =2,

Obviously, the formula (*) is true for n = 1.

b) suppose that the formula (*) is true for n=k , where k N, that is, the equality

A(k)=

Based on the assumption, we will prove the validity of the formula for n =k +1. Really,

A(k+1)=

Since the formula (*) is true for n =1, and from the assumption that it is true for some natural k , it follows that it is true for n =k +1, based on the principle of mathematical induction we conclude that the equality

holds for any natural n .

Task 2.

Calculate the sum 1-2 + 3-4 +…(-1) n -1 n .

Solution.

Let us write down the values ​​of the sums for different values ​​of n in succession.

A(1)=1, A(2)=1-2= -1, A(3)=1-2+3=2, A(4)=1-2+3-4= -2,

A(5)=1-2+3-4+5=3, A(6)=1-2+3-4+5-6= -3.

Observing the pattern, we can assume that A (n)= - for even n and A (n)=
for odd n. Let's combine both results into a single formula:

A(n) =
, where r is the remainder of dividing n by 2.

And r , is obviously determined by the following rule

0 if n is even,

r=

1 if n is odd.

Then r(can be guessed) can be represented as:

Finally we get the formula for A (n):

A(n)=

(*)

Let us prove the equality (*) for all n  N method of mathematical induction.

2. a) Check the equality (*) for n =1. A(1) = 1=

Equality is fair

b) Suppose that the equality

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

true at n=k. Let us prove that it is also valid for n =k + 1, i.e.

A(k+1)=

Indeed,

A(k+1)=A(k)+(-1) k (k+1) =

=

Q.E.D.

The method of mathematical induction is also used to solve divisibility problems.

Task 3.

Prove that the number N (n)=n 3 + 5n is divisible by 6 for any natural n.

Proof.

At n =1 the number N (1)=6 and therefore the statement is true.

Let the number N (k )=k 3 +5k be divisible by 6 for some natural k. Let us prove that N (k +1)= (k +1) 3 + 5(k +1) is divisible by 6. Indeed, we have
N (k +1)= (k +1) 3 + 5(k +1)=(k 3 +5k )+3k (k +1)+6.

Because the k and k +1 are adjacent natural numbers, then one of them is necessarily even, so the expression 3k (k +1) is divisible by 6. Thus, we get that N (k +1) is also divisible by 6. Output number N (n)=n 3 + 5n is divisible by 6 for any natural n.

Consider the solution of a more complex divisibility problem, when the method of complete mathematical induction has to be applied several times.

Task 4.

Prove that for any natural n the number
is not even divisible by 2 n +3 .

Proof.

Imagine
in the form of a work
=

= (*)

By assumption, the first factor in (*) is not evenly divisible by the number 2 k +3 , that is, in the representation of a composite number
in the form of a product of prime numbers, the number 2 is repeated no more than (k + 2) times. So to prove that the number
is not divisible by 2 k +4 , we must prove that
is not divisible by 4.

To prove this assertion, we prove an auxiliary assertion: for any natural n, the number 3 2 n +1 is not divisible by 4. For n =1, the assertion is obvious, since 10 is not divisible by 4 without a remainder. Assuming that 3 2 k +1 is not divisible by 4, we prove that 3 2(k +1) +1 is not divisible either
by 4. Let's represent the last expression as a sum:

3 2(k+1) +1=3 2k+2 +1=3 2k * 9+1=(3 2k +1)+8 * 3 2k . The second term of the sum is divisible by 4, but the first is not divisible. Therefore, the whole sum is not divisible by 4 without a remainder. The auxiliary assertion is proved.

Now it's clear that
is not divisible by 4 because 2k is an even number.

Finally, we get that the number
is not evenly divisible by 2 n +3 for any natural n .

Consider now an example of applying induction to the proof of inequalities.

Task 5.

For which natural n does the inequality 2 n > 2n + 1 hold true?

Solution.

1. When n=1 2 1< 2*1+1,

at n=2 2 2< 2*2+1,

at n =3 2 3 > 2*3+1,

at n =4 2 4 > 2*4+1.

Apparently, the inequality is valid for any natural n  3. Let us prove this assertion.

2. When n =3 the validity of the inequality has already been shown. Now let the inequality be valid for n =k , where k is some natural number not less than 3, i.e.

2 k > 2k+1 (*)

Let us prove that then the inequality is also valid for n =k +1, that is, 2 k +1 >2(k +1)+1. Multiply (*) by 2, we get 2 k +1 >4k +2. Let's compare the expressions 2(k +1)+1 and 4k +2.

4k+2-(2(k+1)+1)=2k-1. Obviously, 2k -1>0 for any natural k . Then 4k +2>2(k +1)+1, i.e. 2k+1 >2(k+1)+1. The assertion has been proven.

Task 6.

Inequality for the arithmetic mean and geometric mean of n non-negative numbers (Cauchy's inequality)., we get =

If at least one of the numbers
is equal to zero, then the inequality (**) is also valid.

Conclusion.

When doing the work, I studied the essence of the method of mathematical induction and its proof. The paper presents problems in which an important role was played by incomplete induction, which leads to the right decision, and then the proof obtained by the method of mathematical induction is carried out.

Literature.

Boltyansky V.G., Sidorov Yu.V., Shaburin M.I. Lectures and problems in elementary mathematics; Science, 1974.

Vilenkin N.Ya. , Shvartsburd S.I. Mathematical analysis.-
M.: Education, 1973.

Galitsky M.L., Moshkovich M.M., Shvartsburd S.I. In-depth study of the course of algebra and mathematical analysis. - M .: Education, 1990.

Potapov M.K., Aleksandrov V.V., Pasichenko P.I. Algebra and analysis of elementary functions.- M.: Nauka, 1980.

Sominsky I.S., Golovina M.L., Yaglom I.M. On mathematical induction. - M.: Nauka, 1967.

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

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

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

The proof by the method of mathematical induction is carried out as follows. First, the assertion to be proved is checked for n=1, i.e., the truth of the statement A(1) is established. This part of the proof is called the induction basis. This is followed by a part of the proof called the induction step. In this part, the validity of the statement for n=k+1 is proved under the assumption that the statement is true for n=k (the inductive assumption), i.e. prove that A(k) ~ A(k+1)

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

• 1) We have n=1=1 2 . Therefore, the statement is true for n=1, i.e. A(1) true
• 2) Let us prove that A(k) ~ A(k+1)

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

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

Let us prove that then the assertion is also true for the next natural number n=k+1, i.e. what

• 1+3+5+…+(2k+1)=(k+1) 2 Indeed,
• 1+3+5+…+(2k-1)+(2k+1)=k 2 +2k+1=(k+1) 2

So, A(k) X A(k+1). Based on the principle of mathematical induction, we conclude that the assumption A(n) is true for any n О N

Prove that

1 + x + x 2 + x 3 + ... + x n \u003d (x n + 1 -1) / (x-1), where x No. 1

• 1) For n=1 we get
• 1+x=(x 2 -1)/(x-1)=(x-1)(x+1)/(x-1)=x+1

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

• 2) Let k be any natural number and let the formula be true for n=k,
• 1+x+x 2 +x 3 +…+x k =(x k+1 -1)/(x-1)

Let us prove that then the equality

• 1+x+x 2 +x 3 +…+x k +x k+1 =(x k+2 -1)/(x-1) Indeed
• 1+х+х 2 +x 3 +…+х k +x k+1 =(1+x+x 2 +x 3 +…+x k)+x k+1 =

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

So A(k) ⋅ A(k+1). Based on the principle of mathematical induction, we conclude that the formula is true for any natural number n

Prove that the number of diagonals of a convex n-gon is n(n-3)/2

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

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

2) Suppose that in any convex k-gon has A 1 sya A k \u003d k (k-3) / 2 diagonals. A k Let's prove that then in a convex A k+1 (k+1)-gon the number of diagonals A k+1 =(k+1)(k-2)/2.

Let А 1 А 2 А 3 …A k A k+1 -convex (k+1)-gon. Let's draw a diagonal A 1 A k in it. To 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, one should take into account the diagonal A 1 A k

In this way,

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

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

Prove that for any n the statement is true:

1 2 +2 2 +3 2 +…+n 2 =n(n+1)(2n+1)/6

Solution: 1) Let n=1, then

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

2) Assume that n=k

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

3) Consider this statement for n=k+1

Xk+1 =(k+1)(k+2)(2k+3)/6

X k+1 =1 2 +2 2 +3 2 +…+k 2 +(k+1) 2 =k(k+1)(2k+1)/6+ +(k+1) 2

=(k(k+1)(2k+1)+6(k+1) 2)/6=(k+1)(k(2k+1)+

6(k+1))/6=(k+1)(2k 2 +7k+6)/6=(k+1)(2(k+3/2)(k+

2))/6=(k+1)(k+2)(2k+3)/6

We have proved the validity of the equality for n=k+1, therefore, by virtue of the method of mathematical induction, the statement is true for any natural n

Prove that for any natural n the equality is true:

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

Solution: 1) Let n=1

Then X 1 =1 3 =1 2 (1+1) 2 /4=1. We see that for n=1 the statement is true.

2) Assume that the equality is true for n=k

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

3) Let us prove the truth of this statement for n=k+1, i.e.

X k+1 =(k+1) 2 (k+2) 2 /4. X k+1 =1 3 +2 3 +…+k 3 +(k+1) 3 =k 2 (k+1) 2 /4+(k+1) 3 =(k 2 (k++1) 2 +4(k+1) 3)/4=(k+1) 2 (k 2 +4k+4)/4=(k+1) 2 (k+2) 2 /4

It can be seen from the above proof that the statement is true for n=k+1, therefore, the equality is true for any natural n

Prove that

((2 3 +1)/(2 3 -1)) ґ ((3 3 +1)/(3 3 -1)) ґ … ґ ((n 3 +1)/(n 3 -1))= 3n(n+1)/2(n 2 +n+1), where n>2

Solution: 1) For n=2, the identity looks like:

• (2 3 +1)/(2 3 -1)=(3 ґ 2 ґ 3)/2(2 2 +2+1), i.e. it is true
• 2) Assume that the expression is true for n=k
• (2 3 +1) / (2 3 -1) ґ ... ґ (k 3 +1) / (k 3 -1) \u003d 3k (k + 1) / 2 (k 2 + k + 1)
• 3) We will prove the correctness of the expression for n=k+1
• (((2 3 +1)/(2 3 -1)) ґ … ґ ((k 3 +1)/(k 3 -1))) ґ (((k+1) 3 +

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

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

ґ ((k+1) 2 +(k+1)+1)

We have proved the validity of the equality for n=k+1, therefore, by virtue of the method of mathematical induction, the statement is true for any n>2

Prove that

1 3 -2 3 +3 3 -4 3 +…+(2n-1) 3 -(2n) 3 =-n 2 (4n+3) for any natural n

Solution: 1) Let n=1, then

• 1 3 -2 3 =-1 3 (4+3); -7=-7
• 2) Assume that n=k, then
• 1 3 -2 3 +3 3 -4 3 +…+(2k-1) 3 -(2k) 3 =-k 2 (4k+3)
• 3) We will prove the truth of this statement for n=k+1
• (1 3 -2 3 +…+(2k-1) 3 -(2k) 3)+(2k+1) 3 -(2k+2) 3 =-k 2 (4k+3)+

+(2k+1) 3 -(2k+2) 3 =-(k+1) 3 (4(k+1)+3)

The validity of the equality for n=k+1 is also proved, therefore the statement is true for any natural n.

Prove the validity of the identity

(1 2 /1 ґ 3)+(2 2 /3 ґ 5)+…+(n 2 /(2n-1) ґ (2n+1))=n(n+1)/2(2n+1) for any natural n

• 1) For n=1 the identity is true 1 2 /1 ґ 3=1(1+1)/2(2+1)
• 2) Assume that for n=k
• (1 2 /1 ґ 3)+…+(k 2 /(2k-1) ґ (2k+1))=k(k+1)/2(2k+1)
• 3) We prove that the identity is true for n=k+1
• (1 2 /1 ґ 3)+…+(k 2 /(2k-1)(2k+1))+(k+1) 2 /(2k+1)(2k+3)=(k(k+ 1)/2(2k+1))+((k+1) 2 /(2k+1)(2k+3))=((k+1)/(2k+1)) ґ ((k/2 )+((k+1)/(2k+3)))=(k+1)(k+2) ґ (2k+1)/2(2k+1)(2k+3)=(k+1 )(k+2)/2(2(k+1)+1)

It can be seen from the above proof that the assertion is true for any positive integer n.

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

Solution: 1) Let n=1, then

11 3 +12 3 =(11+12)(11 2 -132+12 2)=23 ґ 133

But (23 ґ 133) is divisible by 133 without a remainder, so for n=1 the statement is true; A(1) is true.

• 2) Assume that (11 k+2 +12 2k+1) is divisible by 133 without a remainder
• 3) Let us prove that in this case (11 k+3 +12 2k+3) is divisible by 133 without a remainder. Indeed
• 11 k+3 +12 2k+3 =11 ґ 11 k+2 +12 2 ґ 12 2k+1 =11 ґ 11 k+2 +

+(11+133) ґ 12 2k+1 =11(11 k+2 +12 2k+1)+133 ґ 12 2k+1

The resulting amount is divisible by 133 without a remainder, since its first term is divisible by 133 without a remainder by assumption, and in the second one of the factors is 133. So, A (k) Yu A (k + 1). By virtue of the method of mathematical induction, the assertion is proved

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

• 1) Let n=1, then X 1 \u003d 7 1 -1 \u003d 6 is divided by 6 without a remainder. So for n=1 the statement is true
• 2) Suppose that for n \u003d k 7 k -1 is divisible by 6 without a remainder
• 3) Let us prove that the statement is true for n=k+1

X k+1 \u003d 7 k + 1 -1 \u003d 7 ґ 7 k -7 + 6 \u003d 7 (7 k -1) + 6

The first term is divisible by 6, since 7 k -1 is divisible by 6 by assumption, and the second term is 6. So 7 n -1 is a multiple of 6 for any natural n. By virtue of the method of mathematical induction, the assertion is proved.

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

1) Let n=1, then

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

So for n=1 the statement is true

• 2) Suppose that for n=k X k =3 3k-1 +2 4k-3 is divisible by 11 without a remainder
• 3) We prove that the statement is true for n=k+1

X k+1 =3 3(k+1)-1 +2 4(k+1)-3 =3 3k+2 +2 4k+1 =3 3 3 3k-1 +2 4 2 4k-3 =

27 3 3k-1 +16 2 4k-3 =(16+11) 3 3k-1 +16 2 4k-3 =16 3 3k-1 +

11 3 3k-1 +16 2 4k-3 =16(3 3k-1 +2 4k-3)+11 3 3k-1

The first term is divisible by 11 without a remainder, since 3 3k-1 +2 4k-3 is divisible by 11 by assumption, the second is divisible by 11, because one of its factors is the number 11. Hence, the sum is also divisible by 11 without a remainder for any natural n. By virtue of the method of mathematical induction, the assertion is proved.

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

• 1) Let n=1, then 11 2 -1=120 is divisible by 6 without a remainder. So for n=1 the statement is true
• 2) Suppose that for n=k 1 2k -1 is divisible by 6 without a remainder
• 11 2(k+1) -1=121 ґ 11 2k -1=120 ґ 11 2k +(11 2k -1)

Both terms are divisible by 6 without a remainder: the first contains a multiple of 6 number 120, and the second is divisible by 6 without a remainder by assumption. So the sum is divisible by 6 without a remainder. By virtue of the method of mathematical induction, the assertion is proved.

Prove that 3 3n+3 -26n-27 for an arbitrary positive integer n is divisible by 26 2 (676) without a remainder

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

• 1. When n=0
• 3 3 -1=26 is divisible by 26
• 2. Suppose that for n=k
• 3 3k+3 -1 is divisible by 26
• 3. Let us prove that the statement is true for n=k+1
• 3 3k+6 -1=27 ґ 3 3k+3 -1=26 ґ 3 3k+3 +(3 3k+3 -1) - is divisible by 26

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

• 1) It is obvious that for n=1 the statement is true
• 3 3+3 -26-27=676
• 2) Suppose that for n=k the expression 3 3k+3 -26k-27 is divisible by 26 2 without a remainder
• 3) Let's prove that the statement is true for n=k+1
• 3 3k+6 -26(k+1)-27=26(3 3k+3 -1)+(3 3k+3 -26k-27)

Both terms are divisible by 26 2 ; the first is divisible by 26 2 because we have proved that the expression in the brackets is divisible by 26, and the second is divisible by the inductive hypothesis. By virtue of the method of mathematical induction, the assertion is proved

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

• 1) For n=2, the inequality is true, since
• (1+x) 2 =1+2x+x 2 >1+2x

So A(2) is true

• 2) Let us prove that A(k) ⋅ A(k+1) if k> 2. Assume that A(k) is true, i.e., that the inequality
• (1+х) k >1+k ґ x. (3)

Let us prove that then A(k+1) is also true, i.e., that the inequality

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

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

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

Consider the right side of the last inequality; we have

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

As a result, we get that (1+х) k+1 >1+(k+1) ґ x

So A(k) ⋅ A(k+1). Based on the principle of mathematical induction, it can be argued that Bernoulli's inequality is valid for any n> 2

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

Solution: 1) For m=1

• (1+a+a 2) 1 > 1+a+(2/2) ґ a 2 both parts are equal
• 2) Assume that for m=k
• (1+a+a 2) k >1+k ґ a+(k(k+1)/2) ґ a 2
• 3) Let us prove that for m=k+1 the non-equality is true
• (1+a+a 2) k+1 =(1+a+a 2)(1+a+a 2) k >(1+a+a 2)(1+k ґ a+

+(k(k+1)/2) ґ a 2)=1+(k+1) ґ a+((k(k+1)/2)+k+1) ґ a 2 +

+((k(k+1)/2)+k) ґ a 3 +(k(k+1)/2) ґ a 4 > 1+(k+1) ґ a+

+((k+1)(k+2)/2) ґ a 2

We have proved the validity of the inequality for m=k+1, therefore, due to the method of mathematical induction, the inequality is valid for any natural m

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

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

• 1. For n=7 we have 3 7 /2 7 =2187/128>14=2 ґ 7 the inequality is true
• 2. Suppose that for n=k (3/2) k >2k
• 3) Let us prove the validity of the inequality for n=k+1
• 3k+1 /2k+1 =(3k /2k) ґ (3/2)>2k ґ (3/2)=3k>2(k+1)

Since k>7, the last inequality is obvious.

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

Prove that for n>2 the inequality

1+(1/2 2)+(1/3 2)+…+(1/n 2)<1,7-(1/n)

• 1) For n=3 the inequality is true
• 1+(1/2 2)+(1/3 2)=245/180
• 2. Suppose that for n=k
• 1+(1/2 2)+(1/3 2)+…+(1/k 2)=1.7-(1/k)
• 3) Let us prove the validity of the inequality for n=k+1
• (1+(1/2 2)+…+(1/k 2))+(1/(k+1) 2)

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

S (1/(k+1) 2)+(1/k+1)<1/k Ы (k+2)/(k+1) 2 <1/k Ы

s k(k+2)<(k+1) 2 Ы k 2 +2k

The latter is obvious, and therefore

1+(1/2 2)+(1/3 2)+…+(1/(k+1) 2)<1,7-(1/k+1)

By virtue of the method of mathematical induction, the inequality is proved.