Method mathematical induction
Introduction
Main part
- Full and not full induction
- Principle of mathematical induction
- Method of mathematical induction
- Solving Examples
- Equalities
- Dividing numbers
- Inequalities
Conclusion
List of used literature
Introduction
The basis of any mathematical research is deductive and inductive methods. The deductive method of reasoning is reasoning from the general to the specific, i.e. reasoning, the starting point of which is overall result, and the final point is a particular result. Induction is used when moving from particular results to general ones, i.e. is the opposite of deductive method.
The method of mathematical induction can be compared to progress. We start from the bottom, as a result logical thinking we come to the highest. Man has always strived for progress, for the ability to develop his thoughts logically, which means that nature itself destined him to think inductively.
Although the scope of application of the method of mathematical induction has grown, little time is devoted to it in the school curriculum. Well, say what useful to a person will bring those two or three lessons, during which he will hear five words of theory, solve five primitive problems, and, as a result, will receive an A for the fact that he knows nothing.
But it is so important to be able to think inductively.
Main part
In its original meaning, the word “induction” is applied to reasoning through which general conclusions are obtained based on a number of specific statements. The simplest method of reasoning of this kind is complete induction. Here is an example of such reasoning.
Let it be necessary to establish that every even natural number n within 4< n < 20 представимо в виде суммы двух простых чисел. Для этого возьмём все такие числа и выпишем соответствующие разложения:
4=2+2; 6=3+3; 8=5+3; 10=7+3; 12=7+5;
14=7+7; 16=11+5; 18=13+5; 20=13+7.
These nine equalities show that each of the numbers we are interested in is indeed represented as the sum of two simple terms.
Thus, complete induction consists of proving the general statement separately in each of a finite number of possible cases.
Sometimes the general result can be predicted after considering not all, but a sufficiently large number of particular cases (the so-called incomplete induction).
The result obtained by incomplete induction remains, however, only a hypothesis until it is proven by precise 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, you want to find the sum of the first n consecutive odd numbers. Let's 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 proof of the validity of the given formula.
Complete induction has only limited applications in mathematics. Many interesting mathematical statements cover an infinite number of special cases, but we are not able to test them for an infinite number of cases. Incomplete induction often leads to erroneous results.
In many cases, the way out of this kind of difficulty is to resort to a special method of reasoning, called the method of mathematical induction. It is as follows.
Suppose we need to prove the validity of a certain statement for any natural number n (for example, you need to prove that the sum of the first n odd numbers is equal to n 2). 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 they prove that for any natural value of k, the validity of the statement under consideration for n=k implies its validity for n=k+1.
Then the statement is considered proven for all n. In fact, the statement is true for n=1. But then it is also true for next date n=1+1=2. The validity of the statement for n=2 implies its validity for n=2+
1=3. This implies the validity of the statement for n=4, etc. It is clear that, in the end, we will reach any natural number n. This means that the statement is true for any n.
Summarizing what has been said, we formulate the following general principle.
The principle of mathematical induction.
If a sentence A(n), depending on a natural number n, is true for n=1 and from the fact that it is true for n=k (where k is any natural number), it follows that it is also true for the next number n=k +1, then assumption A(n) is true for any natural number n.
In a number of cases, it may be necessary to prove the validity of a certain statement not for all natural numbers, but only for n>p, where p is a fixed natural number. In this case, the principle of mathematical induction is formulated as follows.
If the proposition A(n) is true for n=p and if A(k)ÞA(k+1) for any k>p, then the proposition A(n) is true for any n>p.
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)ÞA(k+1).
Prove that 1+3+5+…+(2n-1)=n 2.
Solution: 1) We have n=1=1 2 . Hence,
the statement is true for n=1, i.e. A(1) is true.
2) Let us prove that A(k)ÞA(k+1).
Let k be any natural number and let the statement be true for n=k, i.e.
1+3+5+…+(2k-1)=k 2 .
Let us prove that then the statement is also true for the next natural number n=k+1, i.e. What
1+3+5+…+(2k+1)=(k+1) 2 .
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.
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 correct; 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 =(x k+1 -1)/(x-1).
Let us prove that then the equality
1+x+x 2 +x 3 +…+x k +x k+1 =(x k+2 -1)/(x-1).
Indeed
1+x+x 2 +x 3 +…+x k +x k+1 =(1+x+x 2 +x 3 +…+x k)+x k+1 =
=(x k+1 -1)/(x-1)+x k+1 =(x k+2 -1)/(x-1).
So, A(k)Þ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 equal to n(n-3)/2.
Solution: 1) For n=3 the statement is true
And 3 is meaningful, because in a triangle
A 3 =3(3-3)/2=0 diagonals;
A 2 A(3) is true.
2) Let us assume that in every
a convex k-gon has-
A 1 x A k =k(k-3)/2 diagonals.
And k Let us prove that then in a convex
(k+1)-gon number
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,
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.
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.
This means that for n=1 the statement is true.
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),
those. 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 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 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 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 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, 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)ÞA(k+1). By virtue of the method of mathematical induction, the statement has been proven.
Prove that for any n 7 n -1 is divisible by 6 without a remainder.
Solution: 1) Let n=1, then X 1 =7 1 -1=6 is divided by 6 without a remainder. This means that when n=1 the statement is true.
2) Suppose that for n=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 =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 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 n is divisible by 11.
Solution: 1) Let n=1, then
X 1 =3 3-1 +2 4-3 =3 2 +2 1 =11 is divided by 11 without a remainder. This means that for n=1 the statement is true.
2) Suppose that for n=k
X k =3 3k-1 +2 4k-3 is divisible by 11 without a remainder.
3) Let us prove that the statement is true for n=k+1.
X k+1 =3 3(k+1)-1 +2 4(k+1)-3 =3 3k+2 +2 4k+1 =3 3´ 3 3k-1 +2 4´ 2 4k-3 =
27´3 3k-1 +16´2 4k-3 =(16+11)´3 3k-1 +16´2 4k-3 =16´3 3k-1 +
11´3 3k-1 +16´2 4k-3 =16(3 3k-1 +2 4k-3)+11´3 3k-1 .
The first term is divisible by 11 without a remainder, since 3 3k-1 +2 4k-3 is divisible by 11 by assumption, the second is divisible by 11, because one of its factors is the number 11. This means that the sum is divisible by 11 without 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 n is divisible by 6 without a remainder.
Solution: 1) Let n=1, then 11 2 -1=120 is divisible by 6 without a remainder. This means that when n=1 the statement is true.
2) Suppose that for n=k
11 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, the number 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.
Solution: First we prove that 3 3n+3 -1 is divisible by 26 without a remainder.
- When n=0
- Let's assume that for n=k
- Let us prove that the statement
3 3 -1=26 is divided by 26
3 3k+3 -1 is divisible by 26
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 carry out the proof of the statement formulated in the problem statement.
1) Obviously, when 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 is true
(1+x) n >1+n´x.
Solution: 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).
Let us consider the right-hand side of the last inequality
stva; 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)ÞA(k+1). Based on the principle of mathematical induction, it can be argued that Bernoulli’s inequality is true for any
Prove that the inequality is true
(1+a+a 2) m > 1+m´a+(m(m+1)/2)´a 2 for a> 0.
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 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 is true
3 n >n´2 n+1 .
Solution: Let's rewrite the inequality in the form
- For n=7 we have
- Let's assume that for n=k
3 7 /2 7 =2187/128>14=2´7
the inequality is true.
3) Let us prove the validity of 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).
Solution: 1) For n=3 the inequality is true
1+(1/2 2)+(1/3 2)=245/180<246/180=1,7-(1/3).
- Let's assume 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 non-
equality for n=k+1
(1+(1/2 2)+…+(1/k 2))+(1/(k+1) 2)<1,7-(1/k)+(1/(k+1) 2).
Let us prove that 1.7-(1/k)+(1/(k+1) 2)<1,7-(1/k+1)Û
Û(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. Conclusion In particular, by studying the method of mathematical induction, I increased my knowledge in this area of mathematics, and also learned to solve problems that were previously beyond my power. These were mainly logical and entertaining tasks, i.e. just those that increase interest in mathematics itself as a science. Solving such problems becomes an entertaining activity and can attract more and more curious people into mathematical labyrinths. In my opinion, this is the basis of any science. Continuing to study the method of mathematical induction, I will try to learn how to apply it not only in mathematics, but also in solving problems in physics, chemistry and life itself. MATHEMATICS: LECTURES, PROBLEMS, SOLUTIONS Tutorial/ V.G.Boltyansky, Yu.V.Sidorov, M.I.Shabunin. Potpourri LLC 1996. ALGEBRA AND BEGINNINGS OF ANALYSIS Textbook / I.T. Demidov, A.N. Kolmogorov, S.I. Shvartsburg, O.S. Ivashev-Musatov, B.E. Weitz. “Enlightenment” 1975. 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. 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. The full form is characterized by 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 that are functionally connected by the relations of a natural series of numbers based on knowledge of this functional connection. In this case, the proof process takes place in three stages: 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: A striking example of the method of mathematical induction is the “Dimensionless flight” problem: 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 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). The result is a map correctly colored in two colors, which is what needed to be proven. 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. 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. 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. The induction method requires a scrupulous attitude, since too much depends on the number of parts of the whole studied: the greater the 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 influences. In science, an inductive conclusion is based on significant features, with the exception of random provisions. This fact is important in connection with the specifics of 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): 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. 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. Induction receives a vote of confidence through practical application in certain subject areas and thanks to the metric accuracy of the inductive basis. An example of induction and deduction in philosophy can be considered the Law of Universal Gravitation. 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 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 processing it (including generalization and systematization). 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, from the fact of high prices, using 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 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 example is a colorful illustration of how inept use of the induction method contributes to the ruin of an enterprise. 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 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 deceiving, therefore, all women are deceivers. You can glean even more “erroneous” examples of induction from life: And many other value judgments based on completely random and, at times, insignificant premises. 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 scheme. But in public places, at work, in a store - it is impossible. When a patient finds himself in a stressful situation, each time he experiences a “tide” of completely different emotional states, which can 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 can be the 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 treasuries 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 off as a new type of induction either suggestion, or some forms of mental illness, or extreme states of the human psyche. From all of the above, it is clear that an attempt to 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. 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 the mass consciousness, the method of deduction is associated with the famous Sherlock Holmes, who in his logical constructions more often uses examples of induction, using deduction in the right situations. The article examined examples of the application of these methods in various sciences and spheres of human activity. The text of the work is posted without images and formulas. Introduction This topic is relevant, since every day people solve various problems in which they use different solution methods, but there are tasks in which one cannot do without the method of mathematical induction, and in such cases knowledge in this area will be very useful. I chose this topic for research because little time is devoted to the method of mathematical induction in the school curriculum; the student learns superficial information that will help him get only a general idea of this method, but in order to study this theory in depth, self-development will be required. It will really be useful to learn more about this topic, as it broadens a person’s horizons and helps in solving complex problems. Goal of the work:
Get acquainted with the method of mathematical induction, systematize knowledge on this topic and apply it when solving mathematical problems and proving theorems, justify and clearly show the practical significance of the method of mathematical induction as a necessary factor for solving problems. Job objectives:
Analyze the literature and summarize knowledge on this topic. Understand the principle of the method of mathematical induction. Explore the application of the method of mathematical induction to problem solving. Formulate conclusions and conclusions about the work done. Main part of the study History:
Only towards the end of the 19th century did a standard of requirements for logical rigor emerge, which remain dominant to this day in the practical work of mathematicians on the development of individual mathematical theories. Induction is a cognitive procedure through which a statement generalizing them is derived from a comparison of existing facts. In mathematics, the role of induction is largely that it underlies the chosen axiomatics. After long-term practice showed that a straight path is always shorter than a curved or broken one, it was natural to formulate an axiom: for any three points A, B and C, an inequality holds. The awareness of the method of mathematical induction as a separate important method goes back to Blaise Pascal and Gersonides, although individual cases of application are found in ancient times in Proclus and Euclid. The modern name for the method was introduced by De Morgan in 1838. The method of mathematical induction can be compared to progress: we start from the lowest, and as a result of logical thinking we come to the highest. Man has always strived for progress, for the ability to logically develop his thoughts, which means that nature itself destined him to think inductively. Induction and deduction
It is known that there are both particular and general statements, and these two terms are based on the transition from one to the other. Deduction (from Latin deductio - deduction) - a transition in the process of cognition from general knowledge to private And single. In deduction, general knowledge serves as the starting point of reasoning, and this general knowledge is assumed to be “ready-made,” existing. The peculiarity of deduction is that the truth of its premises guarantees the truth of the conclusion. Therefore, deduction has enormous persuasive power and is widely used not only to prove theorems in mathematics, but also wherever reliable knowledge is needed. Induction (from Latin inductio - guidance) is a transition in the process of cognition from private knowledge to general In other words, it is a method of research and cognition associated with generalizing the results of observations and experiments. A feature of induction is its probabilistic nature, i.e. If the initial premises are true, the conclusion of induction is only probably true and in the final result it can turn out to be either true or false. Complete and incomplete induction
Inductive inference is a form of abstract thinking in which thought develops from knowledge of a lesser degree of generality to knowledge of a greater degree of generality, and the conclusion arising from the premises is predominantly probabilistic in nature. During the research, I found out that induction is divided into two types: complete and incomplete. Complete induction is an inference in which a general conclusion about a class of objects is made based on the study of all objects of this class. For example, let it be necessary to establish that every even natural number n within the range 6≤ n≤ 18 can be represented as the sum of two prime numbers. To do this, take all such numbers and write out the corresponding expansions: 6=3+3; 8=5+3; 10=7+3; 12=7+5;14=7+7; 16=11+5; 18=13+5; These equalities show that each of the numbers we are interested in is indeed represented as the sum of two simple terms. Consider the following example: sequence yn= n 2 +n+17; Let's write out the first four terms: y 1 =19; y 2 =23; y 3 =29; y 4 =37; Then we can assume that the entire sequence consists of prime numbers. But this is not so, let's take y 16 = 16 2 +16+17=16(16+1)+17=17*17. This is a composite number, which means our assumption is incorrect, thus, incomplete induction does not lead to completely reliable conclusions, but allows us to formulate a hypothesis, which subsequently requires mathematical proof or refutation. Method of mathematical induction
Complete induction has only limited applications in mathematics. Many interesting mathematical statements cover an infinite number of special cases, and we are not able to test for all these situations. But how can we test for an infinite number of cases? This method was proposed by B. Pascal and J. Bernoulli, this is a method of mathematical induction, which is based on principle of mathematical induction. If a sentence A(n), depending on a natural number n, is true for n=1 and from the fact that it is true for n=k (where k is any natural number), it follows that it is also true for the next number n=k +1, then assumption A(n) is true for any natural number n. In a number of cases, it may be necessary to prove the validity of a certain statement not for all natural numbers, but only for n>p, where p is a fixed natural number. In this case, the principle of mathematical induction is formulated as follows: If the proposition A(n) is true for n=p and if A(k)
A(k+1) for any k>p, then the proposition A(n) is true for any n>p. Algorithm (it consists of four stages):
1.base(we show that the statement being proved is true for some simplest special cases ( P
= 1)); 2.assumption(we assume that the statement has been proven for the first To
cases); 3
.step(under this assumption we prove the statement for the case P
=
To
+ 1); 4.output (at the statement is true for all cases, that is, for all P)
. Note that the method of mathematical induction can not solve all problems, but only problems parameterized by a certain variable. This variable is called the induction variable. Application of the method of mathematical induction
Let's apply this entire theory in practice and find out in what problems this method is used. Problems to prove inequalities.
Example 1. Prove Bernoulli's inequality(1+x)n≥1+n x, x>-1, n € N. 1) For n=1 the inequality is true, since 1+x≥1+x 2) Suppose that the inequality is true for some n=k, i.e. (1+x) k ≥1+k x. Multiplying both sides of the inequality by a positive number 1+x, we get (1+x) k+1 ≥(1+kx)(1+ x) =1+(k+1) x + kx 2 Taking into account that kx 2 ≥0, we arrive at the inequality (1+x) k+1 ≥1+(k+1) x. Thus, from the assumption that Bernoulli's inequality is true for n=k, it follows that it is true for n=k+1. Based on the method of mathematical induction, it can be argued that Bernoulli’s inequality is valid for any n € N. Example 2. Prove that for any natural number n>1, . Let's prove it using the method of mathematical induction. Let us denote the left side of the inequality by. 1), therefore, for n=2 the inequality is valid. 2) Let for some k. Let us prove that then and. We have, . Comparing and, we have, i.e. . For any positive integer k, the right-hand side of the last equality is positive. That's why. But that means and. We have proven the validity of the inequality for n=k+1, therefore, by virtue of the method of mathematical induction, the inequality is valid for any natural number n>1. Problems to prove identities.
Example 1. Prove that for any natural number n the equality is true: 1 3 +2 3 +3 3 +…+n 3 =n 2 (n+1) 2 /4. Let n=1, then X 1 =1 3 =1 2 (1+1) 2 /4=1. We see that for n=1 the statement is true. 2) Suppose that the equality is true for n=kX k =k 2 (k+1) 2 /4. 3) Let us prove the truth of this statement for n=k+1, i.e. X k+1 =(k+1) 2 (k+2) 2 /4. X k+1 =1 3 +2 3 +…+k 3 +(k+1) 3 =k 2 (k+1) 2 /4+(k+1) 3 =(k 2 (k+1) 2 +4(k+1) 3)/4=(k+1) 2 (k 2 +4k+4)/4=(k+1) 2 (k+2) 2 /4. From the above proof it is clear that the statement is true for n=k+1, therefore, the equality is true for any natural number n. Example 2. Prove that for any natural n the equality is true 1) Let us check that this identity is true for n = 1.; - right. 2) Let the identity also be true for n = k, i.e.. 3) Let us prove that this identity is also true for n = k + 1, i.e.; Because If the equality is true for n=k and n=k+1, then it is true for any natural number n. Summation problems.
Example 1. Prove that 1+3+5+…+(2n-1)=n 2. Solution: 1) We have n=1=1 2 . Therefore, the statement is true for n=1, i.e. A(1) is true. 2) Let us prove that A(k) A(k+1). Let k be any natural number and let the statement be true for n=k, i.e. 1+3+5+…+(2k-1)=k 2 . Let us prove that then the statement is also true for the next natural number n=k+1, i.e. What 1+3+5+…+(2k+1)=(k+1) 2 . In fact, 1+3+5+…+(2k-1)+(2k+1)=k 2 +2k+1=(k+1) 2 . So, A(k) A(k+1). Based on the principle of mathematical induction, we conclude that assumption A(n) is true for any n N. Example 2. Prove the formula, n is a natural number. Solution: When n=1, both sides of the equality turn to one and, therefore, the first condition of the principle of mathematical induction is satisfied. Let's assume that the formula is correct for n=k, i.e. . Let's add to both sides of this equality and transform the right side. Then we get Thus, from the fact that the formula is true for n=k, it follows that it is also true for n=k+1, then this statement is true for any natural number n. Divisibility problems.
Example 1. Prove that (11 n+2 +12 2n+1) is divisible by 133 without a remainder. Solution:
1) Let n=1, then 11 3 +12 3 =(11+12)(11 2 -132+12 2)=23× 133. (23×133) is divisible by 133 without a remainder, which means that for n=1 the statement is true; 2) Suppose that (11 k+2 +12 2k+1) is divisible by 133 without a remainder. 3) Let us prove that in this case (11 k+3 +12 2k+3) is divisible by 133 without a remainder. Indeed, 11 k+3 +12 2l+3 =11×11 k+2 + 12 2 ×12 2k+1 =11× 11 k+2 +(11+133)× 12 2k+1 =11(11 k+2 +12 2k+1)+133× 12 2k+1 . The resulting sum is divided by 133 without a remainder, since its first term is divisible by 133 without a remainder by assumption, and in the second one of the factors is 133. So, A(k)→ A(k+1), then based on the method of mathematical induction, the statement is true for any natural n. Example 2. Prove that 3 3n-1 +2 4n-3 for an arbitrary natural number n is divisible by 11. Solution: 1) Let n=1, then X 1 =3 3-1 +2 4-3 =3 2 +2 1 =11 is divisible by 11 without a remainder. This means that for n=1 the statement is true. 2) Suppose that for n=k X k =3 3k-1 +2 4k-3 is divisible by 11 without a remainder. 3) Let us prove that the statement is true for n=k+1. X k+1 =3 3(k+1)-1 +2 4(k+1)-3 =3 3k+2 +2 4k+1 =3 3 *3 3k-1 +2 4 *2 4k-3 = 27 3 3k-1 +16* 2 4k-3 =(16+11)* 3 3k-1 +16* 2 4k-3 =16* 3 3k-1 + 11* 3 3k-1 +16* 2 4k-3 =16(3 3k-1 +2 4k-3)+11* 3 3k-1 . The first term is divisible by 11 without a remainder, since 3 3k-1 +2 4k-3 is divisible by 11 by assumption, the second is divisible by 11, because one of its factors is the number 11. This means that the sum is divisible by 11 without a remainder for any natural number n. Problems from real life.
Example 1. Prove that the sum Sn of interior angles of any convex polygon is equal to ( P- 2)π, where P— the number of sides of this polygon: Sn = ( P- 2)π (1). This statement does not make sense for all natural P, but only for P >
3, since the minimum number of angles in a triangle is 3. 1) When P= 3 our statement takes the form: S 3 = π. But the sum of the interior angles of any triangle is indeed π. Therefore, when P= 3 formula (1) is correct. 2) Let this formula be true for n =k, that is S k
= (k- 2)π, where k >
3. Let us prove that in this case the formula holds: S k+
1 = (k- 1)π. Let A 1 A 2 ... A k
A k+
1—arbitrary convex ( k+ 1) -gon (Fig. 338). Connecting points A 1 and A k
, we get convex k-gon A 1 A 2 ... A k
— 1 A k
. Obviously, the sum of the angles ( k+ 1) -gon A 1 A 2 ... A k
A k+
1 is equal to the sum of the angles k-gon A 1 A 2 ... A k
plus the sum of the angles of a triangle A 1 A k
A k+
1 . But the sum of the angles k-gon A 1 A 2 ... A k
by assumption equal to ( k- 2)π, and the sum of the angles of the triangle A 1 A k
A k+
1 is equal to π. That's why S k+
1 = S k
+ π = ( k- 2)π + π = ( k- 1)π. So, both conditions of the principle of mathematical induction are satisfied, and therefore formula (1) is true for any natural P >
3. Example 2. There is a staircase, all steps of which are the same. It is required to indicate the minimum number of positions that would guarantee the ability to “climb” onto any step by number. Everyone agrees that there must be a condition. We must be able to climb to the first step. Next, they must be able to climb from the 1st step to the second. Then to the second - to the third, etc. to the nth step. Of course, in totality, “n” statements guarantee that we will be able to get to the nth step. Let's now look at the 2, 3,..., n position and compare them with each other. It is easy to see that they all have the same structure: if we have reached the k step, then we can climb up to the (k+1) step. Hence, the following axiom becomes natural for the validity of statements depending on “n”: if a sentence A(n), in which n is a natural number, holds for n=1 and from the fact that it holds for n=k (where k is any natural number), it follows that it holds for n=k+1, then assumption A(n) holds for any natural number n. Application Problems using the method of mathematical induction when entering universities.
Note that upon admission to higher education educational establishments There are also problems that can be solved by this method. Let's look at them using specific examples. Example 1. Prove that any natural P equality is true 1) When n=1 we get the correct equality Sin. 2) Having made the induction assumption that when n= k the equality is true, consider the sum on the left side of the equality for n =k+1; 3) Using reduction formulas, we transform the expression: Then, by virtue of the method of mathematical induction, the equality is true for any natural number n. Example 2. Prove that for any natural number n the value of the expression 4n +15n-1 is a multiple of 9. 1) With n=1: 2 2 +15-1=18 - a multiple of 9 (since 18:9=2) 2) Let the equality hold for n=k: 4 k +15k-1 multiple of 9. 3) Let us prove that the equality holds for the next number n=k+1 4 k+1 +15(k+1)-1=4 k+1 +15k+15-1=4.4 k +60k-4-45k+18=4(4 k +15k-1)-9(5k- 2) 4(4 k +15k-1) - multiple of 9; 9(5k-2) - multiple of 9; Consequently, the entire expression 4(4 k +15k-1)-9(5k-2) is a multiple of 9, which is what needed to be proven. Example 3. Prove that for any natural number P the condition is met: 1∙2∙3+2∙3∙4+…+ p(p+1)(p+2)=. 1) Let's check that this formula is correct when n=1: Left side = 1∙2∙3=6.
Right part = .
6 = 6; true when n=1. 2) Suppose that this formula is true for n =k: 1∙2∙3+2∙3∙4+…+k(k+1)(k+2)=. S k =.
3) Let us prove that this formula is true for n =k+1: 1∙2∙3+2∙3∙4+…+(k+1)(k+2)(k+3)=. S k+1 =.
Proof: So, this condition true in two cases and proven to be true for n =k+1, therefore it is true for any natural number P. Conclusion To summarize, in the process of research I found out what induction is, which can be complete or incomplete, got acquainted with the method of mathematical induction based on the principle of mathematical induction, and considered many problems using this method. I also learned a lot of new information, different from what is included in the school curriculum. While studying the method of mathematical induction, I used various literature, Internet resources, and also consulted with a teacher. Conclusion:
Having generalized and systematized knowledge on mathematical induction, I became convinced of the need for knowledge on this topic in reality. Positive quality The method of mathematical induction is its wide application in solving problems: in the field of algebra, geometry and real mathematics. This knowledge also increases interest in mathematics as a science. I am confident that the skills I acquired during my work will help me in the future.
Bibliography Sominsky I.S. Method of mathematical induction. Popular lectures on mathematics, issue 3-M.: Science, 1974. L. I. Golovina, I. M. Yaglom. Induction in geometry. - Fizmatgiz, 1961. - T. 21. - 100 p. — (Popular lectures on mathematics). Dorofeev G.V., Potapov M.K., Rozov N.Kh. A manual on mathematics for applicants to universities (Selected questions elementary mathematics) - 5th edition, revised, 1976 - 638 p. A. Shen. Mathematical induction. - MCNMO, 2004. - 36 p. M.L. Galitsky, A.M. Goldman, L.I. Zvavich Collection of problems in algebra: textbook for grades 8-9. with depth studying mathematics 7th ed. - M.: Prosveshchenie, 2001. - 271 p. Ma-ka-ry-chev Yu.N., Min-dyuk N.G Additional chapters for the school textbook of al-geb-ry 9th grade. - M.: Pro-sve-shche-nie, 2002. Wikipedia is a free encyclopedia. Savelyeva Ekaterina The paper discusses the application of the method of mathematical induction in solving divisibility problems and summing series. Examples of applying the method of mathematical induction to proving inequalities and solving geometric problems are considered. The work is illustrated with a presentation. Ministry of Science and Education of the Russian Federation State educational institution average comprehensive school № 618
Course: algebra and beginnings of analysis Topic of project work “The method of mathematical induction and its application to problem solving” Work completed: Savelyeva E, 11B class Supervisor : Makarova T.P., mathematics teacher, secondary school No. 618 1. Introduction. 2.Method of mathematical induction in solving divisibility problems. 3. Application of the method of mathematical induction to the summation of series. 4. Examples of applying the method of mathematical induction to the proof of inequalities. 5. Application of the method of mathematical induction to solving geometric problems. 6. List of used literature. Introduction The basis of any mathematical research is deductive and inductive methods. The deductive method of reasoning is reasoning from the general to the specific, i.e. reasoning, the starting point of which is the general result, and the final point is the particular result. Induction is used when moving from particular results to general ones, i.e. is the opposite of deductive method. The method of mathematical induction can be compared to progress. We start from the lowest, and as a result of logical thinking we come to the highest. Man has always strived for progress, for the ability to develop his thoughts logically, which means that nature itself destined him to think inductively. Although the scope of application of the method of mathematical induction has grown, little time is devoted to it in the school curriculum. But it is so important to be able to think inductively. The application of this principle in solving problems and proving theorems is on a par with the consideration in school practice of other mathematical principles: excluded middle, inclusion-exclusion, Dirichlet, etc. This abstract contains problems from different branches of mathematics, in which the main tool is the use method of mathematical induction. Speaking about the importance of this method, A.N. Kolmogorov noted that “understanding and ability to apply the principle of mathematical induction is good criterion maturity, which is absolutely necessary for a mathematician.” The method of induction in its broad sense consists in the transition from particular observations to a universal, general pattern or general formulation. In this interpretation, the method is, of course, the main method of conducting research in any experimental natural science. human activity. The method (principle) of mathematical induction in its simplest form is used when it is necessary to prove a certain statement for all natural numbers. Task 1. In his article “How I became a mathematician” A.N. Kolmogorov writes: “I learned the joy of a mathematical “discovery” early, having noticed a pattern at the age of five or six 1 =1
2
,
1 + 3 = 2
2
,
1 + 3 + 5 = 3 2, 1 + 3 + 5 + 7 = 4 2 and so on. The school published the magazine "Spring Swallows". In it my discovery was published...” We don’t know what kind of evidence was given in this journal, but it all started with private observations. The hypothesis itself, which probably arose after the discovery of these partial equalities, is that the formula 1 + 3 + 5 + ... + (2n - 1) = n 2 true for any given number n = 1, 2, 3, ... To prove this hypothesis, it is enough to establish two facts. Firstly, for n = 1 (and even for n = 2, 3, 4) the desired statement is true. Secondly, suppose that the statement is true for p = k, and we will make sure that then it is also true for n = k + 1: 1 + 3 + 5+…+ (2k - 1) + (2k + 1) = (1 + 3 + 5 + ... + (2k - 1)) + (2k + 1) = k 2 + (2k + 1) = (k + I) 2. This means that the statement being proved is true for all values n: for n = 1 it is true (this has been verified), and due to the second fact - for n = 2, whence for n = 3 (due to the same, second fact), etc. Task 2. Consider all possible common fractions with numerator 1 and any (positive integer) (nominal) denominator: Prove that for any p> 3 we can represent the unit as a sum P various fractions of this type. Solution, Let us first check this statement for n = 3; we have: Therefore, the basic statement is satisfied Let us now assume that the statement we are interested in is true for some number To, and prove that it is also true for the number following it To + 1. In other words, suppose that there is a representation in which k terms and all denominators are different. Let us prove that then we can obtain a representation of unity as a sum from To + 1 fractions the desired type. We will assume that the fractions are decreasing, that is, the denominators (in the representation of the unit by the sum To terms) increase from left to right so that T - the largest of the denominators. We will get the representation we need in the form of a sum(To + 1)th fraction, if we split one fraction, for example the last one, into two. This can be done because And therefore In addition, all fractions remained different, since T was the largest denominator, and t + 1 > t, and t(t + 1) > t. Thus, we have established: On this basis, we can claim that the statement in question is true for all natural numbers, starting from three. Moreover, the above proof also implies an algorithm for finding the required partition of unity. (What algorithm is this? Imagine the number 1 as the sum of 4, 5, 7 terms on its own.) In solving the previous two problems, two steps were taken. The first step is called basis induction, second -inductive junctionor step of induction. The second step is the most important, and it involves making an assumption (the statement is true when n = k) and conclusion (the statement is true when n = k + 1). The parameter n itself is called induction parameter.This logical scheme (technique), which allows us to conclude that the statement in question is true for all natural numbers (or for all, starting from some), since both the basis and the transition are valid, is calledthe principle of mathematical induction, on which The method of mathematical induction is based.The term “induction” itself comes from the Latin word induction (guidance), which means the transition from single knowledge about individual objects of a given class to general conclusion about all subjects of a given class, which is one of the main methods of cognition. The principle of mathematical induction, precisely in the familiar form of two steps, first appeared in 1654 in Blaise Pascal’s “Treatise on the Arithmetic Triangle,” in which a simple way to calculate the number of combinations (binomial coefficients) was proved by induction. D. Polya quotes B. Pascal in the book with minor changes given in square brackets: “Although the proposal in question [the explicit formula for binomial coefficients] contains countless special cases, I will give a very short proof for it, based on two lemmas. The first lemma states that the assumption is true for the reason - this is obvious. [At P = 1 explicit formula is valid...] The second lemma states the following: if our assumption is true for an arbitrary basis [for an arbitrary r], then it will be true for the following reason [for n + 1]. From these two lemmas it necessarily follows that the proposition is valid for all values P. Indeed, by virtue of the first lemma it is true for P = 1; therefore, by virtue of the second lemma, it is true for P = 2; therefore, again by virtue of the second lemma, it is valid for n = 3 and so on ad infinitum.” Problem 3. The Towers of Hanoi puzzle consists of three rods. On one of the rods there is a pyramid (Fig. 1), consisting of several rings of different diameters, decreasing from bottom to top Fig 1 This pyramid must be moved to one of the other rods, moving only one ring each time and not placing the larger ring on the smaller one. Is it possible to do this? Solution. So, we need to answer the question: is it possible to move a pyramid consisting of P rings of different diameters, from one rod to another, following the rules of the game? Now we have, as they say, parametrized the problem (a natural number has been introduced into consideration P), and it can be solved by mathematical induction. Pyramid from to rings lying on the largest(To + 1)-th ring, we can, according to the assumption, move it to any other rod. Let's do it. motionless(To + The 1)th ring will not prevent us from carrying out the movement algorithm, since it is the largest. After moving To rings, let's move this biggest one(To + 1)th ring on the remaining rod. And then again we apply the movement algorithm known to us by inductive assumption To rings, and move them to the rod with the one lying below(To + 1)th ring. Thus, if we know how to move pyramids with To rings, then we know how to move the pyramids and with To + 1 rings. Therefore, according to the principle of mathematical induction, it is always possible to move the pyramid consisting of n rings, where n > 1. Method of mathematical induction in solving divisibility problems. Using the method of mathematical induction, you can prove various statements regarding the divisibility of natural numbers. Problem 4 . 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 it is 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. Problem 3. Prove that the number Z 3
+
3
- 26n - 27 with arbitrary natural n is divisible by 26 2 without a remainder. Solution. Let us first prove by induction the auxiliary statement that 3 3n+3 — 1 is divisible by 26 without a remainder when n > 0. Induction step. Let's assume that 3 3n+3 - 1 is divided by 26 when n = k, and Let us prove that in this case the statement will be true for n = k + 1. Since 3 then from the inductive hypothesis we conclude that the number 3 3k + 6 - 1 is divisible by 26. Now we will prove the statement formulated in the problem statement. And again by induction. divisible by 26 2 without a trace. In the last sum, both terms are divisible by 26 2
. The first is because we have proven that the expression in parentheses is divisible by 26; the second is by the induction hypothesis. By virtue of the principle of mathematical induction, the desired statement is completely proven. Application of the method of mathematical induction to the summation of series. Task 5. Prove formula N is a natural number. Solution. When n=1, both sides of the equality turn to one and, therefore, the first condition of the principle of mathematical induction is satisfied. Let's assume that the formula is correct for n=k, i.e. Let's add to both sides of this equality and transform the right side. Then we get Thus, from the fact that the formula is true for n=k, it follows that it is also true for n=k+1. 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. Task 6. Two numbers are written on the board: 1,1. By entering their sum between the numbers, we get the numbers 1, 2, 1. Repeating this operation again, we get the numbers 1, 3, 2, 3, 1. After three operations, the numbers will be 1, 4, 3, 5, 2, 5, 3, 4, 1. What will be the sum of all the numbers on the board after 100 operations? Solution. Do everything 100 operations would be a very labor-intensive and time-consuming task. This means we need to try to find some general formula for the sum S numbers after n operations. Let's look at the table: Have you noticed any pattern here? If not, you can take one more step: after four operations there will be numbers 1, 5, 4, 7, 3, 8, 5, 7, 2, 7, 5, 8, 3, 7, 4, 5, 1,
the sum of which S 4 is equal to 82. In fact, you can not write down the numbers, but immediately say how the sum will change after adding new numbers. Let the sum be equal to 5. What will it become when new numbers are added? Let's divide each new number into the sum of the two old ones. For example, from 1, 3, 2, 3, 1 we go to 1, 1 + 3, 3, 3 + 2, 2, 2 + 3, 3, 3 + 1, 1.
That is, each old number (except for the two extreme units) is now included in the sum three times, so the new sum is equal to 3S - 2 (subtract 2 to take into account the missing units). Therefore S 5 = 3S 4 - 2 = 244, and in general What is it general formula? If it were not for the subtraction of two units, then each time the sum would increase three times, as in powers of three (1, 3, 9, 27, 81, 243, ...). And our numbers, as we can now see, are one more. Thus, it can be assumed that Let us now try to prove this by induction. Induction base. See table (for n = 0, 1, 2, 3). Induction step. Let's pretend that Let us then prove that S k + 1 = Z k + 1 + 1. Really, So, our formula is proven. It shows that after one hundred operations the sum of all numbers on the board will be equal to 3 100
+ 1.
Let's look at one great example of applying the principle of mathematical induction, in which you first need to introduce two natural parameters and then carry out induction on their sum. Task 7. Prove that if= 2, x 2 = 3 and for any natural p> 3 the relation holds x p = 3x p - 1 - 2x p - 2, That 2 p - 1 + 1, p = 1, 2, 3, ... Solution. Note that in this problem the original sequence of numbers(x p) is determined by induction, since the terms of our sequence, except for the first two, are specified inductively, that is, through the previous ones. So given sequences are called recurrent, and in our case, this sequence is determined (by specifying its first two terms) in a unique way. Induction base. It consists of checking two statements: when n = 1 and n = 2.V In both cases the statement is true by condition. Induction step. Let's assume that for n = k - 1 and n = k the statement is fulfilled, that is Let us then prove the validity of the statement for n = k + 1. We have: x 1 = 3(2 + 1) - 2(2 + 1) = 2+1, which is what needed to be proven. Task 8. Prove that any natural number can be represented as the sum of several different terms of the recurrent sequence of Fibonacci numbers: for k > 2. Solution. Let n - natural number. We will carry out induction on P. Induction base. When n = Statement 1 is true since one itself is a Fibonacci number. Induction step. Suppose that all natural numbers less than some number P, can be represented as the sum of several different terms of the Fibonacci sequence. Let's find the largest Fibonacci number Ft, not superior P; thus, F t p and F t +1 > p. Because the By the induction hypothesis, the number n- F t can be represented as the sum 5 of several different terms of the Fibonacci sequence, and from the last inequality it follows that all terms of the Fibonacci sequence involved in the sum 8 are less F t . Therefore, the expansion of the number n = 8 + F t satisfies the conditions of the problem. Examples of applying the method of mathematical induction to proving inequalities. Task 9. (Bernoulli's inequality.)Prove that when x > -1, x 0, and for integer n > 2 the inequality is true (1 + x) n > 1 + xn. Solution. We will again carry out the proof by induction. 1. Base of induction. Let us verify the validity of the inequality for n = 2. Indeed, (1 + x) 2 = 1 + 2x + x 2 > 1 + 2x. 2. Induction step. Let's assume that for the number p = k the statement is true, that is (1 + x) k > 1 + xk, Where k > 2. Let's prove it for n = k + 1. We have: (1 + x) k + 1 = (1 + x) k (1 + x)>(1 + kx)(1 + x) = 1 + (k + 1)x + kx 2 > 1 + (k + 1)x. So, based on the principle of mathematical induction, we can claim that Bernoulli’s inequality is true for any n > 2. In the context of problems solved using the method of mathematical induction, the general law that needs to be proved is not always clearly formulated. Sometimes it is necessary, by observing particular cases, to first discover (guess) which general law they give, and only then prove the stated hypothesis using the method of mathematical induction. In addition, the induction variable can be masked, and before solving the problem, it is necessary to determine on what parameter the induction will be carried out. As examples, consider the following tasks. Problem 10. Prove that under any natural n > 1. Solution, Let's try to prove this inequality using the method of mathematical induction. The induction basis can be easily verified:1+ By the induction hypothesis and it remains for us to prove that If we use the inductive hypothesis, we will argue that Although this equality is in fact true, it does not give us a solution to the problem. Let's try to prove a stronger statement than required in the original problem. Namely, we will prove that It may seem that proving this statement by induction is a hopeless matter. However, when n = 1 we have: the statement is true. To justify the inductive step, let us assume that and then we will prove that Really, Thus, we have proven a stronger statement, from which the statement contained in the statement of the problem immediately follows. The instructive thing here is that although we had to prove a stronger statement than required in the problem, we could use a stronger assumption in the inductive step. This explains that the straightforward application of the principle of mathematical induction does not always lead to the goal. The situation that arose when solving the problem was calledinventor's paradox.The paradox itself is that more complex plans can be implemented with great success, if they are based on a deeper understanding of the essence of the matter. Problem 11. Prove that 2 m + n - 2 m for any natural type. Solution. Here we have two parameters. Therefore, you can try to carry out the so-calleddouble induction(induction within induction). We will conduct inductive reasoning on P. 1.
The induction base according to paragraph. When n = 1 need to check that 2 t ~ 1 > t. To prove this inequality we use induction on T. A) Induction base according to the so-called When t = 1 executed b) The induction step according to so-calledLet's assume that when t = k the statement is true, that is 2 k ~ 1 > k. Then up to with natural to. So the inequality 2
performed in any natural T. 2. Induction step according to item.Let's choose and fix some natural number T. Let's assume that when n = I the statement is true (for a fixed t), that is, 2 t +1 ~ 2 > t1, and we will prove that then the statement will be true also for n = l + 1. for any natural type. Therefore, based on the principle of mathematical induction (by P) the statement of the problem is true for any P and for any fixed T. Thus, this inequality holds for any natural type. Problem 12. Let m, n and k are natural numbers, and t > p. Which of the two numbers is greater: In every expression To signs square root,
t and p alternate. Solution. Let us first prove some auxiliary statement. Lemma. For any natural t and p (t > p) and non-negative (not necessarily whole) X inequality is true Proof. Consider the inequality This inequality is true since both factors on the left side are positive. Expanding the brackets and transforming, we get: Taking the square root of both sides of the last inequality, we obtain the statement of the lemma. So, the lemma is proven. Let us now move on to solving the problem. Let us denote the first of these numbers by A, and the second - through b k. Let us prove that a under any natural To. We will carry out the proof using the method of mathematical induction separately for even and odd To. Induction base. When k = 1 we have inequality y[t > y/n , fair due to the fact that t > p. When k = 2 the required is obtained from the proven lemma by substitution x = 0. Induction step. Suppose, for some k inequality a > b k fair. Let's prove that From the induction assumption and square root monotonicity we have: On the other hand, from the proven lemma it follows that Combining the last two inequalities, we get: According to the principle of mathematical induction, the statement is proven. Problem 13. (Cauchy's inequality.)Prove that for any positive numbers..., a p inequality is true Solution. For n = 2 the inequality we will assume that the arithmetic mean and the geometric mean (for two numbers) are known. Let n= 2, k = 1, 2, 3, ... and first perform induction on To. The basis of this induction takes place by now assuming that the required inequality has already been established for n = 2, let's prove it for P = 2 . We have (applying the inequality for two numbers): Therefore, by the inductive hypothesis Thus, by induction on k we have proven the inequality for all p 9 being a power of two. To prove the inequality for other values P Let us use “downward induction”, that is, we will prove that if the inequality holds for arbitrary non-negative P numbers, then it is also true for(P - 1st day. To verify this, we note that, according to the assumption made for P numbers the inequality holds that is, a g + a 2 + ... + a n _ x > (n - 1)A. Dividing both parts into P - 1, we obtain the required inequality. So, first we established that the inequality holds for an infinite number of possible values P, and then showed that if the inequality holds for P numbers, then it is also true for(P - 1) numbers. From this we now conclude that Cauty's inequality holds for the set of P any non-negative numbers at any n = 2, 3, 4, ... Problem 14. (D. Uspensky.) For any triangle ABC whose angles = CAB, = CBA are commensurate, there are inequalities Solution. Angles and are commensurable, and this (by definition) means that these angles have general measure, for which = p, = (p, q are coprime natural numbers). Let's use the method of mathematical induction and carry it out through the sum p = p + q natural coprime numbers.. Induction base. For p + q = 2 we have: p = 1 and q = 1. Then triangle ABC is isosceles, and the necessary inequalities are obvious: they follow from the triangle inequality Induction step. Let us now assume that the necessary inequalities are established for p + q = 2, 3, ..., k - 1, where k > 2. Let us prove that the inequalities are also valid for p + q = k. Let ABC - a given triangle that has> 2. Then sides AC and BC cannot be equal: let AC > BC. Let us now construct, as in Figure 2, an isosceles triangle ABC; we have: AC = DC and AD = AB + BD, therefore, 2AC > AB + BD (1) Consider now the triangle BDC, whose angles are also commensurate: DСВ = (q - р), ВDC = p. Rice. 2 For this triangle the inductive hypothesis holds, and therefore (2)
Adding (1) and (2), we have: 2AC+BD> and therefore From the same triangle VBS by the induction hypothesis we conclude that Taking into account the previous inequality, we conclude that Thus, the inductive transition is obtained, and the statement of the problem follows from the principle of mathematical induction. Comment. The statement of the problem remains valid even in the case when the angles a and p are not commensurate. In the basis of consideration in the general case, it is already necessary to apply another important mathematical principle— the principle of continuity. Problem 15. Several straight lines divide the plane into parts. Prove that you can color these parts white and black colors so that adjacent parts that have a common border segment are different color(as in Figure 3 with n = 4). pic 3 Solution. Let us use induction on the number of lines. So let P - the number of lines dividing our plane into parts, n > 1. Induction base. If there is only one straight line(P = 1), then it divides the plane into two half-planes, one of which can be colored in White color, and the second in black, and the statement of the problem is correct. Induction step. To make the proof of the inductive transition more clear, consider the process of adding one new line. If we draw a second straight line(P= 2), then we get four parts that can be colored as needed by painting the opposite corners the same color. Let's see what happens if we draw a third straight line. It will divide some of the “old” parts, while new sections of the border will appear, on both sides of which the color is the same (Fig. 4). Rice. 4 Let's proceed as follows:On the one sidefrom the new straight line we will change the colors - we will make white black and vice versa; at the same time, we do not repaint those parts that lie on the other side of this straight line (Fig. 5). Then this new coloring will satisfy the necessary requirements: on one side of the line it was already alternating (but with different colors), and on the other side it was what was needed. In order for the parts that have a common border belonging to the drawn line to be painted in different colors, we repainted the parts only on one side of this drawn straight line. Fig.5 Let us now prove the inductive transition. Let us assume that for somep = kthe statement of the problem is true, that is, all parts of the plane into which it is divided by theseTostraight, you can paint them white and black so that adjacent parts are of different colors. Let us prove that then there exists such a coloring forP=
To+ 1 direct. Let us proceed similarly to the case of transition from two lines to three. Let's draw on the planeTostraight Then, by the induction hypothesis, the resulting “map” can be colored in the desired way. Let's now carry out(To+ 1)th straight line and on one side of it we change the colors to the opposite ones. So now(To+ 1)-th straight line separates areas of different colors everywhere, while the “old” parts, as we have already seen, remain correctly colored. According to the principle of mathematical induction, the problem is solved. Task16. On the edge of the desert there is a large supply of gasoline and a car that, when fully refueled, can travel 50 kilometers. There are unlimited quantities of canisters into which you can pour gasoline from your car’s gas tank and leave it for storage anywhere in the desert. Prove that a car can travel any integer distance greater than 50 kilometers. You are not allowed to carry gasoline cans; you can carry empty ones in any quantity. Solution.Let's try to prove by induction onP,that the car can drive awayPkilometers from the edge of the desert. AtP= 50 is known. All that remains is to carry out the induction step and explain how to get therep = k+ 1 kilometers if it is known thatp = kYou can drive kilometers. However, here we encounter a difficulty: after we have passedTokilometers, there may not be enough gasoline even for the return journey (not to mention storage). And in this case, the solution is to strengthen the statement being proven (the inventor's paradox). We will prove that you can not only drivePkilometers, but also to make an arbitrarily large supply of gasoline at a point at a distancePkilometers from the edge of the desert, arriving at this point after the end of transportation. Induction base.Let a unit of gasoline be the amount of gasoline required to travel one kilometer. Then a trip of 1 kilometer and back requires two units of gasoline, so we can leave 48 units of gasoline in a storage facility a kilometer away from the edge and return for a new portion. Thus, over several trips to the storage facility, we can make a stock of any size that we need. At the same time, to create 48 units of reserve, we consume 50 units of gasoline. Induction step.Let's assume that at a distanceP=
Tofrom the edge of the desert you can stock up on any amount of gasoline. Let us prove that then it is possible to create a storage facility at a distancep = k+ 1 kilometers with any reserve of gasoline specified in advance and end up at this storage facility at the end of the transportation. Because at the pointP=
Tothere is an unlimited supply of gasoline, then (according to the induction base) we can reach a point in several tripsp = k+ 1 do at pointP=
To4- 1 stock of any size that is required. The truth of a more general statement than in the problem statement now follows from the principle of mathematical induction. Conclusion In particular, by studying the method of mathematical induction, I increased my knowledge in this area of mathematics, and also learned to solve problems that were previously beyond my strength. Mostly these were logical and entertaining tasks, i.e. just those that increase interest in mathematics itself as a science. Solving such problems becomes an entertaining activity and can attract more and more curious people into mathematical labyrinths. In my opinion, this is the basis of any science. Continuing to study the method of mathematical induction, I will try to learn how to apply it not only in mathematics, but also in solving problems in physics, chemistry and life itself. Literature 1.Vulenkin INDUCTION. Combinatorics. Manual FOR teachers. M., Enlightenment, 1976.-48 p. 2. Golovina L.I., Yaglom I.M. Induction in geometry. - M.: State. published liter. - 1956 - S.I00. A manual on mathematics for those entering universities / Ed. Yakovleva G.N. The science. -1981. - P.47-51. 3.Golovina L.I., Yaglom I.M. Induction in geometry. — 4. I.T.Demidov, A.N.Kolmogorov, S.I.Schvartsburg, O.S.Ivashev-Musatov, B.E.Weitz. Textbook / “Enlightenment” 1975. 5.R. Courant, G. Robbins "What is mathematics?" Chapter 1, § 2 6.Popa D. Mathematics and plausible reasoning. - M,: Nauka, 1975. 7.Popa D. Mathematical discovery. - M.: Nauka, 1976. 8. Rubanov I.S. How to teach the method of mathematical induction / Mathematics school. - Nl. - 1996. - P.14-20. 9. Sominsky I.S., Golovina L.I., Yaglom IM. On the method of mathematical induction. - M.: Nauka, 1977. - (Popular lectures on mathematics.) 10.Solominsky I.S. Method of mathematical induction. - M.: Science. 63s. 11.Solominsky I.S., Golovina L.I., Yaglom I.M. About mathematical induction. - M.: Science. - 1967. - P.7-59. 12.http://w.wikimedia.org/wiki 13.htt12:/ /www.refeshtcollestiop.ru/40 124.html Lecture 6. Method of mathematical induction. New knowledge in science and life is obtained in different ways, but all of them (if you do not go into details) are divided into two types - the transition from the general to the specific and from the specific to the general. The first is deduction, the second is induction. Deductive reasoning is what is commonly called in mathematics. logical reasoning, and in mathematical science deduction is the only legitimate method of investigation. The rules of logical reasoning were formulated two and a half millennia ago by the ancient Greek scientist Aristotle. He created a complete list of the simplest correct reasoning, syllogisms– “building blocks” of logic, while simultaneously indicating typical reasoning that is very similar to correct, but incorrect (we often encounter such “pseudological” reasoning in the media). Induction (induction - in Latin guidance) is clearly illustrated by the famous legend of how Isaac Newton formulated the law of universal gravitation after an apple fell on his head. Another example from physics: in a phenomenon such as electromagnetic induction, an electric field creates, “induces” a magnetic field. “Newton's apple” is a typical example of a situation where one or more special cases, that is, observations, “suggest” a general statement; a general conclusion is drawn on the basis of particular cases. Inductive method is fundamental for obtaining general patterns in both the natural and human sciences. But it has a very significant drawback: based on particular examples, an incorrect conclusion can be drawn. Hypotheses arising from private observations are not always correct. Let's consider an example due to Euler. We will calculate the value of the trinomial for some first values n: Note that the numbers obtained as a result of calculations are prime. And one can directly verify that for each n 1 to 39 polynomial value Leibniz proved in the 17th century that for every positive whole n number The considered examples allow us to draw an important conclusion: a statement can be fair in a number of special cases and at the same time unfair in general. The question of the validity of a statement in the general case can be resolved by using a special method of reasoning called by mathematical induction(complete induction, perfect induction). 6.1. The principle of mathematical induction. ♦ The method of mathematical induction is based on principle of mathematical induction
, which is as follows: 1) the validity of this statement is checked forn=1
(induction basis)
,
2) the validity of this statement is assumed forn=
k, Wherek– arbitrary natural number 1(induction assumption)
, and taking this assumption into account, its validity is established forn=
k+1.
Proof.
Let us assume the opposite, that is, suppose that the statement is not true for every natural n. Then there is such a natural m, What: 1) statement for n=m not fair, 2) for everyone n, smaller m, the statement is true (in other words, m is the first natural number for which the statement is not true). It's obvious that m>1, because For n=1 the statement is true (condition 1). Hence, Note that the proof used the axiom that any set of natural numbers contains the smallest number. A proof based on the principle of mathematical induction is called by the method of complete mathematical induction
.
Example6.1.
Prove that for any natural n number Solution. 1) When n=1, so a 1 is divisible by 3 and the statement is true when n=1. 2) Suppose that the statement is true for n=k,
Indeed, Because Each term is divisible by 3, then their sum is also divisible by 3. ■
Example6.2.
Prove that the sum of the first n natural odd numbers is equal to the square of their number, that is. Solution. Let's use the method of complete mathematical induction. 1) We check the validity of this statement when n=1: 1=1 2 – this is true. 2) Suppose that the sum of the first k
( We use our assumption and get .
■
The method of complete mathematical induction is used to prove some inequalities. Let us prove Bernoulli's inequality. Example6.3.
Prove that when Solution. 1) When n=1 we get 2) We assume that when n=k there is inequality Let's multiply both sides of the inequality (*) by the number That is (1+ Proof by method incomplete mathematical induction
some statement depending on n, Where Some problems do not explicitly state a statement that can be proven by mathematical induction. In such cases, you need to establish the pattern yourself and make a hypothesis about the validity of this pattern, and then use the method of mathematical induction to test the proposed hypothesis. Example6.4.
Find the amount Solution. Let's find the sums S 1 ,
S 2 ,
S 3. We have 1) When n=1 hypothesis is correct, because 2) Suppose that the hypothesis is true for n=k,
Indeed, So, based on the assumption that the hypothesis is true when n=k,
Example6.5.
In mathematics, it is proven that the sum of two uniformly continuous functions is a uniformly continuous function. Based on this statement, you need to prove that the sum of any number Solution. The basis of induction here is contained in the formulation of the problem itself. Having made the induction assumption, consider This proves the statement and we will use it further. ■
Example6.6.
Find all natural n, for which the inequality is true Solution. Let's consider n=1, 2, 3, 4, 5, 6. We have: 2 1 >1 2, 2 2 =2 2, 2 3<3 2 ,
2 4 =4 2 ,
2 5 >5 2, 2 6 >6 2. Thus, we can make a hypothesis: inequality 1) As was established above, this hypothesis is true when n=5. 2) Assume that it is true for n=k,
Because then we get that From paragraphs. 1 and 2, based on the principle of incomplete mathematical induction, it follows that the inequality Example6.7.
Prove that for any natural number n the differentiation formula is valid Solution. At n=1 this formula looks like Q.E.D. ■
Example6.8.
Prove that the set consisting of n elements, has Solution. A set consisting of one element A, has two subsets. This is true because all its subsets are the empty set and the empty set itself, and 2 1 =2. Let us assume that every set of n elements has The set B consists of n elements, and therefore, by induction, he has But in the second class there are the same number of subsets: each of them is obtained from exactly one subset of the first class by adding an element d. Therefore, in total the set A Thus the statement is proven. Note that it is also true for a set consisting of 0 elements - the empty set: it has a single subset - itself, and 2 0 = 1. ■
Induction in mathematics
Both jokingly and seriously
Familiar circles
Examples with natural numbers
Errors in judgment
Induction and the laws of logic
Induction in the scientific community
Induction and deduction from the position of philosophy
Application of induction in economics
a competing company has expanded its product line;
nothing else has changed;
Deduction and induction in psychology
Instead of a conclusion
The full version of the work is available in the "Work Files" tab in PDF formatDownload:
Preview:
then it is also true for k + 1.
Let us prove that then we can move the pyra midka from n = k + 1.
expression 3 3k + 3 - 26k - 27 is divided by 26 2
without remainder, and prove that the statement is true for n = k + 1,
that is, that number
equality, which is acceptable.
let us say that the statement will be true also for t = k + 1.
We have:
We have:
M.: Nauka, 1961. - (Popular lectures on mathematics.)
is prime number. However, when n=40 we get the number 1681=41 2, which is not prime. Thus, the hypothesis that could arise here, that is, the hypothesis that for each n number 
is simple, turns out to be false.
divisible by 3, number 
divisible by 5, etc. Based on this, he assumed that for any odd k and any natural n number 
divided by k, but soon I noticed that 
is not divisible by 9.
- natural number. It turns out that for a natural number 
the statement is true, and for the next natural number m it's unfair. This contradicts condition 2. ■
divisible by 3.
, that is, that number 
is divisible by 3, and we establish that when n=k+1 number is divisible by 3.
) of odd numbers is equal to the square of the number of these numbers, that is. Based on this equality, we establish that the sum of the first k+1 odd numbers is equal to 
, that is .
and any natural n inequality is true 
(Bernoulli's inequality).
, which is true.
(*). Using this assumption, we prove that 
. Note that when 
this inequality holds and therefore it suffices to consider the case 
.
and we get:
.■
held the same way, but at the beginning fairness is established for the smallest value n.
.
,
,
. We hypothesize that for any natural n the formula is valid 
. To test this hypothesis, we will use the method of complete mathematical induction.
.
, that is 
. Using this formula, we establish that the hypothesis is true even when n=k+1, that is
, it has been proven that it is true also for n=k+1, and based on the principle of mathematical induction we conclude that the formula is valid for any natural number n.
■
uniformly continuous functions is uniformly continuous function. But since we have not yet introduced the concept of “uniformly continuous function,” let us pose the problem more abstractly: let it be known that the sum of two functions that have some property S, itself has the property S. Let us prove that the sum of any number of functions has the property S.
functions f 1 ,
f 2 ,
…, f n ,
f n+1 that have the property S. Then . On the right side, the first term has the property S by the induction hypothesis, the second term has the property S by condition. Consequently, their sum has the property S– for two terms the induction basis “works”.
.
has a place for everyone 
. To prove the truth of this hypothesis, we will use the principle of incomplete mathematical induction.
, that is, the inequality is true 
. Using this assumption, we prove that the inequality 
.
and at 
there is inequality 
at 
,
. So, the truth of the hypothesis at n=k+1 follows from the assumption that it is true when n=k,
.
true for every natural 
.
■
.
, or 1=1, that is, it is correct. Making the induction assumption, we have:
subsets
subsets If the set A consists of n+1 elements, then we fix one element in it - we denote it d, and divide all subsets into two classes - those not containing d and containing d. All subsets from the first class are subsets of the set B obtained from A by removing an element d.
subsets, so in the first class 
subsets
subsets