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).
Let us then restore the discarded circle and on one side of it, for example inside, change the color of each area to the opposite (see the second picture). It is easy to see that in this case we will get a map correctly colored with two colors, but only now for n+1 circles, which is what needed to be proved.
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 some 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 are 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 in this expression instead of x k 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.
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< 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 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 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 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. Using the method of mathematical induction, prove that for any natural n the following equalities are valid: Solution. a) When n= 1 the equality is true. Assuming the validity of the equality at n, let us show its validity even when n+ 1. Indeed, Q.E.D. b) When n= 1 the validity of the equality is obvious. From the assumption of its validity at n should Given the equality 1 + 2 + ... + n = n(n+ 1)/2, we get 1 3 + 2 3 + ... + n 3 + (n + 1) 3 = (1 + 2 + ... + n + (n + 1)) 2 , i.e. the statement is also true when n + 1. Example 1. Prove the following equalities Solution. a) When n= 1 the equality will take the form 1=1, therefore, P(1) is true. Let us assume that this equality is true, that is, it holds Thus, according to the method of mathematical induction, the original equality is valid for any natural n. Note 2. This example could have been solved differently. Indeed, the sum is 1 + 2 + 3 + ... + n is the sum of the first n terms of an arithmetic progression with the first term a 1 = 1 and difference d= 1. By virtue of the well-known formula b) When n= 1 the equality will take the form: 2 1 - 1 = 1 2 or 1=1, that is, P(1) is true. Let us assume that the equality 1 + 3 + 5 + ... + (2n - 1) = n 2 and prove that it occursP(n + 1):
1 + 3 + 5 + ... + (2n - 1) + (2(n + 1) - 1) = (n+ 1) 2 or 1 + 3 + 5 + ... + (2 n - 1) + (2n + 1) = (n + 1) 2 . Using the induction hypothesis, we obtain 1 + 3 + 5 + ... + (2n - 1) + (2n + 1) = n 2 + (2n + 1) = (n + 1) 2 . Thus, P(n+ 1) is true and, therefore, the required equality is proven. Note 3. This example can be solved (similar to the previous one) without using the method of mathematical induction. c) When n= 1 the equality is true: 1=1. Let us assume that the equality is true d) When n= 1 the equality is true: 1=1. Let us assume that it takes place Really, e) Approval P(1) true: 2=2. Let us assume that the equality Consequently, the original equality holds for any natural n. f) P(1) true: Indeed, considering that P(n) holds, we get Thus, equality is proven. g) When n= 1 we have a + b = b + a and therefore equality is fair. Let Newton's binomial formula be valid for n = k, that is, Example 2. Prove inequalities Solution. a) When n= 1 we get a true inequality 1 + a ≥ 1 + a . Let us assume that there is an inequality Indeed, since a > -1 implies a + 1 > 0, then multiplying both sides of inequality (1) by (a + 1), we obtain (1 + a) n(1 + a) ≥ (1 + n a )(1 + a ) or (1 + a ) n + 1 ≥ 1 + (n+ 1)a + n a 2 Since n a 2 ≥ 0, therefore(1 + a) n + 1 ≥ 1 + (n+ 1)a + n a 2 ≥ 1 + ( n+ 1)a . Thus, if P(n) is true, then P(n+ 1) is true, therefore, according to the principle of mathematical induction, Bernoulli’s inequality is true. b) When n= 1 we get x 1 = 1 and therefore x 1 ≥ 1 that is P(1) is a fair statement. Let's pretend that P(n) is true, that is, if adica, x 1 ,x 2 ,...,x n - n positive numbers whose product is equal to one, x 1 x 2 ·...· x n= 1, and x 1 + x 2 + ... + x n ≥ n. Let us show that this sentence entails the truth of the following: if x 1 ,x 2 ,...,x n ,x n+1 - (n+ 1) positive numbers such that x 1 x 2 ·...· x n · x n+1 = 1, then x 1 + x 2 + ... + x n + x n + 1 ≥n + 1. Consider the following two cases: 1) x 1 = x 2 = ... = x n = x n+1 = 1. Then the sum of these numbers is ( n+ 1), and the required inequality is satisfied; 2) at least one number is different from one, let, for example, be greater than one. Then, since x 1 x 2 · ... · x n · x n+ 1 = 1, there is at least one more number different from one (more precisely, less than one). Let x n+ 1 > 1 and x n < 1. Рассмотрим n positive numbers Because the (1 - x n)(x n+1 - 1) > 0, then n + x n + x n+1 - x n x n+1 = n + 1 + x n+1 (1 - x n) - 1 + x n = Note 4. The equal sign holds if and only if x 1 = x 2 = ... = x n = 1. c) Let x 1 ,x 2 ,...,x n- arbitrary positive numbers. Consider the following n positive numbers: Note 5. Equality holds if and only if x 1 = x 2 = ... = x n . d) P(1) is a fair statement: sin 2 a + cos 2 a = 1. Let us assume that P(n) is a true statement: Sin 2 n a + cos 2 n a ≤ 1 and show what happensP(n+ 1). Really, sin 2( n+ 1) a + cos 2( n+ 1) a = sin 2 n a sin 2 a + cos 2 n a cos 2 a< sin 2n a + cos 2 n a ≤ 1 (if sin 2 a ≤ 1, then cos 2 a < 1, и обратно: если cos
2 a ≤ 1, then sin 2 a < 1). Таким образом, для любого
n ABOUT N sin 2 n a + cos 2 n ≤ 1 and the equality sign is achieved only whenn = 1.
e) When n= 1 statement is true: 1< 3 / 2 . Let's assume that f) Taking into account remark 1, let's check P(10): 2 10 > 10 3, 1024 > 1000, therefore, for n= 10 the statement is true. Let's assume that 2 n > n 3 (n> 10) and prove P(n+ 1), that is 2 n+1 > (n + 1) 3 . Since when n> 10 we have or 2n 3 > n 3 + 3n 2 + 3n+ 1 or n 3 > 3n 2 + 3n + 1. Given the inequality (2 n >
n 3 ), we get 2 n+1 = 2 n·2 = 2 n + 2 n > n 3 + n 3 > n 3 + 3n 2 + 3n + 1 = (n + 1) 3 . Thus, according to the method of mathematical induction, for any natural n ABOUT N, n≥ 10 we have 2 n > n 3 . Example 3. Prove that for anyone n ABOUT N Solution. a) P(1) is a true statement (0 is divided by 6). Let P(n) is fair, that is n(2n 2 - 3n + 1) = n(n - 1)(2n- 1) is divisible by 6. Let us show that then it occurs P(n+ 1), that is, ( n + 1)n(2n+ 1) is divisible by 6. Indeed, since Thus, P(n+ 1) is a fair statement, and therefore n(2n 2 - 3n+ 1) divisible by 6 for any n ABOUT N. b) Let's check P(1): 6 0 + 3 2 + 3 0 = 11, therefore, P(1) is a fair statement. It should be proven that if 6 2 n-2 + 3 n+1 + 3 n-1 is divided by 11 ( P(n)), then 6 2 n + 3 n+2 + 3 n also divisible by 11 ( P(n+ 1)). Indeed, since 6 2n + 3 n+2 + 3 n = 6 2n-2+2 + 3 n+1+1 + 3 n-1+1 = = 6 2 6 2 n-2 + 3 3 n+1 + 3 3 n-1 = 3·(6 2 n-2 + 3 n+1 + 3 n-1) + 33 6 2 n-2 and like 6 2 n-2 + 3
n+1 + 3
n-1 and 33 6 2 n-2 are divisible by 11, then their sum is 6 2n + 3
n+2 + 3
n is divisible by 11. The statement is proven. Induction in geometry Example 4. Calculate side of correct 2 n-a triangle inscribed in a circle of radius R. METHOD OF MATHEMATICAL INDUCTION The word induction in Russian means guidance, and conclusions based on observations, experiments, i.e. are called inductive. obtained by inference from the particular to the general. For example, every day we observe that the Sun rises from the east. Therefore, you can be sure that tomorrow it will appear in the east, and not in the west. We draw this conclusion without resorting to any assumptions about the reason for the movement of the Sun across the sky (moreover, this movement itself turns out to be apparent, since the globe is actually moving). And yet this inductive conclusion correctly describes the observations we will make tomorrow. The role of inductive conclusions in experimental sciences is very great. They give those provisions from which further conclusions are then drawn through deduction. And although theoretical mechanics is based on Newton’s three laws of motion, these laws themselves were the result of deep thinking through experimental data, in particular Kepler’s laws of planetary motion, which he derived from the processing of many years of observations by the Danish astronomer Tycho Brahe. Observation and induction turn out to be useful in the future for clarifying the assumptions made. After Michelson's experiments on measuring the speed of light in a moving medium, it turned out to be necessary to clarify the laws of physics and create the theory of relativity. In mathematics, the role of induction is largely that it underlies the chosen axiomatics. After long-term practice showed that a straight path is always shorter than a curved or broken one, it was natural to formulate an axiom: for any three points A, B and C, the inequality The concept of following, which is the basis of arithmetic, also appeared from observations of the formation of soldiers, ships and other ordered sets. One should not, however, think that this exhausts the role of induction in mathematics. Of course, we should not experimentally test theorems logically deduced from axioms: if no logical errors were made during the derivation, then they are true insofar as the axioms we accepted are true. But a lot of statements can be deduced from this system of axioms. And the selection of those statements that need to be proven is again suggested by induction. It is this that allows you to separate useful theorems from useless ones, indicates which theorems may turn out to be true, and even helps to outline the path of proof. In many branches of arithmetic, algebra, geometry, and analysis, it is necessary to prove the truth of sentences A(n) depending on a natural variable. The proof of the truth of the proposition A(n) for all values of a variable can often be carried out by the method of mathematical induction, which is based on the following principle. The proposition A(n) is considered true for all natural values of the variable if the following two conditions are met: Proposition A(n) is true for n=1. From the assumption that A(n) is true for n=k (where k is any natural number), it follows that it is true for the next value n=k+1. This principle is called the principle of mathematical induction. It is usually chosen as one of the axioms defining the natural series of numbers, and is therefore accepted without proof. The method of mathematical induction means the following method of proof. If you want to prove the truth of a sentence A(n) for all natural n, then, firstly, you should check the truth of the statement A(1) and, secondly, assuming the truth of the statement A(k), try to prove that the statement A(k +1) true. If this can be proven, and the proof remains valid for each natural value of k, then, in accordance with the principle of mathematical induction, the proposition A(n) is recognized as true for all values of n. The method of mathematical induction is widely used in proving theorems, identities, inequalities, in solving divisibility problems, in solving some geometric and many other problems. divisibility Using the method of mathematical induction, you can prove various statements regarding the divisibility of natural numbers. The following statement can be proven relatively simply. Let us show how it is obtained using the method of mathematical induction. Example 1. If n is a natural number, then the number is even. When n=1 our statement is true: - an even number. Let's assume that it is an even number. Since , a 2k is an even number, then Example 2.Prove the truth of the sentence A(n)=(the number 5 is a multiple of 19), n is a natural number. Solution. The statement A(1)=(a number divisible by 19) is true. Suppose that for some value n=k A(k)=(number divisible by 19) is true. Then, since Obviously, A(k+1) is also true. Indeed, the first term is divisible by 19 due to the assumption that A(k) is true; the second term is also divisible by 19 because it contains a factor of 19. Both conditions of the principle of mathematical induction are satisfied, therefore, the proposition A(n) is true for all values of n. summing series
Example 1.Prove formula Solution. When n=1, both sides of the equality turn to one and, therefore, the first condition of the principle of mathematical induction is satisfied. Let's assume that the formula is correct for n=k, i.e. Let's add to both sides of this equality and transform the right side. Then we get Thus, from the fact that the formula is true for n=k, it follows that it is also true for n=k+1. This statement is true for any natural value of k. So, the second condition of the principle of mathematical induction is also satisfied. The formula is proven. Example 2.Prove that the sum of the first n numbers of the natural series is equal to . Solution. Let us denote the required amount, i.e. When n=1 the hypothesis is true. Let Indeed, The problem is solved. Example 3.Prove that the sum of the squares of the first n numbers of the natural series is equal to Solution. Let . Let's pretend that And finally. Example 4. Prove that . Solution. If , then Example 5. Prove that Solution. When n=1 the hypothesis is obviously true. Let . Let's prove that . Really, Examples of applying the method of mathematical induction to
proof of inequalities
Example 1.Prove that for any natural number n>1 Solution. Let us denote the left side of the inequality by . Therefore, for n=2 the inequality is true. Let for some k. Let us prove that then and . We have Comparing and , we have For any positive integer k, the right-hand side of the last equality is positive. That's why . But that means also. Example 2.Find the error in the reasoning. Statement. For any natural number n the inequality is true. Proof. . (1)
Let us prove that then the inequality is also valid for n=k+1, i.e. Indeed, no less than 2 for any natural k. Let's add to the left side of inequality (1) and to the right side 2. We get a fair inequality, or Example 3.Prove that Solution. For n=2 the inequality is true, since . Let the inequality be true for n=k, where k is some natural number, i.e. Let us show that then the inequality is also valid for n=k+1, i.e. . (2)
Indeed, by condition, , therefore the inequality is true , (3)
obtained from inequality (1) by multiplying each part by . Let us rewrite inequality (3) as follows: . Discarding the positive term on the right side of the last inequality, we obtain fair inequality (2). Example 4. Prove that (1)
where , , n is a natural number greater than 1. Solution. For n=2 inequality (1) takes the form Since , then the inequality is true . (3)
By adding to each part of inequality (3) we obtain inequality (2). This proves that for n=2 inequality (1) is true. Let inequality (1) be true for n=k, where k is some natural number, i.e. . (4)
Let us prove that then inequality (1) must also be true for n=k+1, i.e. (5)
Let's multiply both sides of inequality (4) by a+b. Since, by condition, , we obtain the following fair inequality: . (6)
In order to prove the validity of inequality (5), it is enough to show that , (7)
or, what is the same, . (8)
Inequality (8) is equivalent to inequality If , then , and on the left side of inequality (9) we have the product of two positive numbers. If , then , and on the left side of inequality (9) we have the product of two negative numbers. In both cases, inequality (9) is true. This proves that the validity of inequality (1) for n=k implies its validity for n=k+1. Method of mathematical induction applied to others
tasks The most natural application of the method of mathematical induction in geometry, close to the use of this method in number theory and algebra, is its application to solving geometric calculation problems. Let's look at a few examples. Example 1.Calculate the side of a regular square inscribed in a circle of radius R. Solution. When n=2 correct 2 n - a square is a square; his side. Further, according to the doubling formula we find that the side of a regular octagon Let us assume that the side of a regular inscribed square is expressed by formula (1). In this case, according to the doubling formula whence it follows that formula (1) is valid for all n. Example 2.How many triangles can an n-gon (not necessarily convex) be divided into by its disjoint diagonals? Solution. For a triangle, this number is equal to one (not a single diagonal can be drawn in a triangle); for a quadrilateral this number is obviously two. Suppose we already know that every k-gon, where k A n A 1 A 2 Let A 1 A k be one of the diagonals of this partition; it divides the n-gon A 1 A 2 ...A n into the k-gon A 1 A 2 ...A k and the (n-k+2)-gon A 1 A k A k+1 ...A n . Due to the assumption made, the total number of triangles in the partition will be equal to (k-2)+[(n-k+2)-2]=n-2; Thus, our statement is proven for all n. Example 3.State the rule for calculating the number P(n) of ways in which a convex n-gon can be divided into triangles by disjoint diagonals. Solution. For a triangle, this number is obviously equal to one: P(3)=1. Let us assume that we have already determined the numbers P(k) for all k Р(n)=P(n-1)+P(n-2)P(3)+P(n-3)P(4)+…+P(3)P(n-2)+P(n -1). Using this formula we consistently obtain: P(4)=P(3)+P(3)=2, P(5)=P(4)+P(3)P(3)+P(4)+5, P(6)=P(5)+P(4)P(3)+P(3)P(4)+P(5)=14 etc. You can also solve problems with graphs using the method of mathematical induction. Let there be a network of lines on the plane that connect some points and have no other points. We will call such a network of lines a map, given points as its vertices, segments of curves between two adjacent vertices - the boundaries of the map, parts of the plane into which it is divided by borders - the countries of the map. Let some map be given on the plane. We will say that it is correctly colored if each of its countries is painted with a certain color, and any two countries that have a common border are painted with different colors. Example 4.There are n circles on the plane. Prove that for any arrangement of these circles, the map they form can be correctly colored with two colors. Solution. For n=1 our statement is obvious. Let us assume that our statement is true for any map formed by n circles, and let there be n+1 circles on the plane. By removing one of these circles, we get a map that, by virtue of the assumption made, can be correctly colored with two colors, for example, black and white. Mathematical induction is the basis of one of the most common methods of mathematical proof. With its help, you can prove most of the formulas with natural numbers n, for example, the formula for finding the sum of the first terms of the progression S n = 2 a 1 + n - 1 d 2 · n, Newton's binomial formula a + b n = C n 0 · a n · C n 1 · a n - 1 · b + . . . + C n n - 1 · a · b n - 1 + C n n · b n . In the first paragraph, we will analyze the basic concepts, then consider the basics of the method itself, and then tell you how to use it to prove equalities and inequalities. Yandex.RTB R-A-339285-1 First, let's look at what induction and deduction are in general. Definition 1 Induction is a transition from the particular to the general, and deduction on the contrary – from the general to the specific. For example, we have a statement: 254 can be divided by two. From it we can draw many conclusions, including both true and false. For example, the statement that all integers that end with the number 4 can be divided by two without a remainder is true, but the statement that any number of three digits is divisible by 2 is false. In general, it can be said that with the help of inductive reasoning, many conclusions can be drawn from a single known or obvious reasoning. Mathematical induction allows us to determine how valid these conclusions are. Let's say we have a sequence of numbers like 1 1 2, 1 2 3, 1 3 4, 1 4 5, . . . , 1 n (n + 1) , where n denotes some natural number. In this case, when adding the first elements of the sequence, we get the following: S 1 = 1 1 2 = 1 2, S 2 = 1 1 2 + 1 2 3 = 2 3, S 3 = 1 1 2 + 1 2 3 + 1 3 4 = 3 4, S 4 = 1 1 · 2 + 1 2 · 3 + 1 3 · 4 + 1 4 · 5 = 4 5 , . . . Using induction, we can conclude that S n = n n + 1 . In the third part we will prove this formula. This method is based on the principle of the same name. It is formulated like this: Definition 2 A certain statement will be true for a natural value n when 1) it will be true for n = 1 and 2) from the fact that this expression is valid for an arbitrary natural value n = k, it follows that it will be true for n = k + 1 . The application of the method of mathematical induction is carried out in 3 stages: Let's take the example we talked about earlier. Example 1 Prove the formula S n = 1 1 · 2 + 1 2 · 3 + . . . + 1 n (n + 1) = n n + 1 . Solution
As we already know, to apply the method of mathematical induction, three sequential actions must be performed. We can represent k + 1 as the sum of the first terms of the original sequence and k + 1: S k + 1 = S k + 1 k + 1 (k + 2) Since in the second action we received that S k = k k + 1, we can write the following: S k + 1 = S k + 1 k + 1 (k + 2) . Now we perform the necessary transformations. We will need to reduce the fraction to a common denominator, reduce similar terms, apply the abbreviated multiplication formula and reduce what we get: S k + 1 = S k + 1 k + 1 (k + 2) = k k + 1 + 1 k + 1 (k + 2) = = k (k + 2) + 1 k + 1 (k + 2) = k 2 + 2 k + 1 k + 1 (k + 2) = (k + 1) 2 k + 1 (k + 2) = k + 1 k + 2 Thus, we have proven the equality in the third point by completing all three steps of the method of mathematical induction. Answer: the assumption about the formula S n = n n + 1 is correct. Let's take a more complex problem with trigonometric functions. Example 2 Give a proof of the identity cos 2 α · cos 4 α · . . . · cos 2 n α = sin 2 n + 1 α 2 n sin 2 α . Solution
As we remember, the first step should be to check the validity of the equality when n equals one. To find out, we need to remember the basic trigonometric formulas. cos 2 1 = cos 2 α sin 2 1 + 1 α 2 1 sin 2 α = sin 4 α 2 sin 2 α = 2 sin 2 α cos 2 α 2 sin 2 α = cos 2 α Therefore, for n equal to one, the identity will be true. Now let’s assume that its validity remains true for n = k, i.e. it will be true that cos 2 α · cos 4 α · . . . · cos 2 k α = sin 2 k + 1 α 2 k sin 2 α . We prove the equality cos 2 α · cos 4 α · . . . · cos 2 k + 1 α = sin 2 k + 2 α 2 k + 1 sin 2 α for the case when n = k + 1, taking the previous assumption as a basis. According to the trigonometric formula, sin 2 k + 1 α cos 2 k + 1 α = = 1 2 (sin (2 k + 1 α + 2 k + 1 α) + sin (2 k + 1 α - 2 k + 1 α)) = = 1 2 sin (2 2 k + 1 α) + sin 0 = 1 2 sin 2 k + 2 α Hence, cos 2 α · cos 4 α · . . . · cos 2 k + 1 α = = cos 2 α · cos 4 α · . . . · cos 2 k α · cos 2 k + 1 α = = sin 2 k + 1 α 2 k sin 2 α · cos 2 k + 1 α = 1 2 · sin 2 k + 1 α 2 k sin 2 α = sin 2 k + 2 α 2 k + 1 sin 2 α We gave an example of solving a problem to prove an inequality using this method in the article about the least squares method. Read the paragraph where formulas for finding approximation coefficients are derived. If you notice an error in the text, please highlight it and press Ctrl+Enter
A) 
;
b) 
.
, we get
1/3 = 1/3. Let there be equality P(n):a) Bernoulli inequality: (1 + a) n ≥ 1 + n a , a > -1, n ABOUT N.
b) x 1 + x 2 + ... + x n ≥ n, If x 1 x 2 · ... · x n= 1 and x i > 0, .
c) Cauchy's inequality with respect to the arithemetic mean and the geometric mean
Where x i > 0, , n ≥ 2.
d) sin 2 n a + cos 2 n a ≤ 1, n ABOUT N.
e)
f) 2 n > n 3 , n ABOUT N, n ≥ 10.
and we will show that then it takes place and(1 + a) n + 1 ≥ 1 + (n+ 1)a . (1 + a) n ≥ 1 + n a (1)
= n + 1 + x n+1 (1 - x n) - (1 - x n) = n + 1 + (1 - x n)(x n+1 - 1) ≥ n+ 1. Therefore, x 1 + x 2 + ... + x n + x n+1 ≥ n+1, that is, if P(n) is true, thenP(n+ 1) fair. The inequality has been proven.
and we will prove that
considering P(n), we get 
, follows that
The essence of the method of mathematical induction
The method of mathematical induction in solving problems on
even. So, parity is proven for n=1, parity is deduced from parity 
.This means that it is even for all natural values of n.
Application of the method of mathematical induction to
, n is a natural number.
.
.
. Let's show that 
.
.
.
. Then
.
, .
, i.e. 
.
.
. The statement has been proven.
, where >-1, , n is a natural number greater than 1.
. (1)
. (2)
. (9)
, side of a regular hexagon 
, side of a regular thirty-two triangle 
. We can therefore assume that the side of the correct inscribed 2 n - square for any equal
. (1)
,
Concepts of induction and deduction
What is the method of mathematical induction?
How to use the method of mathematical induction to solve inequalities and equations