Method of mathematical induction
Introduction
Main part
- Complete and incomplete 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 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. Well, tell me that those two or three lessons will be useful to a person, 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 can be represented as the sum of two prime numbers. To do this, take all such numbers and write out the corresponding expansions:
4=2+2; 6=3+3; 8=5+3; 10=7+3; 12=7+5;
14=7+7; 16=11+5; 18=13+5; 20=13+7.
These nine equalities show that each of the numbers 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 several 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 you 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 the next number 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 proposal A(n), depending on the natural numbern, true forn=1 and from the fact that it is true forn= k (Wherek-any natural number), it follows that it is true for the next numbern= k+1, then assumption A(n) true for any natural numbern.
In a number of cases, it may be necessary to prove the validity of a certain statement not for all natural numbers, but only for n>p, where p is a fixed natural number. In this case, the principle of mathematical induction is formulated as follows.
If proposal A(n) true forn= p and if A(k) Þ A(k+1) for anyonek> p, then proposal A(n) true for anyonen> 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).
EXAMPLE 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.
EXAMPLE 2
Prove that
1+x+x 2 +x 3 +…+x n =(x n +1 -1)/(x-1), where x¹1
Solution: 1) For n=1 we get
1+x=(x 2 -1)/(x-1)=(x-1)(x+1)/(x-1)=x+1
therefore, for n=1 the formula is 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 holds
1+x+x 2 +x 3 +…+x k +x k +1 =(x k +2 -1)/(x-1).
Indeed
1+x+x 2 +x 3 +…+x k +x k +1 =(1+x+x 2 +x 3 +…+x k)+x k +1 =
=(x k +1 -1)/(x-1)+x k +1 =(x k +2 -1)/(x-1).
So, A(k)ÞA(k+1). Based on the principle of mathematical induction, we conclude that the formula is true for any natural number n.
EXAMPLE 3
Prove that the number of diagonals of a convex n-gon is 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 the 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.
EXAMPLE 4
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.
EXAMPLE 5
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.
EXAMPLE 6
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
EXAMPLE 7
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.
EXAMPLE 8
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.
EXAMPLE 9
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.
EXAMPLE 10
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.
EXAMPLE 11
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 3 k -1 +2 4k-3)+11´3 3k-1 .
The first term is divisible by 11 without a remainder, since 3 3 k-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.
EXAMPLE 12
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 2 k -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.
EXAMPLE 13
Prove that 3 3 n+3 -26n-27 for an arbitrary natural number n is divisible by 26 2 (676) without a remainder.
Solution: First we prove that 3 3 n+3 -1 is divisible by 26 without a remainder.
- When n=0
3 3 -1=26 is divided by 26
- Let's assume that for n=k
3 3k+3 -1 is divisible by 26
- Let us prove that the statement
true for n=k+1.
3 3 k+6 -1=27´3 3k+3 -1=26´3 3l+3 +(3 3 k +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 3 k+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.
EXAMPLE 14
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
EXAMPLE 15
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.
EXAMPLE 16
Prove that for n>6 the inequality is true
Solution: Let's rewrite the inequality in the form
- For n=7 we have
3 7 /2 7 =2187/128>14=2´7
the inequality is true.
- Let's assume that for n=k
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.
EXAMPLE 17
Prove that for n>2 the inequality is true
1+(1/2 2)+(1/3 2)+…+(1/n 2)
Solution: 1) For n=3 the inequality is true
1+(1/2 2)+(1/3 2)=245/180
- 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)
Let us prove that 1.7-(1/k)+(1/(k+1) 2)
Û(1/(k+1) 2)+(1/k+1)Ûk(k+2)
The latter is obvious, and therefore
1+(1/2 2)+(1/3 2)+…+(1/(k+1) 2)
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
Textbook / 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.
The video lesson “Method of Mathematical Induction” helps you master the method of mathematical induction. The video contains material that helps you understand the essence of the method, remember the features of its application, and learn how to apply this method when solving problems. The purpose of this video tutorial is to facilitate the development of the material and to develop the ability to solve mathematical problems using the induction method.
To keep students' attention on learning the material, animation effects, illustrations, and presentation of information in color are used. A video lesson frees up the teacher’s time in class to improve the quality of individual work and solve other educational problems.
The concept of the method of mathematical induction is introduced by considering the sequence a n , in which a 1 =4, and a n+1 = a n +2n+3. In accordance with the general representation of the sequence member, it is determined that a 1 =4, a 2 =4+2·1+3=9, a 3 =9+2·2+3=16, that is, the sequence of numbers 4, 9, 16,... It is assumed that for this sequence a n =(n+1) 2 is true. For the indicated terms of the sequence - first, second, third - the formula is correct. It is necessary to prove the validity of this formula for any arbitrarily large n. It is indicated that in such cases the method of mathematical induction is used to help prove the statement.
The essence of the method is revealed. The formula for n=k is assumed to be valid, the value a k =(k+1) 2 . It is necessary to prove that the equality will also be valid for k+1, which means a k +1 =(k+2) 2 . To do this, in the formula a k +1 =a k +2k+3 we replace a k with (k+1) 2. After substitution and reduction of similar ones, we obtain the equality a k +1 =(k+2) 2 . This gives us the right to assert that the validity of the formula for n makes it true for n=k+1. The considered proof in relation to the sequence a n , which is represented by the numbers 4, 9, 16,... and the general term a n =(n+1) 2, gives the right to assert that if the formula turns into a true equality for n=1, then also for n=1+ 1=2, and for 3, etc., that is, for any natural number n.
Next, the essence of the induction method is presented in mathematical language. The principle of the method is based on the validity of the statement that a fact holds for an arbitrary natural number n when two conditions are met: 1) the statement is true for n=1 2) from the validity of this formula for n=k it follows that it is valid for n=k+1. From this principle follows the structure of the proof, using the method of mathematical induction. It is noted that this method assumes for n=1 the proof of the validity of the statement, and when assuming the validity of the proof for n=k, it is proved that it is also true for n=k+1.
An example of proving Archimedes' formula using the method of mathematical induction is analyzed. Given the formula 1 2 +2 2 +3 2 +…+n 2 =n(n+1)(2n+1)/6. Calculations are carried out on the screen to show the validity of the formula for n=1. The second point of the proof is the assumption that for n=k the formula is valid, that is, it takes the form 1 2 +2 2 +3 2 +…+k 2 =k(k+1)(2k+1)/6. Based on this , it is proved that the formula is also true for n=k+1. After substituting n=k+1 we get the value of the formula 1 2 +2 2 +3 2 +…+k 2 +(k+1) 2 =(k+1)(k+2)(2k+3)/6. Thus, Archimedes' formula is proven.
Another example examines the proof of the multiplicity of 7 of the sum 15 n +6 for any natural number n. In the proof we use the method of mathematical induction. First, we check the validity of the statement for n=1. Indeed, 15 1 +6=21. Then we assume validity for n=k. This means that 15 k +6 is a multiple of 7. By substituting n=k+1 into the formula we prove that the value 15 k +1 +6 is a multiple of 7. After transforming the expression, we get: 15 k +1 +6=15 k +1 ·14+(15 k +6). Therefore the sum 15 n +6 is a multiple of 7.
The video lesson “Method of Mathematical Induction” clearly and in detail reveals the essence and mechanism of using the method of mathematical induction in proof. Therefore, this video material can serve not only as a visual aid in an algebra lesson, but will be useful when the student independently studies the material, and will help explain the topic to the teacher during distance learning.
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.
Download:
Preview:
Ministry of Science and Education of the Russian Federation
State educational institution
secondary school No. 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 a good criterion of 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.
Problem 2. Consider all possible ordinary 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 of the required 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:
- with n = 3 this statement is true;
- if the statement we are interested in is true for To,
then it is also true for k + 1.
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 transitionor 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 a general conclusion about all objects 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.
- Induction base. When n = 1 everything is clear, since a pyramid of one ring can obviously be moved to any rod.
- Induction step. Let's assume that we can move any pyramids with the number of rings p = k.
Let us prove that then we can move the pyra midka from n = k + 1.
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 base. For n = 0 we have: 3 3 - 1 = 26—divisible by 26.
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.
- Induction base. It is obvious that when n = 1 statement is true: since 3 3+3 - 26 - 27 = 676 = 26 2 .
- Induction step. Let's assume that when p = k
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
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 the 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) what general law they lead to, and only then prove the stated hypothesis by 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 greater 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
equality, which is acceptable.
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
let us say that the statement will be true also for t = k + 1.
We have:
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.
We have:
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 square root signs, 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 for 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 a common 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, we already have to apply another important mathematical principle - the principle of continuity.
Problem 15. Several straight lines divide the plane into parts. Prove that you can color these parts white
and black colors so that adjacent parts that have a common border segment are of different colors (as in Figure 3 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 white and the second black, and the statement of the problem is true.
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 straight 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, in several trips to the pointp = 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 power.
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. —
M.: Nauka, 1961. - (Popular lectures on mathematics.)
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
Induction is a method of obtaining a general statement from particular observations. In the case where a mathematical statement concerns a finite number of objects, it can be proven by testing for each object. For example, the statement: “Every two-digit even number is the sum of two prime numbers,” follows from a series of equalities that are quite feasible to establish:
10=5+5 12=5+7 14=7+7 16=5+11 . . . 92=3+89 94=5+89 96=7+89 98=19+79.
A method of proof in which a statement is verified for a finite number of cases that exhaust all possibilities is called complete induction. This method is used relatively rarely, since mathematical statements, as a rule, concern not finite, but infinite sets of objects. For example, the statement about even two-digit numbers proved above by complete induction is only a special case of the theorem: “Any even number is the sum of two prime numbers.” This theorem has not yet been proven or disproven.
Mathematical induction is a method of proving a certain statement for any natural number n based on the principle of mathematical induction: “If a statement is true for n=1 and its validity for n=k implies the validity of this statement for n=k+1, then it is true for all n " The method of proof by mathematical induction is as follows:
1) base of induction: they prove or directly check the validity of the statement for n=1 (sometimes n=0 or n=n 0);
2) induction step (transition): they assume the validity of the statement for some natural number n=k and, based on this assumption, prove the validity of the statement for n=k+1.
Problems with solutions
1. Prove that for any natural number n, the number 3 2n+1 +2 n+2 is divisible by 7.
Let us denote A(n)=3 2n+1 +2 n+2.
Induction base. If n=1, then A(1)=3 3 +2 3 =35 and, obviously, is divisible by 7.
Induction Assumption. Let A(k) be divisible by 7.
Induction transition. Let us prove that A(k+1) is divisible by 7, that is, the validity of the statement of the problem for n=k.
A(k+1)=3 2(k+1)+1 +2 (k+1)+2 =3 2k+1 ·3 2 +2 k+2 ·2 1 =3 2k+1 ·9+2 k+2 ·2=
3 2k+1 9+2 k+2 (9–7)=(3 2k+1 +2 k+2) 9–7 2 k+2 =9 A(k)–7 2 k +2.
The last number is divisible by 7, since it is the difference of two integers divisible by 7. Therefore, 3 2n+1 +2 n+2 is divisible by 7 for any natural number n.
2. Prove that for any natural number n, the number 2 3 n +1 is divisible by 3 n+1 and not divisible by 3 n+2.
Let's introduce the notation: a i =2 3 i +1.
For n=1 we have, and 1 =2 3 +1=9. So, a 1 is divisible by 3 2 and not divisible by 3 3.
Let for n=k the number a k is divisible by 3 k+1 and not divisible by 3 k+2, that is, a k =2 3 k +1=3 k+1 m, where m is not divisible by 3. Then
and k+1 =2 3 k+1 +1=(2 3 k) 3 +1=(2 3 k +1)(2 3 k ·2 –2 3 k +1)=3 k+1 ·m· ((2 3 k +1) 2 –3·2 3 k)=3 k+1 ·m·((3 k+1 ·m) 2 –3·2 3 k)=
3 k+2 ·m·(3 2k+1 ·m 2 –2 3 k).
Obviously, a k+1 is divisible by 3 k+2 and not divisible by 3 k+3.
Therefore, the statement is proven for any natural number n.
3. It is known that x+1/x is an integer. Prove that x n +1/x n is also an integer for any integer n.
Let’s introduce the notation: a i =х i +1/х i and immediately note that a i =а –i, so we will continue to talk about natural indices.
Note: a 1 is an integer by convention; and 2 is an integer, since a 2 = (a 1) 2 –2; and 0 =2.
Let us assume that a k is an integer for any natural number k not exceeding n. Then a 1 ·a n is an integer, but a 1 ·a n =a n+1 +a n–1 and a n+1 =a 1 ·a n –a n–1 . However, n–1, according to the induction hypothesis, is an integer. This means that a n+1 is also an integer. Therefore, x n +1/x n is an integer for any integer n, which is what needed to be proved.
4. Prove that for any natural number n greater than 1 the double inequality is true
5. Prove that for natural n > 1 and |x|
(1–x)n +(1+x)n
For n=2 the inequality is true. Really,
(1–x) 2 +(1+x) 2 = 2+2 x 2
If the inequality is true for n=k, then for n=k+1 we have
(1–x) k+1 +(1+x) k+1
The inequality has been proven for any natural number n > 1.
6. There are n circles on a plane. Prove that for any arrangement of these circles, the map they form can be correctly colored with two colors.
Let's use the method of mathematical induction.
For n=1 the statement is obvious.
Let us assume that the statement is true for any map formed by n circles, and let there be n+1 circles on the plane. By removing one of these circles, we get a map that, due to the assumption made, can be correctly colored with two colors (see the first picture below).
Then we will restore the discarded circle and on one side of it, for example inside, we will change the color of each area to the opposite (see the second picture). It is easy to see that in this case we will obtain a map correctly colored with two colors, but only now for n+1 circles, which is what we needed to prove.
7. We will call a convex polygon “beautiful” if the following conditions are met:
1) each of its vertices is painted in one of three colors;
2) any two adjacent vertices are painted in different colors;
3) at least one vertex of the polygon is painted in each of the three colors.
Prove that any beautiful n-gon can be cut by disjoint diagonals into “beautiful” triangles.
Let's use the method of mathematical induction.
Induction base. With the smallest possible n=3, the statement of the problem is obvious: the vertices of the “beautiful” triangle are painted in three different colors and no cuts are needed.
Induction Assumption. Let us assume that the statement of the problem is true for any “beautiful” n-gon.
Induction step. Let us consider an arbitrary “beautiful” (n+1)-gon and prove, using the induction hypothesis, that it can be cut by certain diagonals into “beautiful” triangles. Let us denote by A 1, A 2, A 3, ... A n, A n+1 the successive vertices of the (n+1)-gon. If only one vertex of an (n+1)-gon is colored in any of the three colors, then by connecting this vertex with diagonals to all vertices that are not adjacent to it, we obtain the necessary partition of the (n+1)-gon into “beautiful” triangles.
If at least two vertices of an (n+1)-gon are colored in each of the three colors, then we denote the color of vertex A 1 by number 1, and the color of vertex A 2 by number 2. Let k be the smallest number such that vertex A k is colored in the third color. It is clear that k > 2. Let us cut off the triangle A k–2 A k–1 A k from the (n+1)-gon with diagonal A k–2 A k . In accordance with the choice of the number k, all the vertices of this triangle are painted in three different colors, that is, this triangle is “beautiful”. The convex n-gon A 1 A 2 ... A k–2 A k A k+1 ... A n+1 , which remains, will also, by virtue of the inductive assumption, be “beautiful”, which means it is divided into “beautiful” triangles, which and needed to be proven.
8. Prove that in a convex n-gon it is impossible to choose more than n diagonals so that any two of them have a common point.
Let's carry out the proof using the method of mathematical induction.
Let us prove a more general statement: in a convex n-gon it is impossible to choose more than n sides and diagonals so that any two of them have a common point. For n = 3 the statement is obvious. Let us assume that this statement is true for an arbitrary n-gon and, using this, we will prove its validity for an arbitrary (n+1)-gon.
Let us assume that this statement is not true for an (n+1)-gon. If no more than two selected sides or diagonals emerge from each vertex of an (n+1)-gon, then no more than n+1 of them are selected in total. Therefore, from some vertex A there emerge at least three selected sides or diagonals AB, AC, AD. Let AC lie between AB and AD. Since any side or diagonal that emerges from point C and other than CA cannot simultaneously intersect AB and AD, only one chosen diagonal CA emerges from point C.
Discarding point C together with diagonal CA, we obtain a convex n-gon in which more than n sides and diagonals are selected, any two of which have a common point. Thus, we come to a contradiction with the assumption that the statement is true for an arbitrary convex n-gon.
So, for an (n+1)-gon the statement is true. According to the principle of mathematical induction, the statement is true for any convex n-gon.
9. There are n straight lines in a plane, no two of which are parallel and no three pass through the same point. How many parts do these lines divide the plane into?
Using elementary drawings, you can easily verify that one straight line divides the plane into 2 parts, two straight lines into 4 parts, three straight lines into 7 parts, and four straight lines into 11 parts.
Let us denote by N(n) the number of parts into which n straight lines divide the plane. It can be noticed that
N(2)=N(1)+2=2+2,
N(3)=N(2)+3=2+2+3,
N(4)=N(3)+4=2+2+3+4.
It is natural to assume that
N(n)=N(n–1)+n=2+2+3+4+5+…+n,
or, as is easy to establish, using the formula for the sum of the first n terms of an arithmetic progression,
N(n)=1+n(n+1)/2.
Let us prove the validity of this formula using the method of mathematical induction.
For n=1 the formula has already been checked.
Having made the induction assumption, we consider k+1 lines that satisfy the conditions of the problem. Let us select k straight lines from them in an arbitrary manner. By the induction hypothesis, they will split the plane into 1+ k(k+1)/2 parts. The remaining (k+1)th straight line will be divided by the selected k straight lines into k+1 parts and, therefore, will pass along the (k+1)th part into which the plane has already been divided, and each of these parts will be divided into 2 parts, that is, another k+1 part will be added. So,
N(k+1)=N(k)+k+1=1+ k(k+1)/2+k+1=1+(k+1)(k+2)/2,
Q.E.D.
10. In the expression x 1: x 2: ... : x n, parentheses are placed to indicate the order of actions and the result is written as a fraction:
(in this case, each of the letters x 1, x 2, ..., x n is either in the numerator of the fraction or in the denominator). How many different expressions can be obtained in this way with all possible ways of placing parentheses?
First of all, it is clear that in the resulting fraction x 1 will be in the numerator. It is almost as obvious that x 2 will be in the denominator no matter how the parentheses are placed (the division sign in front of x 2 refers either to x 2 itself or to some expression containing x 2 in the numerator).
It can be assumed that all other letters x 3, x 4, ..., x n can be located in the numerator or denominator in a completely arbitrary manner. It follows that in total you can get 2 n–2 fractions: each of the n–2 letters x 3, x 4, ..., x n can appear independently of the others in the numerator or denominator.
Let us prove this statement by induction.
With n=3 you can get 2 fractions:
so the statement is true.
Let's assume that it is true for n=k and prove it for n=k+1.
Let the expression x 1: x 2: ... : x k after some placement of brackets be written in the form of a certain fraction Q. If instead of x k in this expression we substitute x k: x k+1, then x k will be in the same place as it was in fraction Q, and x k+1 will not be where x k was (if x k was in the denominator, then x k+1 will be in the numerator and vice versa).
Now we will prove that we can add x k+1 to the same place where x k is located. In the fraction Q, after placing the brackets, there will necessarily be an expression of the form q:x k, where q is the letter x k–1 or some expression in brackets. Replacing q:x k with the expression (q:x k):x k+1 =q:(x k ·x k+1), we obviously get the same fraction Q, where instead of x k there is x k ·x k+1 .
Thus, the number of all possible fractions in the case n=k+1 is 2 times greater than in the case n=k and is equal to 2 k–2 ·2=2 (k+1)–2. Thus the statement is proven.
Answer: 2 n–2 fractions.
Problems without solutions
1. Prove that for any natural n:
a) the number 5 n –3 n +2n is divisible by 4;
b) the number n 3 +11n is divisible by 6;
c) the number 7 n +3n–1 is divisible by 9;
d) the number 6 2n +19 n –2 n+1 is divisible by 17;
e) the number 7 n+1 +8 2n–1 is divisible by 19;
e) the number 2 2n–1 –9n 2 +21n–14 is divisible by 27.
2. Prove that (n+1)·(n+2)· …·(n+n) = 2 n ·1·3·5·…·(2n–1).
3. Prove the inequality |sin nx| n|sin x| for any natural n.
4. Find natural numbers a, b, c that are not divisible by 10 and such that for any natural n the numbers a n + b n and c n have the same last two digits.
5. Prove that if n points do not lie on the same line, then among the lines that connect them there are at least n different ones.
Bibliographic description: Badanin A. S., Sizova M. Yu. Application of the method of mathematical induction to solving problems on the divisibility of natural numbers // Young scientist. 2015. No. 2. P. 84-86..04.2019).
In mathematics Olympiads there are often quite difficult problems to prove the divisibility of natural numbers. Schoolchildren face a problem: how to find a universal mathematical method that allows them to solve such problems?
It turns out that most problems in proving divisibility can be solved by the method of mathematical induction, but school textbooks pay very little attention to this method; most often a brief theoretical description is given and several problems are analyzed.
We find the method of mathematical induction in number theory. At the dawn of number theory, mathematicians discovered many facts inductively: L. Euler and K. Gauss sometimes considered thousands of examples before noticing a numerical pattern and believing in it. But at the same time they understood how deceptive hypotheses that have passed the “final” test can be. To inductively move from a statement verified for a finite subset to a similar statement for the entire infinite set, a proof is required. This method was proposed by Blaise Pascal, who found a general algorithm for finding signs of divisibility of any integer by any other integer (treatise “On the nature of the divisibility of numbers”).
The method of mathematical induction is used to prove by reasoning the truth of a certain statement for all natural numbers or the truth of a statement starting from a certain number n.
Solving problems to prove the truth of a certain statement using the method of mathematical induction consists of four stages (Fig. 1):
Rice. 1. Scheme for solving the problem
1. Induction basis . They check the validity of the statement for the smallest natural number for which the statement makes sense.
2. Inductive hypothesis . We assume that the statement is true for some value of k.
3. Induction transition . We prove that the statement is true for k+1.
4. Conclusion . If such a proof was completed, then, based on the principle of mathematical induction, it can be argued that the statement is true for any natural number n.
Let's consider the application of the method of mathematical induction to solving problems to prove the divisibility of natural numbers.
Example 1. Prove that the number 5 is a multiple of 19, where n is a natural number.
Proof:
1) Let's check that this formula is correct for n = 1: the number =19 is a multiple of 19.
2) Let this formula be true for n = k, i.e. the number is a multiple of 19.
It is a multiple of 19. Indeed, the first term is divisible by 19 due to assumption (2); the second term is also divisible by 19 because it contains a factor of 19.
Example 2. Prove that the sum of the cubes of three consecutive natural numbers is divisible by 9.
Proof:
Let us prove the statement: “For any natural number n, the expression n 3 +(n+1) 3 +(n+2) 3 is a multiple of 9.
1) Let's check that this formula is correct for n = 1: 1 3 +2 3 +3 3 =1+8+27=36 multiples of 9.
2) Let this formula be true for n = k, i.e. k 3 +(k+1) 3 +(k+2) 3 is a multiple of 9.
3) Let us prove that the formula is also true for n = k + 1, i.e. (k+1) 3 +(k+2) 3 +(k+3) 3 is a multiple of 9. (k+1) 3 +( k+2) 3 +(k+3) 3 =(k+1) 3 +(k+2) 3 + k 3 + 9k 2 +27 k+ 27=(k 3 +(k+1) 3 +(k +2) 3)+9(k 2 +3k+ 3).
The resulting expression contains two terms, each of which is divisible by 9, so the sum is divisible by 9.
4) Both conditions of the principle of mathematical induction are satisfied, therefore, the sentence is true for all values of n.
Example 3. Prove that for any natural number n, the number 3 2n+1 +2 n+2 is divisible by 7.
Proof:
1) Let's check that this formula is correct for n = 1: 3 2*1+1 +2 1+2 = 3 3 +2 3 =35, 35 is a multiple of 7.
2) Let this formula be true for n = k, i.e. 3 2 k +1 +2 k +2 is divided by 7.
3) Let us prove that the formula is also true for n = k + 1, i.e.
3 2(k +1)+1 +2 (k +1)+2 =3 2 k +1 ·3 2 +2 k +2 ·2 1 =3 2 k +1 ·9+2 k +2 ·2 =3 2 k +1 ·9+2 k +2 ·(9–7)=(3 2 k +1 +2 k +2)·9–7·2 k +2 .T. k. (3 2 k +1 +2 k +2) 9 is divided by 7 and 7 2 k +2 is divided by 7, then their difference is divided by 7.
4) Both conditions of the principle of mathematical induction are satisfied, therefore, the sentence is true for all values of n.
Many proof problems in the theory of divisibility of natural numbers can be conveniently solved using the method of mathematical induction; one can even say that solving problems with this method is completely algorithmic; it is enough to perform 4 basic steps. But this method cannot be called universal, since there are also disadvantages: firstly, it can only be proven on a set of natural numbers, and secondly, it can only be proven for one variable.
For the development of logical thinking and mathematical culture, this method is a necessary tool, because the great Russian mathematician A. N. Kolmogorov said: “Understanding and the ability to correctly apply the principle of mathematical induction is a good criterion of logical maturity, which is absolutely necessary for a mathematician.”
Literature:
1. Vilenkin N. Ya. Induction. Combinatorics. - M.: Education, 1976. - 48 p.
2. Genkin L. On mathematical induction. - M., 1962. - 36 p.
3. Solominsky I. S. Method of mathematical induction. - M.: Nauka, 1974. - 63 p.
4. Sharygin I.F. Optional course in mathematics: Problem solving: Textbook for 10th grade. school average - M.: Education, 1989. - 252 p.
5. Shen A. Mathematical induction. - M.: MTsNMO, 2007. - 32 p.