True knowledge at all times has been based on establishing a pattern and proving its truthfulness in certain circumstances. Over such a long period of existence of logical reasoning, formulations of rules were given, and Aristotle even compiled a list of “correct reasoning.” Historically, it has been customary to divide all inferences into two types - from the concrete to the multiple (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 conjunction and cannot be interchanged.
Induction in mathematics
The term “induction” has Latin roots and is literally translated as “guidance.” Upon closer study, one can highlight the structure of the word, namely the Latin prefix - in- (denotes a directed action inward or being inside) and -duction - introduction. It is worth noting that there are two types - complete and incomplete induction. Full form characterize conclusions drawn from the study of all objects of a certain class.
Incomplete - conclusions that apply to all subjects of the class, but are made based on the study of only some units.
Complete mathematical induction is an inference based on a general conclusion about the entire class of any objects, functionally connected by relationship natural series of numbers based on knowledge of this functional connection. In this case, the proof process takes place in three stages:
- the first one proves the correctness of the position of mathematical induction. 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 is an inductive hypothesis;
- at the third stage, the validity of the position for the number f=h+1 is proven, based on the correctness of the position of the previous point - this is an induction transition, or a step of mathematical induction. An example is the so-called if the first stone in a row falls (basis), then all the stones in the row fall (transition).
Both jokingly and seriously
For ease of understanding, examples of solutions using the method of mathematical induction are presented in the form of joke problems. This is the “Polite Queue” task:
- The rules of conduct prohibit a man from taking a turn in front of a woman (in such a situation, she is allowed to go ahead). Based on this statement, if the last one in line is a man, then everyone else is a man.
A striking example of the method of mathematical induction is the “Dimensionless flight” problem:
- It is required to prove that any number of people can fit on the minibus. It is true that one person can fit inside a vehicle without difficulty (basis). But no matter how full the minibus is, 1 passenger will always fit on it (induction step).
Familiar circles
Examples of solving problems and equations by mathematical induction are quite common. As an illustration of this approach, consider the following problem.
Condition: there are h circles on the plane. It is required to prove that, for any arrangement of figures, the map they form can be correctly colored with two colors.
Solution: when h=1 the truth of the statement is obvious, so the proof will be constructed for the number of circles h+1.
Let us accept the assumption that the statement is valid for any map, and there are h+1 circles on the plane. By removing from total number one of the circles, 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). The result is a map correctly colored in two colors, which is what needed to be proven.
Examples with natural numbers
The application of the method of mathematical induction is clearly shown below.
Examples of solutions:
Prove that for any h the following equality is correct:
1 2 +2 2 +3 2 +…+h 2 =h(h+1)(2h+1)/6.
1. Let h=1, which means:
R 1 =1 2 =1(1+1)(2+1)/6=1
It follows from this that for h=1 the statement is correct.
2. Assuming that h=d, the equation is obtained:
R 1 =d 2 =d(d+1)(2d+1)/6=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, therefore the statement is true for any natural number, as shown in the example solution by mathematical induction.
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 =7 1 -1=6 (i.e. divided by 6 without remainder)
Therefore, for h=1 the statement is true;
2. Let h=d and 7 d -1 be divided 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 according to the assumption of the first point, 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.
Errors in judgment
Often incorrect reasoning is used in proofs due to the inaccuracy of the logical constructions used. This mainly happens when the structure and logic of the proof is violated. An example of incorrect reasoning is the following illustration.
Task
Condition: proof is required 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 adding one more stone, the set will not be a heap. The conclusion suggests itself that the assumption is valid for all natural h.
The mistake is that there is no definition of how many stones form a pile. Such an omission is called a 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.” Scientific disciplines such as logic and philosophy describe them in the form of opposites.
From the point of view of the law of logic, inductive definitions rely on facts, and the truthfulness 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, naturally, must be verified and confirmed by additional research. An example of induction in logic would be the following statement:
There is a drought in Estonia, a drought in Latvia, a drought in Lithuania.
Estonia, Latvia and Lithuania are Baltic states. There is drought in all the 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 languishes on the margins of deduction: a huge number of provisions and scientific laws are substantiated using the induction method. An example is the same mathematics, biology and other sciences. This is mostly due to the method of complete induction, but in some cases partial induction is also applicable.
The venerable age of induction has allowed it to penetrate almost all spheres of human activity - this is science, economics, and everyday conclusions.
Induction in the scientific community
The induction method requires a scrupulous attitude, since too much depends on the number of studied parts of the whole: what larger number studied, the more reliable the result. Based on this feature, scientific laws, obtained by induction, are tested for a long time at the level of probabilistic assumptions to isolate and study all possible structural elements, connections and impacts.
In science, an inductive conclusion is based on significant features, with the exception of random provisions. This fact is important due to the specifics scientific knowledge. This is clearly seen in the examples of induction in science.
There are two types of induction in scientific world(in connection with the method of study):
- induction-selection (or selection);
- induction - exclusion (elimination).
The first type is distinguished by the methodical (scrupulous) selection of samples of a class (subclasses) from its different areas.
An example of this type of induction is the following: silver (or silver salts) purifies water. The conclusion is based on many years of observations (a kind of selection of confirmations and refutations - selection).
The second type of induction is based on conclusions that establish causal relationships and exclude circumstances that do not correspond to its properties, namely universality, adherence to temporal sequence, necessity and unambiguity.
Induction and deduction from the position of philosophy
Looking back historically, 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 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 induction from the deductive method, as his contemporaries demanded.
Induction was further developed by J. Mill, who considered the inductive theory from the perspective of four main methods: agreement, difference, residues and corresponding changes. It is not surprising that today the listed methods, when examined in detail, are deductive.
The realization of the inconsistency of the theories of Bacon and Mill led scientists to study the probabilistic basis of induction. However, even here there were some extremes: attempts were made to reduce induction to the theory of probability with all the ensuing consequences.
The induction receives a vote of confidence when practical application in specific subject areas and due to the metric precision of the inductive framework. An example of induction and deduction in philosophy can be considered the Law universal gravity. On the date of discovery of the law, Newton was able to verify it with an accuracy of 4 percent. And when checked more than two hundred years later, the correctness was confirmed with an accuracy of 0.0001 percent, although the verification was carried out by the same inductive generalizations.
Modern philosophy pays more attention to deduction, which is dictated by the logical desire to derive new knowledge (or truths) from what is already known, without resorting to experience or intuition, but using “pure” reasoning. When referring to true premises in deductive method in all cases the output is a true statement.
This one is very important characteristic should not overshadow the value inductive method. Since induction, based on the achievements of experience, also becomes a means of processing it (including generalization and systematization).
Application of induction in economics
Induction and deduction have long been used as methods for studying the economy and forecasting its development.
The range of use of the induction method is quite wide: studying the fulfillment of forecast indicators (profits, 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 maps”, where, under the assumption of the division of processes into controlled and uncontrollable, 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 induction method, and since economics is a science that often uses mathematical analysis, risk theory and statistics, it is not at all surprising that induction is on the list of main methods.
An example of induction and deduction in economics is the following situation. 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, due to the fact of high cost, using mathematical methods You can 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 with sufficient truthfulness the development of an enterprise, market behavior, and the consequences of competition, an inductive-deductive approach to the analysis and processing of information is necessary.
A clear example of induction in economics related to erroneous judgments:
- the company's profit decreased by 30%;
a competing company has expanded its product line;
nothing else has changed; - the production policy of a competing company caused a reduction in profits by 30%;
- therefore, the same production policy needs to be implemented.
The example is a colorful illustration of how inept use of the induction method contributes to the ruin of an enterprise.
Deduction and induction in psychology
Since there is a method, then, logically, there is also properly organized thinking (to use 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 psychology pages on the Internet there is practically no justification for the integrity of the deductive-inductive method. Although professional psychologists more often they encounter manifestations of induction, or more precisely, erroneous conclusions.
An example of induction in psychology, as an illustration of erroneous judgments, is the statement: my mother is deceiving, therefore, all women are deceivers. You can glean even more “erroneous” examples of induction from life:
- a student is incapable of anything if he gets a bad grade in math;
- he is a fool;
- he is smart;
- I can do anything;
And many others value judgments, derived from absolutely random and, at times, insignificant messages.
It should be noted: when the fallacy of a person’s judgment reaches the point of absurdity, a frontier of work appears for the psychotherapist. One example of induction at a specialist appointment:
“The patient is absolutely sure that the color red is only dangerous for him in any form. As a result, the person excluded this color scheme from his life - as much as possible. There are many opportunities for a comfortable stay at home. You can refuse all red items or replace them with analogues made in a different color. color scheme. But in in public places, at work, in the store - impossible. When placed in a stressful situation, each time the patient experiences a “tide” of completely different emotional states, which may pose a danger to others."
This example of induction, and unconscious induction, is called “fixed ideas.” If this happens to a mentally healthy person, we can talk about a lack of organization of mental activity. A way to get rid of obsessive states may 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 you from the consequences (of 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 point 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 broadening one’s horizons (those who think clearly express themselves clearly). This recommendation directs the “suffering” to the treasures of science and information (libraries, websites, educational initiatives, travel, etc.).
Special mention should be made of the so-called “psychological induction”. This term, although not often, can be found on the Internet. All sources do not provide at least a brief formulation of the definition of this term, but refer to “examples from life”, while passing it off as the new kind induction of 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 derive a “new term” based on false (often untrue) premises dooms the experimenter to obtain an erroneous (or hasty) statement.
It should be noted that the reference to the experiments of 1960 (without indicating the location, 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 organs of perception (the phrase “is affected” would fit in more organically in this case), makes one think about the gullibility and uncriticality of the author of the statement.
Instead of a conclusion
It is not for nothing that the queen of sciences, mathematics, 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 mass consciousness The method of deduction is associated with the famous Sherlock Holmes, who in his logical constructions more often uses examples of induction, in necessary situations using deduction.
The article examined examples of the application of these methods in various sciences and spheres of human activity.
If a sentence A(n), depending on a natural number n, is true for n=1 and from the fact that it is true for n=k (where k is any natural number), it follows that it is true for next date n=k+1, then assumption A(n) is true for any natural number n.
In a number of cases, it may be necessary to prove the validity of a certain statement not for all natural numbers, but only for n>p, where p is a fixed natural number. In this case, the principle of mathematical induction is formulated as follows.
If the proposition A(n) is true for n=p and if A(k) ≈ A(k+1) for any k>p, then the proposition A(n) is true for any n>p.
The proof using the method of mathematical induction is carried out as follows. First, the statement to be proved is checked for n=1, i.e. the truth of statement A(1) is established. This part of the proof is called the induction basis. Then comes the part of the proof called the induction step. In this part, they prove the validity of the statement for n=k+1 under the assumption of the validity of the statement for n=k (induction assumption), i.e. prove that A(k) 1 A(k+1)
Prove that 1+3+5+…+(2n-1)=n 2.
- 1) We have n=1=1 2 . Therefore, the statement is true for n=1, i.e. A(1) true
- 2) Let us prove that A(k) ≥ A(k+1)
Let k be any natural number and let the statement be true for n=k, i.e.
1+3+5+…+(2k-1)=k 2
Let us prove that then the statement is also true for the next natural number n=k+1, i.e. What
- 1+3+5+…+(2k+1)=(k+1) 2 Indeed,
- 1+3+5+…+(2k-1)+(2k+1)=k 2 +2k+1=(k+1) 2
So, A(k) 1 A(k+1). Based on the principle of mathematical induction, we conclude that assumption A(n) is true for any n O N
Prove that
1+x+x 2 +x 3 +…+x n =(x n+1 -1)/(x-1), where x No. 1
- 1) For n=1 we get
- 1+x=(x 2 -1)/(x-1)=(x-1)(x+1)/(x-1)=x+1
therefore, for n=1 the formula is correct; A(1) true
- 2) Let k be any natural number and let the formula be true for n=k,
- 1+x+x 2 +x 3 +…+x k =(x k+1 -1)/(x-1)
Let us prove that then the equality holds
- 1+x+x 2 +x 3 +…+x k +x k+1 =(x k+2 -1)/(x-1) Indeed
- 1+x+x 2 +x 3 +…+x k +x k+1 =(1+x+x 2 +x 3 +…+x k)+x k+1 =
=(x k+1 -1)/(x-1)+x k+1 =(x k+2 -1)/(x-1)
So, A(k) 1 A(k+1). Based on the principle of mathematical induction, we conclude that the formula is true for any natural number n
Prove that the number of diagonals convex n-gon equals n(n-3)/2
Solution: 1) For n=3 the statement is true, because in the triangle
A 3 =3(3-3)/2=0 diagonals; A 2 A(3) true
2) Suppose that in every convex k-gon there are A 1 x A k =k(k-3)/2 diagonals. A k Let us prove that then in a convex A k+1 (k+1)-gon the number of diagonals A k+1 =(k+1)(k-2)/2.
Let A 1 A 2 A 3 …A k A k+1 be a convex (k+1)-gon. Let's draw a diagonal A 1 A k in it. To calculate the total number of diagonals of this (k+1)-gon, you need to count the number of diagonals in the k-gon A 1 A 2 ...A k , add k-2 to the resulting number, i.e. the number of diagonals of the (k+1)-gon emanating from the vertex A k+1, and, in addition, the diagonal A 1 A k should be taken into account
Thus,
G k+1 =G k +(k-2)+1=k(k-3)/2+k-1=(k+1)(k-2)/2
So, A(k) 1 A(k+1). Due to the principle of mathematical induction, the statement is true for any convex n-gon.
Prove that for any n the following statement is true:
1 2 +2 2 +3 2 +…+n 2 =n(n+1)(2n+1)/6
Solution: 1) Let n=1, then
X 1 =1 2 =1(1+1)(2+1)/6=1
2) Assume that n=k
X k =k 2 =k(k+1)(2k+1)/6
3) Consider this statement for n=k+1
X k+1 =(k+1)(k+2)(2k+3)/6
X k+1 =1 2 +2 2 +3 2 +…+k 2 +(k+1) 2 =k(k+1)(2k+1)/6+ +(k+1) 2
=(k(k+1)(2k+1)+6(k+1) 2)/6=(k+1)(k(2k+1)+
6(k+1))/6=(k+1)(2k 2 +7k+6)/6=(k+1)(2(k+3/2)(k+
2))/6=(k+1)(k+2)(2k+3)/6
We have proven the equality to be true for n=k+1, therefore, by virtue of the method of mathematical induction, the statement is true for any natural number n
Prove that for any natural number n the equality is true:
1 3 +2 3 +3 3 +…+n 3 =n 2 (n+1) 2 /4
Solution: 1) Let n=1
Then X 1 =1 3 =1 2 (1+1) 2 /4=1. We see that for n=1 the statement is true.
2) Suppose that the equality is true for n=k
X k =k 2 (k+1) 2 /4
3) Let us prove the truth of this statement for n=k+1, i.e.
X k+1 =(k+1) 2 (k+2) 2 /4. X k+1 =1 3 +2 3 +…+k 3 +(k+1) 3 =k 2 (k+1) 2 /4+(k+1) 3 =(k 2 (k++1) 2 +4(k+1) 3)/4=(k+1) 2 (k 2 +4k+4)/4=(k+1) 2 (k+2) 2 /4
From the above proof it is clear that the statement is true for n=k+1, therefore, the equality is true for any natural number n
Prove that
((2 3 +1)/(2 3 -1)) ґ ((3 3 +1)/(3 3 -1)) ґ ... ґ ((n 3 +1)/(n 3 -1))= 3n(n+1)/2(n 2 +n+1), where n>2
Solution: 1) For n=2 the identity looks like:
- (2 3 +1)/(2 3 -1)=(3 ґ 2 ґ 3)/2(2 2 +2+1), i.e. it's true
- 2) Assume that the expression is true for n=k
- (2 3 +1)/(2 3 -1) ґ … ґ (k 3 +1)/(k 3 -1)=3k(k+1)/2(k 2 +k+1)
- 3) Let us prove the validity of the expression for n=k+1
- (((2 3 +1)/(2 3 -1)) ґ … ґ ((k 3 +1)/(k 3 -1))) ґ (((k+1) 3 +
1)/((k+1) 3 -1))=(3k(k+1)/2(k 2 +k+1)) ґ ((k+2)((k+
1) 2 -(k+1)+1)/k((k+1) 2 +(k+1)+1))=3(k+1)(k+2)/2 ґ
ґ ((k+1) 2 +(k+1)+1)
We have proven the equality to be true for n=k+1, therefore, by virtue of the method of mathematical induction, the statement is true for any n>2
Prove that
1 3 -2 3 +3 3 -4 3 +…+(2n-1) 3 -(2n) 3 =-n 2 (4n+3) for any natural number n
Solution: 1) Let n=1, then
- 1 3 -2 3 =-1 3 (4+3); -7=-7
- 2) Suppose that n=k, then
- 1 3 -2 3 +3 3 -4 3 +…+(2k-1) 3 -(2k) 3 =-k 2 (4k+3)
- 3) Let us prove the truth of this statement for n=k+1
- (1 3 -2 3 +…+(2k-1) 3 -(2k) 3)+(2k+1) 3 -(2k+2) 3 =-k 2 (4k+3)+
+(2k+1) 3 -(2k+2) 3 =-(k+1) 3 (4(k+1)+3)
The validity of the equality for n=k+1 has also been proven, therefore the statement is true for any natural number n.
Prove the identity is correct
(1 2 /1 ґ 3)+(2 2 /3 ґ 5)+…+(n 2 /(2n-1) ґ (2n+1))=n(n+1)/2(2n+1) for any natural n
- 1) For n=1 the identity is true 1 2 /1 ґ 3=1(1+1)/2(2+1)
- 2) Suppose that for n=k
- (1 2 /1 ґ 3)+…+(k 2 /(2k-1) ґ (2k+1))=k(k+1)/2(2k+1)
- 3) Let us prove that the identity is true for n=k+1
- (1 2 /1 ґ 3)+…+(k 2 /(2k-1)(2k+1))+(k+1) 2 /(2k+1)(2k+3)=(k(k+ 1)/2(2k+1))+((k+1) 2 /(2k+1)(2k+3))=((k+1)/(2k+1)) ґ ((k/2 )+((k+1)/(2k+3)))=(k+1)(k+2) ґ (2k+1)/2(2k+1)(2k+3)=(k+1 )(k+2)/2(2(k+1)+1)
From the above proof it is clear that the statement is true for any natural number n.
Prove that (11 n+2 +12 2n+1) is divisible by 133 without remainder
Solution: 1) Let n=1, then
11 3 +12 3 =(11+12)(11 2 -132+12 2)=23 ґ 133
But (23 ґ 133) is divisible by 133 without a remainder, which means that for n=1 the statement is true; A(1) is true.
- 2) Suppose that (11 k+2 +12 2k+1) is divisible by 133 without a remainder
- 3) Let us prove that in this case (11 k+3 +12 2k+3) is divisible by 133 without a remainder. Indeed
- 11 k+3 +12 2l+3 =11 ґ 11 k+2 +12 2 ґ 12 2k+1 =11 ґ 11 k+2 +
+(11+133) ґ 12 2k+1 =11(11 k+2 +12 2k+1)+133 ґ 12 2k+1
The resulting sum is divided by 133 without a remainder, since its first term is divisible by 133 without a remainder by assumption, and in the second one of the factors is 133. So, A(k) 1 A(k+1). By virtue of the method of mathematical induction, the statement is proven
Prove that for any n 7 n -1 is divisible by 6 without a remainder
- 1) Let n=1, then X 1 =7 1 -1=6 is divided by 6 without a remainder. This means that for n=1 the statement is true
- 2) Suppose that when n=k 7 k -1 is divided by 6 without a remainder
- 3) Let us prove that the statement is true for n=k+1
X k+1 =7 k+1 -1=7 ґ 7 k -7+6=7(7 k -1)+6
The first term is divisible by 6, since 7 k -1 is divisible by 6 by assumption, and the second term is 6. This means 7 n -1 is a multiple of 6 for any natural number n. By virtue of the method of mathematical induction, the statement is proven.
Prove that 3 3n-1 +2 4n-3 for an arbitrary natural number n is divisible by 11.
1) Let n=1, then
X 1 =3 3-1 +2 4-3 =3 2 +2 1 =11 is divided by 11 without a remainder.
This means that for n=1 the statement is true
- 2) Suppose that when n=k X k =3 3k-1 +2 4k-3 is divided by 11 without a remainder
- 3) Let us prove that the statement is true for n=k+1
X k+1 =3 3(k+1)-1 +2 4(k+1)-3 =3 3k+2 +2 4k+1 =3 3 ґ 3 3k-1 +2 4 ґ 2 4k-3 =
27 ґ 3 3k-1 +16 ґ 2 4k-3 =(16+11) ґ 3 3k-1 +16 ґ 2 4k-3 =16 ґ 3 3k-1 +
11 ґ 3 3k-1 +16 ґ 2 4k-3 =16(3 3k-1 +2 4k-3)+11 ґ 3 3k-1
The first term is divisible by 11 without a remainder, since 3 3k-1 +2 4k-3 is divisible by 11 by assumption, the second is divisible by 11, because one of its factors is the number 11. This means that the sum is divisible by 11 without a remainder for any natural number n. By virtue of the method of mathematical induction, the statement is proven.
Prove that 11 2n -1 for an arbitrary natural number n is divisible by 6 without a remainder
- 1) Let n=1, then 11 2 -1=120 is divisible by 6 without a remainder. This means that for n=1 the statement is true
- 2) Suppose that when n=k 1 2k -1 is divided by 6 without a remainder
- 11 2(k+1) -1=121 ґ 11 2k -1=120 ґ 11 2k +(11 2k -1)
Both terms are divisible by 6 without a remainder: the first contains a multiple of 6, 120, and the second is divisible by 6 without a remainder by assumption. This means that the sum is divisible by 6 without a remainder. By virtue of the method of mathematical induction, the statement is proven.
Prove that 3 3n+3 -26n-27 for an arbitrary natural number n is divisible by 26 2 (676) without a remainder
Let us first prove that 3 3n+3 -1 is divisible by 26 without a remainder
- 1. When n=0
- 3 3 -1=26 is divided by 26
- 2. Suppose that for n=k
- 3 3k+3 -1 is divisible by 26
- 3. Let us prove that the statement is true for n=k+1
- 3 3k+6 -1=27 ґ 3 3k+3 -1=26 ґ 3 3л+3 +(3 3k+3 -1) -divided by 26
Now let's prove the statement formulated in the problem statement
- 1) Obviously, for n=1 the statement is true
- 3 3+3 -26-27=676
- 2) Suppose that for n=k the expression 3 3k+3 -26k-27 is divided by 26 2 without a remainder
- 3) Let us prove that the statement is true for n=k+1
- 3 3k+6 -26(k+1)-27=26(3 3k+3 -1)+(3 3k+3 -26k-27)
Both terms are divisible by 26 2; the first is divisible by 26 2 because we have proven the expression in parentheses is divisible by 26, and the second is divisible by the induction hypothesis. By virtue of the method of mathematical induction, the statement is proven
Prove that if n>2 and x>0, then the inequality (1+x) n >1+n ґ x is true
- 1) For n=2 the inequality is valid, since
- (1+x) 2 =1+2x+x 2 >1+2x
So A(2) is true
- 2) Let us prove that A(k) ≈ A(k+1), if k> 2. Assume that A(k) is true, i.e., that the inequality
- (1+x) k >1+k ґ x. (3)
Let us prove that then A(k+1) is also true, i.e., that the inequality
(1+x) k+1 >1+(k+1) ґ x
In fact, multiplying both sides of inequality (3) by the positive number 1+x, we obtain
(1+x) k+1 >(1+k ґ x)(1+x)
Consider the right side of the last inequality; we have
(1+k ґ x)(1+x)=1+(k+1) ґ x+k ґ x 2 >1+(k+1) ґ x
As a result, we get that (1+x) k+1 >1+(k+1) ґ x
So, A(k) 1 A(k+1). Based on the principle of mathematical induction, it can be argued that Bernoulli’s inequality is valid for any n> 2
Prove that the inequality (1+a+a 2) m > 1+m ґ a+(m(m+1)/2) ґ a 2 for a> 0 is true
Solution: 1) When m=1
- (1+a+a 2) 1 > 1+a+(2/2) ґ a 2 both sides are equal
- 2) Suppose that for m=k
- (1+a+a 2) k >1+k ґ a+(k(k+1)/2) ґ a 2
- 3) Let us prove that for m=k+1 the inequality is true
- (1+a+a 2) k+1 =(1+a+a 2)(1+a+a 2) k >(1+a+a 2)(1+k ґ a+
+(k(k+1)/2) ґ a 2)=1+(k+1) ґ a+((k(k+1)/2)+k+1) ґ a 2 +
+((k(k+1)/2)+k) ґ a 3 +(k(k+1)/2) ґ a 4 > 1+(k+1) ґ a+
+((k+1)(k+2)/2) ґ a 2
We have proven the inequality to be true for m=k+1, therefore, by virtue of the method of mathematical induction, the inequality is valid for any natural number m
Prove that for n>6 the inequality 3 n >n ґ 2 n+1 is true
Let us rewrite the inequality in the form (3/2) n >2n
- 1. For n=7 we have 3 7 /2 7 =2187/128>14=2 ґ 7 the inequality is true
- 2. Suppose that for n=k (3/2) k >2k
- 3) Let us prove the inequality for n=k+1
- 3 k+1 /2 k+1 =(3 k /2 k) ґ (3/2)>2k ґ (3/2)=3k>2(k+1)
Since k>7, the last inequality is obvious.
By virtue of the method of mathematical induction, the inequality is valid for any natural number n
Prove that for n>2 the inequality is true
1+(1/2 2)+(1/3 2)+…+(1/n 2)<1,7-(1/n)
- 1) For n=3 the inequality is true
- 1+(1/2 2)+(1/3 2)=245/180
- 2. Suppose that for n=k
- 1+(1/2 2)+(1/3 2)+…+(1/k 2)=1.7-(1/k)
- 3) Let us prove the validity of the inequality for n=k+1
- (1+(1/2 2)+…+(1/k 2))+(1/(k+1) 2)
Let us prove that 1.7-(1/k)+(1/(k+1) 2)<1,7-(1/k+1) Ы
S (1/(k+1) 2)+(1/k+1)<1/k Ы (k+2)/(k+1) 2 <1/k Ы
ы k(k+2)<(k+1) 2 Ы k 2 +2k The latter is obvious, and therefore 1+(1/2 2)+(1/3 2)+…+(1/(k+1) 2)<1,7-(1/k+1) By virtue of the method of mathematical induction, the inequality is proven. 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 a mathematical profile. Primary goals: to introduce students to the method of mathematical induction and teach how to apply it in solving various problems. The methodological development addresses issues of elementary mathematics: divisibility problems, proof of identities, proof of inequalities, problems of varying degrees of complexity are proposed, including problems proposed at Olympiads. The role of inductive conclusions in experimental sciences is very great. They give those provisions from which further conclusions are then drawn through deduction. Name method of mathematical induction deceptive - in fact, this method is deductive and provides rigorous proof of statements guessed through induction. The method of mathematical induction helps to identify connections between different branches of mathematics and helps the development of the student’s mathematical culture. 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 TEACHERS
1. M.L. Galitsky. In-depth study of the course of algebra and mathematical analysis. – M. Education. 1986. 2. L.I.Zvavich. Algebra and the beginnings of analysis. Didactic materials. M. Bustard.2001. 3. N.Ya.Vilenkin. Algebra and mathematical analysis. M Enlightenment.1995. 4. Yu.V.Mikheev. Method of mathematical induction. NSU.1995. LITERATURE FOR STUDENTS
1. N.Ya.Vilenkin. Algebra and mathematical analysis. M Enlightenment.1995. 2. Yu.V.Mikheev. Method of mathematical induction. NSU.1995. KEYWORDS
Induction, axiom, principle of mathematical induction, complete induction, incomplete induction, statement, identity, inequality, divisibility. DIDACTICAL 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 of searching for new results and proving the truth of the assumptions made. Although this method in mathematics is not new, interest in it does not wane. For the first time in a clear presentation, the method of mathematical induction was used in the 17th century by the outstanding French scientist Blaise Pascal when proving the properties of the number triangle, which has since bear his name. 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. Let's look at the idea of mathematical induction using examples. Example No. 1.
The square is divided into two parts by a segment, then one of the resulting parts is divided into two parts, and so on. Determine how many parts the square will be divided into P steps? Solution. After the first step, according to the condition, we will 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. This begs the suggestion that through P steps we will get (n+1) Part. But this proposition needs to be proven. Let's assume that after To steps the square will be divided into (k+1) Part. Then on (k+1) step we take To parts will be left unchanged, but (k+1) divide part into two parts and get (k+2) parts. You notice that you can argue this way for as long as you like, ad infinitum. That is, our assumption is that through P steps the square will be divided into (n+1) part becomes proven. Example No. 2.
My grandmother had a granddaughter who really loved jam, and especially the kind that came in a liter jar. But my grandmother did not allow me to touch him. And the granddaughters planned to deceive their grandmother. He decided to eat 1/10 liter from this jar every day and top it up with water, mixing thoroughly. How many days will it take for grandma to discover the deception if the jam remains the same in appearance when diluted by half with water? Solution. Let's find how much pure jam remains in the jar after P days. After the first day, a mixture consisting of 9/10 jam and 1/10 water will remain in the jar. After two days, 1/10 of the mixture of water and jam will disappear from the jar and will remain (1 liter of the mixture contains 9/10 liters of jam, 1/10 liter 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. 1 liter of mixture contains 81/100 liters of jam, 1/10 liter of mixture contains 81/1000 liters of jam. 81/100 – 81/1000= 729/1000=(9/10) 3 liters of jam will remain after 3 days, and the rest will be taken up by water. A pattern emerges. Through P days left in bank (9/10) P l jam. But this, again, is just our guess. Let To– an arbitrary natural number. Let's assume that after To days there will be (9/10) liters of jam left in the jar. Let's see what will be in the bank in another day, that is, in (k+1) day. Will disappear from the jar 1/10l a mixture consisting of (9/10)
To l jam and water. IN 1l the 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 jam, after 7 days - 4782969/10000000l jam, that is, less than half. Answer: After 7 days, grandma will discover the deception. Let's try to highlight the most important things in solving the problems considered. We began to solve each of them by considering individual or, as they say, special cases. Then, based on our observations, we made some assumption P(n), depending on natural P.
the statement has been verified, that is, proven P(1), P(2), P(3);
suggested that P(n) valid for p=k and concluded that then it will be true in the next n, n=k+1.
And then they reasoned something like this: P(1) right, P(2) right, P(3) right, P(4) right... that means right P(p).
The principle of mathematical induction.
Statement P(n), depending on natural P, valid for all natural P, If 1) the validity of the statement has been proven when n=1;
2) from the assumption of the validity of the statement P(n) at p=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 using 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 where a mathematical statement concerns a finite number of objects, it can be proven by testing 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 not yet been proven or disproved. Even if we tested this theorem for the first billion, it would not bring us one step closer to its proof. In the natural sciences, incomplete induction is used, checking the experiment several times and transferring the result to all cases. Example No. 3.
Let us guess, using incomplete induction, the 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 p=k.
Let us prove that is true for n=k+1.
Conclusion: the formula for the sum of cubes of natural numbers is true for any natural number P.
Example No. 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 No. 5.
Write the following expressions as a sum: 1) Example No. 6.
Write the following amounts using the sign 2) Example No. 7.
Write the following expressions as products: 1) 3) Example No. 8.
Write the following works using the sign (capital Greek letter "pi") 1) Example No. 9.
Calculating the value of a polynomial Is this assumption correct? Solution. If each term of a sum is divisible by a number, then the sum is divided by that number, Analysis of a finite number of cases plays an important role in mathematics: without giving a proof of a particular 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 hypothesis that any natural number, starting with two, is the sum of no more than three prime numbers. Lesson #3.
The method of mathematical induction allows one to prove various identities. Example No. 10. Let us prove that for everyone P the identity holds Solution. Let's put We need to prove that Let us prove that Then from the truth of the identity Using the principle of mathematical induction, the truth of the identity is proven for all P.
Example No. 11.
Let's prove the identity Proof. the resulting equalities term by term. Lesson No. 4.
Proof of identities using the method of mathematical induction.
Example No. 12.
Let's prove the identity Proof. Using the principle of mathematical induction, we proved that the equality is true for all P.
Example No. 13.
Let's prove the identity Proof. Using the principle of mathematical induction, we proved that the statement is true for any natural P.
Example No. 14.
Let's prove the identity Proof. Example No. 15.
Let's prove the identity 1)
n=1;
2) for p=k
equality holds 3) we prove that the equality holds for p=k+1:
Conclusion: the identity is valid for any natural P.
Example No. 16. Let's prove the identity Proof. If n=1
, That Let the identity hold for p=k.
Let us prove that the identity holds for n=k+1.
Then the identity is true for any natural P.
Lesson No. 5.
Proof of identities using the method of mathematical induction.
Example No. 17. Let's prove the identity Proof. If n=2
, then we get the correct equality: Let the equality be true forp=k:
Let us prove the validity of the statement when n=k+1.
According to the principle of mathematical induction, the identity is proven. Example No. 18.
Let's prove the identity At n=2
this identity can be rewritten in a very simple form and obviously true. Let at p=k really Let us prove the validity of the statement whenn=k+1,
that is, the equality holds: . So, we have proven that the identity is true for any natural number n≥2.
Example No. 19.
Let's prove the identity At n=1
we get the correct equality: Let's assume that when p=k we also get the correct equality: Let us prove that the equality is valid for p=k+1:
Then the identity is valid for any natural number P.
Lesson No. 6.
Solving divisibility problems.
Example No. 20. Prove by mathematical induction that Proof. At n=1
there is a division into6
without a trace, Let at p=k
expression Let us prove that when p=k+1
expression Each term is a multiple 6
, therefore the sum is a multiple 6
.
Example No. 21.
Proof. At n=1
the expression is divided without remainder Let at p=k
expression At p=k+1 divided by 5
.
Example No. 22.
Prove the divisibility of an expression Proof. At n=1 multiple 16
.
Let at p=k
At p=k+1
All terms are divisible by 16:
the first is obvious, the second is by assumption, and the third has an even number in brackets. Example No. 23.
Prove divisibility Proof. Let us first prove that At n=0
Let at p=k
Then at p=k+1 divided by 26
.
Now we will carry out a proof of the statement formulated in the problem statement. At n=1 divided by 676.
At p=k
it's true that At p=k+1
.
Both terms are divisible by 676
; first - because we proved divisibility by 26
expression in parentheses, and the second is divided according to the assumption of induction. Lesson No. 7.
Solving divisibility problems.
Example No. 24.
Prove that Proof. At n=1
At p=k
At p=k+1
each term is divided by5
without a trace. Example No. 25.
Prove that Proof. At n=1
Let at p=k
At p=k+1 divided by 6
without a remainder, since each term is divisible by6
without remainder: the first term is by induction hypothesis, the second is obvious, the third is because Example No. 26.
Prove that Proof. Let's prove that At n=1 At p=k+1 divided by 9
.
Example No. 27.
Prove that it is divisible by15
without a trace. Proof. At n=1 divided by 15
.
Let at p=k divided by 15
without a trace. At p=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 Lesson No. 8-9.
Proving inequalities by mathematical induction
Example No. 28. At n=1 we have Let at p=k At p=k+1 Then the inequality is valid for any natural P. Example No. 29. Prove that the inequality is true At n=1 we get the correct inequality 4 >1.
Let at p=k inequality is true Let us prove that when p=k+1 inequality is true For any natural To there is inequality. If Example No. 30. Let n=1 Let us assume that the inequality holds for p=k: At p=k+1 Example No. 31. Prove the validity of the inequality Let us first prove that for any natural T inequality is true At n=1 the original inequality is correct Let the inequality hold for p=k: At p=k+1 Lesson No. 10.
Solving problems on the topic
Method of mathematical induction.
Example No. 32. Prove Bernoulli's inequality. If Proof. At n=1
the inequality being proved takes the form Since by condition Because So, the inequality is true for n=1, and from its truth at p=k it follows that it is true even if n=k+1. This means that, by virtue of mathematical induction, it holds for all natural P.
For example, Example No. 33.
Find all natural valuesP
, for which the inequality is true Solution. At n=1 inequality is fair. At n=2 inequality is also true. At n=3 the inequality no longer holds. Only when n=6 the inequality holds, so we can take as the basis of induction n=6.
Suppose that the inequality is true for some natural To:
The last inequality is satisfied if METHOD OF MATHEMATICAL INDUCTION The word induction in Russian means guidance, and conclusions based on observations, experiments, i.e. are called inductive. obtained by inference from the particular to the general. For example, every day we observe that the Sun rises from the east. Therefore, you can be sure that tomorrow it will appear in the east, and not in the west. We draw this conclusion without resorting to any assumptions about the reason for the movement of the Sun across the sky (moreover, this movement itself turns out to be apparent, since the globe is actually moving). And yet this inductive conclusion correctly describes the observations we will make tomorrow. The role of inductive conclusions in experimental sciences is very great. They give those provisions from which further conclusions are then drawn through deduction. And although theoretical mechanics is based on Newton’s three laws of motion, these laws themselves were the result of deep thinking through experimental data, in particular Kepler’s laws of planetary motion, which he derived from the processing of many years of observations by the Danish astronomer Tycho Brahe. Observation and induction turn out to be useful in the future for clarifying the assumptions made. After Michelson's experiments on measuring the speed of light in a moving medium, it turned out to be necessary to clarify the laws of physics and create the theory of relativity. In mathematics, the role of induction is largely that it underlies the chosen axiomatics. After long-term practice showed that a straight path is always shorter than a curved or broken one, it was natural to formulate an axiom: for any three points A, B and C, the inequality The concept of following, which is the basis of arithmetic, also appeared from observations of the formation of soldiers, ships and other ordered sets. One should not, however, think that this exhausts the role of induction in mathematics. Of course, we should not experimentally test theorems logically deduced from axioms: if no logical errors were made during the derivation, then they are true insofar as the axioms we accepted are true. But a lot of statements can be deduced from this system of axioms. And the selection of those statements that need to be proven is again suggested by induction. It is this that allows you to separate useful theorems from useless ones, indicates which theorems may turn out to be true, and even helps to outline the path of proof. In many branches of arithmetic, algebra, geometry, and analysis, it is necessary to prove the truth of sentences A(n) depending on a natural variable. The proof of the truth of the proposition A(n) for all values of a variable can often be carried out by the method of mathematical induction, which is based on the following principle. The proposition A(n) is considered true for all natural values of the variable if the following two conditions are met: Proposition A(n) is true for n=1. From the assumption that A(n) is true for n=k (where k is any natural number), it follows that it is true for the next value n=k+1. This principle is called the principle of mathematical induction. It is usually chosen as one of the axioms defining the natural series of numbers, and is therefore accepted without proof. The method of mathematical induction means the following method of proof. If you want to prove the truth of a sentence A(n) for all natural n, then, firstly, you should check the truth of the statement A(1) and, secondly, assuming the truth of the statement A(k), try to prove that the statement A(k +1) true. If this can be proven, and the proof remains valid for each natural value of k, then, in accordance with the principle of mathematical induction, the proposition A(n) is recognized as true for all values of n. The method of mathematical induction is widely used in proving theorems, identities, inequalities, in solving divisibility problems, in solving some geometric and many other problems. divisibility Using the method of mathematical induction, you can prove various statements regarding the divisibility of natural numbers. The following statement can be proven relatively simply. Let us show how it is obtained using the method of mathematical induction. Example 1. If n is a natural number, then the number is even. When n=1 our statement is true: - an even number. Let's assume that it is an even number. Since , a 2k is an even number, then Example 2.Prove the truth of the sentence A(n)=(the number 5 is a multiple of 19), n is a natural number. Solution. The statement A(1)=(a number divisible by 19) is true. Suppose that for some value n=k A(k)=(number divisible by 19) is true. Then, since Obviously, A(k+1) is also true. Indeed, the first term is divisible by 19 due to the assumption that A(k) is true; the second term is also divisible by 19 because it contains a factor of 19. Both conditions of the principle of mathematical induction are satisfied, therefore, the proposition A(n) is true for all values of n. summing series
Example 1.Prove formula Solution. When n=1, both sides of the equality turn to one and, therefore, the first condition of the principle of mathematical induction is satisfied. Let's assume that the formula is correct for n=k, i.e. Let's add to both sides of this equality and transform the right side. Then we get Thus, from the fact that the formula is true for n=k, it follows that it is also true for n=k+1. This statement is true for any natural value of k. So, the second condition of the principle of mathematical induction is also satisfied. The formula is proven. Example 2.Prove that the sum of the first n numbers of the natural series is equal to . Solution. Let us denote the required amount, i.e. When n=1 the hypothesis is true. Let Indeed, The problem is solved. Example 3.Prove that the sum of the squares of the first n numbers of the natural series is equal to Solution. Let . Let's pretend that And finally. Example 4. Prove that . Solution. If , then Example 5. Prove that Solution. When n=1 the hypothesis is obviously true. Let . Let's prove that . Really, Examples of applying the method of mathematical induction to
proof of inequalities
Example 1.Prove that for any natural number n>1 Solution. Let us denote the left side of the inequality by . Therefore, for n=2 the inequality is valid. Let for some k. Let us prove that then and . We have Comparing and , we have For any positive integer k, the right-hand side of the last equality is positive. That's why . But that means also. Example 2.Find the error in the reasoning. Statement. For any natural number n the inequality is true. Proof. . (1)
Let us prove that then the inequality is also valid for n=k+1, i.e. Indeed, no less than 2 for any natural k. Let's add to the left side of inequality (1) and to the right side 2. We get a fair inequality, or Example 3.Prove that Solution. For n=2 the inequality is true, since . Let the inequality be true for n=k, where k is some natural number, i.e. Let us show that then the inequality is also valid for n=k+1, i.e. . (2)
Indeed, by condition, , therefore the inequality is true , (3)
obtained from inequality (1) by multiplying each part by . Let us rewrite inequality (3) as follows: . Discarding the positive term on the right side of the last inequality, we obtain fair inequality (2). Example 4. Prove that (1)
where , , n is a natural number greater than 1. Solution. For n=2 inequality (1) takes the form Since , then the inequality is true . (3)
By adding to each part of inequality (3) we obtain inequality (2). This proves that for n=2 inequality (1) is true. Let inequality (1) be true for n=k, where k is some natural number, i.e. . (4)
Let us prove that then inequality (1) must also be true for n=k+1, i.e. (5)
Let's multiply both sides of inequality (4) by a+b. Since, by condition, , we obtain the following fair inequality: . (6)
In order to prove the validity of inequality (5), it is enough to show that , (7)
or, what is the same, . (8)
Inequality (8) is equivalent to inequality If , then , and on the left side of inequality (9) we have the product of two positive numbers. If , then , and on the left side of inequality (9) we have the product of two negative numbers. In both cases, inequality (9) is true. This proves that the validity of inequality (1) for n=k implies its validity for n=k+1. Method of mathematical induction applied to others
tasks The most natural application of the method of mathematical induction in geometry, close to the use of this method in number theory and algebra, is its application to solving geometric calculation problems. Let's look at a few examples. Example 1.Calculate the side of a regular square inscribed in a circle of radius R. Solution. When n=2 correct 2 n - a square is a square; his side. Further, according to the doubling formula we find that the side of a regular octagon Let us assume that the side of a regular inscribed square is expressed by formula (1). In this case, according to the doubling formula whence it follows that formula (1) is valid for all n. Example 2.How many triangles can an n-gon (not necessarily convex) be divided into by its disjoint diagonals? Solution. For a triangle, this number is equal to one (not a single diagonal can be drawn in a triangle); for a quadrilateral this number is obviously two. Suppose we already know that every k-gon, where k A n A 1 A 2 Let A 1 A k be one of the diagonals of this partition; it divides the n-gon A 1 A 2 ...A n into the k-gon A 1 A 2 ...A k and the (n-k+2)-gon A 1 A k A k+1 ...A n . Due to the assumption made, the total number of triangles in the partition will be equal to (k-2)+[(n-k+2)-2]=n-2; Thus, our statement is proven for all n. Example 3.State the rule for calculating the number P(n) of ways in which a convex n-gon can be divided into triangles by disjoint diagonals. Solution. For a triangle, this number is obviously equal to one: P(3)=1. Let us assume that we have already determined the numbers P(k) for all k Р(n)=P(n-1)+P(n-2)P(3)+P(n-3)P(4)+…+P(3)P(n-2)+P(n -1). Using this formula we consistently obtain: P(4)=P(3)+P(3)=2, P(5)=P(4)+P(3)P(3)+P(4)+5, P(6)=P(5)+P(4)P(3)+P(3)P(4)+P(5)=14 etc. You can also solve problems with graphs using the method of mathematical induction. Let there be a network of lines on the plane that connect some points and have no other points. We will call such a network of lines a map, given points as its vertices, segments of curves between two adjacent vertices - the boundaries of the map, parts of the plane into which it is divided by borders - the countries of the map. Let some map be given on the plane. We will say that it is correctly colored if each of its countries is painted with a certain color, and any two countries that have a common border are painted with different colors. Example 4.There are n circles on the plane. Prove that for any arrangement of these circles, the map they form can be correctly colored with two colors. Solution. For n=1 our statement is obvious. Let us assume that our statement is true for any map formed by n circles, and let there be n+1 circles on the plane. By removing one of these circles, we get a map that, by virtue of the assumption made, can be correctly colored with two colors, for example, black and white. The proof method based on Peano's axiom 4 is used to prove many mathematical properties and various statements. The basis for this is the following theorem. Theorem. If the statement A(n) with natural variable n true for n= 1 and from the fact that it is true for n = k, it follows that it is true for the next number n=k, then the statement A(n) n. Proof. Let us denote by M the set of those and only those natural numbers for which the statement A(n) true. Then from the conditions of the theorem we have: 1) 1 M; 2) k MkM. From here, based on axiom 4, we conclude that M =N, i.e. statement A(n) true for any natural n. The proof method based on this theorem is called by the method of mathematical induction, and the axiom is the axiom of induction. This proof consists of two parts: 1) prove that the statement A(n) true for n= A(1); 2) assume that the statement A(n) true for n = k, and, based on this assumption, prove that the statement A(n) true for n = k + 1, i.e. that the statement is true A(k) A(k + 1).
If A( 1) A(k) A(k + 1)
- true statement, then they conclude that the statement A(n) true for any natural number n. Proof by the method of mathematical induction can begin not only with confirmation of the truth of the statement for n= 1, but also from any natural number m. In this case the statement A(n) will be proven for all natural numbers nm. Problem: Let us prove that for any natural number the equality 1 + 3 + 5 … + (2 n- 1) =
n. Solution. Equality 1 + 3 + 5 … + (2 n- 1) =
n is a formula that can be used to find the sum of the first consecutive odd natural numbers. For example, 1 + 3 + 5 + 7 = 4= 16 (sum contains 4 terms), 1 + 3 + 5 + 7 + 9 + 11 = 6= 36 (sum contains 6 terms); if this sum contains 20 terms of the indicated type, then it is equal to 20 = 400, etc. Having proven the truth of this equality, we will be able to find the sum of any number of terms of the specified type using the formula. 1) Let us verify the truth of this equality for n= 1. When n= 1 the left side of the equality consists of one term equal to 1, the right side is equal to 1= 1. Since 1 = 1, then for n= 1 this equality is true. 2) Suppose that this equality is true for n = k, i.e. that 1 + 3 + 5 + … + (2 k- 1) =
k. Based on this assumption, we prove that it is true for n = k + 1, i.e. 1 + 3 + 5 + … + (2 k- 1) + (2(k + 1) - 1) =
(k + 1). Let's look at the left side of the last equality. By assumption, the sum of the first k terms is equal to k and therefore 1 + 3 + 5 + … + (2 k- 1) + (2(k + 1) - 1) =
1 + 3 + 5 + … + (2k- 1) + (2k+ 1)= = k+(2k + 1) =
k+ 2k + 1.
Expression
k+ 2k + 1 is identically equal to the expression ( k + 1).
Therefore, the truth of this equality for n = k + 1 has been proven. Thus, this equality is true for n= 1 and from its truth for n = k must be true for n = k + 1. This proves that this equality is true for any natural number. Using the method of mathematical induction, you can prove the truth of not only equalities, but also inequalities. Task. Prove that , where nN. Solution. Let us check the truth of the inequality at n= 1. We have - true inequality. Let us assume that the inequality is true for n = k, those. - true inequality. Let us prove, based on the assumption, that it is also true for
n = k + 1, i.e. Let's transform the left side of the inequality (*), taking into account that: . But So, this inequality is true for n= 1, and, from the fact that the inequality is true for some n= k, we found that it is also true for n= k + 1. Thus, using axiom 4, we proved that this inequality is true for any natural number. Other statements can be proven using the method of mathematical induction. Task. Prove that for any natural number the statement is true. Solution. Let's check the truth of the statement when n= 1: -true statement. Let us assume that this statement is true for n = k: . Let us show, using this, the truth of the statement when n = k + 1: Let's transform the expression: . Let's find the difference k And k+ 1 members. If it turns out that the resulting difference is a multiple of 7, and by assumption the subtrahend is divisible by 7, then the minuend is also a multiple of 7: The product is a multiple of 7, therefore, and . Thus, this statement is true for n= 1 and from its truth for n = k must be true for n = k + 1. This proves that this statement is true for any natural number. Task. Prove that for any natural number n 2 statement (7-1)24 is true. Solution. 1) Let's check the truth of the statement when n= 2: - true statement.
2) 
3)
; 4) 
.
Greek letter "sigma".
:
4) 
2)
f
(
n
)=
n
2
+
n
+11
, at n=1,2,3,4.5,6,7
one can make the assumption that for any naturalP number f
(
n
)
simple.
is not a prime number for any natural numberP.
follows the truth of the identity 
; 
. This means that this identity is true for everyoneP
.
when n≥2.
.
divided by 6
without a trace.
.
multiple6.
multiple6
.
on5
without a trace.
.
also divided into5
without a trace.
on16.
multiple16.
on676.
divided by 
.
.
divided by26
.
divided by26
2
.
divided by5
without a trace.
divided by5.
divided by5
without a trace.
divided by6
without a trace.
divided by6
without a trace.
divided by6
without a trace.
even number.
when divided by9
gives the remainder 1
.
divided by9
.
divided by 9
. Let at p=k
divided by9
.
multiple5
(proven in example No. 21), the fourth and fifth terms are also multiples5
, which is obvious, then the sum is a multiple15
.
.
- right.
- true inequality.
at any P.
.
at 
That
under any natural P and any 
, right.
.
under any natural P.
Let's multiply both sides of the inequality by 
. We obtain an equivalent inequality or 
; 
; - this inequality holds for any natural T.
; 
; 
.
.
, then for all natural valuesP
inequality holds
and obviously fair. Let us assume that it is true forp=k
, that is, what 
.
, That 
, and therefore the inequality does not change its meaning when both its parts are multiplied by 
:
, then we get that
.
Consider the inequality
Test work on the topic p=1 is given recurrently: p≥5, where P- -natural number.
The essence of the method of mathematical induction
The method of mathematical induction in solving problems on
even. So, parity is proven for n=1, parity is deduced from parity 
.This means that it is even for all natural values of n.
Application of the method of mathematical induction to
, n is a natural number.
.
.
. Let's show that 
.
.
.
. Then
.
, .
, i.e. 
.
.
. The statement has been proven.
, where >-1, , n is a natural number greater than 1.
. (1)
. (2)
. (9)
, side of a regular hexagon 
, side of a regular thirty-two triangle 
. We can therefore assume that the side of the correct inscribed 2 n - square for any equal
. (1)
,
(*).
, which means 
.
.
