C 6 method of mathematical induction. The method of mathematical induction and its application to problem solving
True knowledge at all times was based on establishing a pattern and proving its veracity in certain circumstances. For such a long period of existence of logical reasoning, the formulations of the rules were given, and Aristotle even compiled a list of "correct reasoning." Historically, it is customary to divide all inferences into two types - from the concrete to the plural (induction) and vice versa (deduction). It should be noted that the types of evidence from particular to general and from general to particular exist only in interconnection and cannot be interchanged.
Induction in mathematics
The term "induction" (induction) has Latin roots and literally translates as "guidance". Upon closer examination, one can distinguish the structure of the word, namely the Latin prefix - in- (denoting 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 clearly shows this.
Induction and the laws of logic
Historically, they always "walk hand in hand." Such scientific disciplines as logic, philosophy describe them in the form of opposites.
From the point of view of the law of logic, 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 studied particulars of the whole: the larger the number studied, the more reliable the result. Based on this feature, the scientific laws obtained by induction are tested for a 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 provisions. This fact is important in connection with the specific scientific knowledge. This is clearly seen in the examples of induction in science.
There are two types of induction in the scientific world (in connection with the method of study):
- induction-selection (or selection);
- 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 causation 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.
The realization of the failure 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.
Induction receives a vote of confidence in practical application in certain subject areas and thanks to the metric accuracy of the inductive base. An example of induction and deduction in philosophy is the Law gravity. At the date of discovery of the law, Newton was able to verify it with an accuracy of 4 percent. And when checking after more than two hundred years, the correctness was confirmed with an accuracy of 0.0001 percent, although the check was carried out by the same inductive generalizations.
Modern philosophy pays more attention to deduction, which is dictated by a logical desire to derive new knowledge (or truth) from what is already known, without resorting to experience, intuition, but using “pure” reasoning. When referring to true premises in the deductive method, in all cases, the output is a true statement.
This very important characteristic should not overshadow the value of the inductive method. Since induction, based on the achievements of experience, also becomes a means of its processing (including generalization and systematization).
Application of induction in economics
Induction and deduction have long been used as methods of studying the economy and predicting its development.
The range of use of the induction method is quite wide: the study of the fulfillment of forecast indicators (profit, depreciation, etc.) and a general assessment of the state of the enterprise; formation of an effective enterprise promotion policy based on facts and their relationships.
The same method of induction is used in Shewhart's charts, where, under the assumption that processes are divided into controlled and unmanaged, it is stated that the framework of the controlled process is inactive.
It should be noted that scientific laws are justified and confirmed using the method of induction, and since economics is a science that often uses mathematical analysis, risk theory and statistical data, then it is not surprising that induction is included in the list of basic 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 more often they 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. There are many opportunities for comfortable living in the home environment. You can refuse all red items or replace them with analogues made in a different color scheme. But in public places, at work, in the store - it is impossible. Getting into a situation of stress, the patient each time experiences a “tide” of completely different emotional states which may pose a danger to others."
This example of induction, and unconsciously, is called "fixed ideas." If this happens to a mentally healthy person, we can talk about a lack of organization mental activity. The elementary development of deductive thinking can become a way to get rid of obsessive states. In other cases, psychiatrists work with such patients.
The above examples of induction indicate that "ignorance of the law does not exempt from the consequences (erroneous judgments)."
Psychologists, working on the topic of deductive thinking, have compiled a list of recommendations designed to help people master this method.
The first step is problem solving. As can be seen, the form of induction used in mathematics can be considered "classical", and the use of this method contributes to the "discipline" of the mind.
The next condition for the development of deductive thinking is the expansion of horizons (those who think clearly, clearly state). This recommendation directs the "suffering" to the treasuries of science and information (libraries, websites, educational initiatives, travel, etc.).
Separately, mention should be made of the so-called "psychological induction". This term, although infrequently, can be found on the Internet. All sources do not give at least a brief definition of this term, but refer to "examples from life", while presenting either suggestion, some forms of mental illness, or extreme states of the human psyche as a new type of induction. From all of the above, it is clear that an attempt to derive a “new term” based on false (often untrue) premises dooms the experimenter to receive an erroneous (or hasty) statement.
It should be noted that the reference to the experiments of 1960 (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 organs of perception (the phrase “experienced” in this case would fit in more organically), makes one think about the gullibility and uncriticality of the author of the statement.
Instead of a conclusion
The queen of sciences - mathematics, not in vain uses all possible reserves of the method of induction and deduction. The considered examples allow us to conclude that the superficial and inept (thoughtless, as they say) application of even the most accurate and reliable methods always leads to erroneous results.
In the mass consciousness, the deduction method is associated with the famous Sherlock Holmes, who in his logical constructions often uses examples of induction, in the right situations using deduction.
The article considered examples of the application of these methods in various sciences and spheres of human life.
Introduction
Main part
1. Complete and incomplete induction
2. The principle of mathematical induction
3. Method of mathematical induction
4. Solution of examples
5. Equalities
6. Division of numbers
7. Inequalities
Conclusion
List of used literature
Introduction
Deductive and inductive methods are the basis of any mathematical research. The deductive method of reasoning is reasoning from the general to the particular, i.e. reasoning that starts with overall result, and the final point is a partial result. Induction is applied when passing from particular results to general ones, i.e. is the opposite of the deductive method.
The method of mathematical induction can be compared to progress. We start from the lowest, as a result logical thinking we come to the highest. Man has always striven for progress, for the ability to develop his thought logically, which means that nature itself has destined him to think inductively.
Although the field of application of the method of mathematical induction has grown, in school curriculum he has little time. Well, say that a useful person will be brought by those two or three lessons for which he hears five words of theory, solves five primitive problems, and, as a result, gets a five for knowing nothing.
But this is so important - to be able to think inductively.
Main part
In its original meaning, the word "induction" is applied to reasoning by which general conclusions are obtained, based on a number of particular statements. The simplest method of reasoning of this kind is complete induction. Here is an example of such reasoning.
Let it be required to establish that every natural even number n within 4< n < 20 представимо в виде суммы двух prime numbers. To do this, we take all such numbers and write out the corresponding expansions:4=2+2; 6=3+3; 8=5+3; 10=7+3; 12=7+5;
14=7+7; 16=11+5; 18=13+5; 20=13+7.
These nine equalities show that each of the numbers of interest to us is indeed represented as the sum of two prime terms.
Thus, complete induction is that the general statement is proved separately in each of a finite number possible cases.
Sometimes the overall result can be predicted after considering not all, but enough a large number special cases (the so-called incomplete induction).
The result obtained by incomplete induction, however, remains only a hypothesis until it is proved by exact mathematical reasoning, covering all special cases. In other words, incomplete induction in mathematics is not considered a legitimate method of rigorous proof, but is a powerful method for discovering new truths.
Let, for example, it is required to find the sum of the first n consecutive odd numbers. Consider special cases:
1+3+5+7+9=25=5 2
After considering these few special cases, the following general conclusion suggests itself:
1+3+5+…+(2n-1)=n 2
those. the sum of the first n consecutive odd numbers is n 2
Of course, the observation made cannot yet serve as a proof of the validity of the above formula.
Complete induction has only limited applications in mathematics. Many interesting mathematical statements cover an infinite number of special cases, and to test for an infinite number cases we are unable to. Incomplete induction often leads to erroneous results.
In many cases, the way out of this kind of difficulty is to resort to a special method of reasoning, called the method of mathematical induction. It is as follows.
Let it be necessary to prove the validity of a certain statement for any natural number n (for example, it is necessary to prove that the sum of the first n odd numbers is equal to n 2). A direct verification of this statement for each value of n is impossible, since the set of natural numbers is infinite. To prove this statement, first check its validity for n=1. Then it is proved that for any natural value of k, the validity of the statement under consideration for n=k implies its validity for n=k+1 as well.
Then the assertion is considered proven for all n. Indeed, the statement is true for n=1. But then it is also valid for the next number n=1+1=2. The validity of the assertion for n=2 implies its validity for n=2+
1=3. This implies the validity of the statement for n=4, and so on. It is clear that, in the end, we will reach any natural number n. Hence, the statement is true for any n.
Summarizing what has been said, we formulate the following general principle.
The principle of mathematical induction.
If sentence A(n) depending on the natural numbern, true forn=1 and from the fact that it is true forn=k(wherek-any natural number), it follows that it is also true for the next numbern=k+1, then assumption A(n) is true for any natural numbern.
In a number of cases, it may be necessary to prove the validity of a certain statement not for all natural numbers, but only for n>p, where p is a fixed natural number. In this case, the principle of mathematical induction is formulated as follows. If sentence A(n) is true forn=pand if A(k) Þ BUT(k+1)for anyonek>p,then sentence A(n)true for anyonen>p.The proof by the method of mathematical induction is carried out as follows. First, the assertion to be proved is checked for n=1, i.e., the truth of the statement A(1) is established. This part of the proof is called the induction basis. This is followed by a part of the proof called the induction step. In this part, the validity of the statement for n=k+1 is proved under the assumption that the statement is true for n=k (the inductive assumption), i.e. prove that A(k)ÞA(k+1).
EXAMPLE 1
Prove that 1+3+5+…+(2n-1)=n 2 .
Solution: 1) We have n=1=1 2 . Consequently,
the statement is true for n=1, i.e. A(1) is true.
2) Let us prove that A(k)ÞA(k+1).
Let k be any natural number and let the statement be true for n=k, i.e.
1+3+5+…+(2k-1)=k 2 .
Let us prove that then the assertion is also true for the next natural number n=k+1, i.e. what
1+3+5+…+(2k+1)=(k+1) 2 .
Indeed,
1+3+5+…+(2k-1)+(2k+1)=k 2 +2k+1=(k+1) 2 .
So A(k)ÞA(k+1). Based on the principle of mathematical induction, we conclude that Assumption A(n) is true for any nОN.
EXAMPLE 2
Prove that
1+x+x 2 +x 3 +…+x n =(x n+1 -1)/(x-1), where x¹1
Solution: 1) For n=1 we get
1+x=(x 2 -1)/(x-1)=(x-1)(x+1)/(x-1)=x+1
therefore, for n=1 the formula is true; A(1) is true.
2) Let k be any natural number and let the formula be true for n=k, i.e.
1 + x + x 2 + x 3 + ... + x k \u003d (x k + 1 -1) / (x-1).
Let us prove that then the equality
1+x+x 2 +x 3 +…+x k +x k+1 =(x k+2 -1)/(x-1).
Indeed
1+х+х 2 +x 3 +…+х k +x k+1 =(1+x+x 2 +x 3 +…+x k)+x k+1 =
=(x k+1 -1)/(x-1)+x k+1 =(x k+2 -1)/(x-1).
So A(k)ÞA(k+1). Based on the principle of mathematical induction, we conclude that the formula is true for any natural number n.
EXAMPLE 3
Prove that the number of diagonals of a convex n-gon is n(n-3)/2.
Solution: 1) For n=3, the statement is true
And 3 is correct, because in a triangle A 3 =3(3-3)/2=0 diagonals;
A 2 A(3) is true.
2) Suppose that in any
convex k-gon has-
A 1 sya A k \u003d k (k-3) / 2 diagonals.
A k Let us prove that then in a convex
(k+1)-gon number
diagonals A k+1 =(k+1)(k-2)/2.
Let А 1 А 2 А 3 …A k A k+1 -convex (k+1)-angle. Let's draw a diagonal A 1 A k in it. To count 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.
In this way,
k+1 = k +(k-2)+1=k(k-3)/2+k-1=(k+1)(k-2)/2.
So A(k)ÞA(k+1). Due to the principle of mathematical induction, the statement is true for any convex n-gon.
EXAMPLE 4
Prove that for any n the statement is true:
1 2 +2 2 +3 2 +…+n 2 =n(n+1)(2n+1)/6.
Solution: 1) Let n=1, then
X 1 \u003d 1 2 \u003d 1 (1 + 1) (2 + 1) / 6 \u003d 1.
Hence, for n=1 the statement is true.
2) Assume that n=k
X k \u003d k 2 \u003d k (k + 1) (2k + 1) / 6.
3) Consider this statement for n=k+1
Xk+1 =(k+1)(k+2)(2k+3)/6.
X k+1 =1 2 +2 2 +3 2 +…+k 2 +(k+1) 2 =k(k+1)(2k+1)/6+ +(k+1) 2 =(k (k+1)(2k+1)+6(k+1) 2)/6=(k+1)(k(2k+1)+
6(k+1))/6=(k+1)(2k 2 +7k+6)/6=(k+1)(2(k+3/2)(k+
2))/6=(k+1)(k+2)(2k+3)/6.
We have proved the validity of the equality for n=k+1, therefore, by virtue of the method of mathematical induction, the statement is true for any natural n.
EXAMPLE 5
Prove that for any natural n the equality is true:
1 3 +2 3 +3 3 +…+n 3 =n 2 (n+1) 2 /4.
Solution: 1) Let n=1.
Then X 1 =1 3 =1 2 (1+1) 2 /4=1.
We see that for n=1 the statement is true.
2) Assume that the equality is true for n=k
One of the most important methods of mathematical proof is rightly method of mathematical induction. The vast majority of formulas relating to all natural numbers n can be proved by mathematical induction (for example, the formula for the sum of the first n terms arithmetic progression, Newton's binomial formula, etc.).
In this article, we will first dwell on the basic concepts, then consider the method of mathematical induction itself and analyze examples of its application in proving equalities and inequalities.
Page navigation.
Induction and deduction.
by induction called the transition from particular to general statements. On the contrary, the transition from general statements to particular ones is called deduction.
An example of a private statement: 254 is divisible by 2 without a remainder.
From this particular statement, one can formulate a lot of more general statements, both true and false. For example, the more general statement that all integers ending in 4 are divisible by 2 without remainder is true, while the statement that all three-digit numbers are divisible by 2 without remainder is false.
Thus, induction makes it possible to obtain many general statements based on known or obvious facts. And the method of mathematical induction is designed to determine the validity of the statements received.
As an example, consider the numeric sequence: , n is an arbitrary natural number. Then the sequence of sums of the first n elements of this sequence will be the following
Based on this fact, by induction it can be argued that .
We present the proof of this formula.
Method of mathematical induction.
The method of mathematical induction is based on principle of mathematical induction.
It consists in the following: a certain statement is true for any natural n if
- it is valid for n = 1 and
- from the validity of the statement for any arbitrary natural n = k it follows that it is true for n = k+1 .
That is, the proof by the method of mathematical induction is carried out in three stages:
- firstly, the validity of the statement is checked for any natural number n (usually the check is done for n = 1 );
- secondly, the validity of the statement is assumed for any natural n=k ;
- thirdly, the validity of the statement for the number n=k+1 is proved, starting from the assumption of the second point.
Examples of proofs of equations and inequalities by the method of mathematical induction.
Let's go back to the previous example and prove the formula .
Proof.
The method of mathematical induction involves a three-point proof.
Thus, all three steps of the method of mathematical induction have been completed, and thus our assumption about the formula has been proved.
Let's look at the trigonometric problem.
Example.
Prove Identity .
Solution.
First, we check the equality for n = 1 . To do this, we need the basic formulas of trigonometry.
That is, the equality is true for n = 1 .
Secondly, suppose that the equality is true for n = k , that is, the identity
Third, we turn to the proof of the equality for n = k+1 , based on the second point.
Since according to the formula from trigonometry
then
The proof of the equality from the third point is completed, therefore, the original identity is proved by the method of mathematical induction.
Can be proven by mathematical induction.
An example of proving the inequality by mathematical induction can be found in the section on the method of least squares when deriving formulas for finding approximation coefficients.
Bibliography.
- Sominsky I.S., Golovina L.I., Yaglom I.M. On mathematical induction.
If the sentence A(n), which depends on a natural number n, is true for n=1, and from the fact that it is true for n=k (where k is any natural number), it follows that it is also true for the next number n=k +1, then Assumption A(n) is true for any natural number n.
In a number of cases, it may be necessary to prove the validity of a certain statement not for all natural numbers, but only for n>p, where p is a fixed natural number. In this case, the principle of mathematical induction is formulated as follows.
If 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 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, 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 a 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 positive number 1+x, we get
(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, by virtue of 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.
By virtue of 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.
- The displacement is called the vector connecting the start and end points of the trajectory The vector connecting the beginning and end of the path is called
- Trajectory, path length, displacement vector Vector connecting the initial position
- Calculating the area of a polygon from the coordinates of its vertices The area of a triangle from the coordinates of the vertices formula
- Acceptable Value Range (ODZ), theory, examples, solutions