Method of mathematical induction
Introduction
Main part
- Complete and incomplete induction
- Principle of mathematical induction
- Method of mathematical induction
- Solution of examples
- Equality
- Number division
- inequalities
Conclusion
List of used literature
Introduction
Deductive and inductive methods are the basis of any mathematical research. The deductive method of reasoning is reasoning from the general to the particular, i.e. reasoning, the starting point of which is the general result, and the final point is the particular result. Induction is applied when passing from particular results to general ones, i.e. is the opposite of the deductive method.
The method of mathematical induction can be compared with progress. We start from the lowest, as a result of logical thinking we come to the highest. Man has always striven for progress, for the ability to develop his thought logically, which means that nature itself has destined him to think inductively.
Although the field of application of the method of mathematical induction has grown, little time is devoted to it in the school curriculum. Well, say that a useful person will be brought by those two or three lessons for which he hears five words of theory, solves five primitive problems, and, as a result, gets a five for knowing nothing.
But this is so important - to be able to think inductively.
Main part
In its original meaning, the word "induction" is applied to reasoning by which general conclusions are obtained based on a number of particular statements. The simplest method of reasoning of this kind is complete induction. Here is an example of such reasoning.
Let it be required to establish that every natural even number n within 4< n < 20 представимо в виде суммы двух простых чисел. Для этого возьмём все такие числа и выпишем соответствующие разложения:
4=2+2; 6=3+3; 8=5+3; 10=7+3; 12=7+5;
14=7+7; 16=11+5; 18=13+5; 20=13+7.
These nine equalities show that each of the numbers of interest to us is indeed represented as the sum of two prime terms.
Thus, complete induction is that the general statement is proved separately in each of a finite number of possible cases.
Sometimes the general result can be predicted after considering not all, but rather a large number of special cases (the so-called incomplete induction).
The result obtained by incomplete induction, however, remains only a hypothesis until it is proved by exact mathematical reasoning, covering all special cases. In other words, incomplete induction in mathematics is not considered a legitimate method of rigorous proof, but is a powerful method for discovering new truths.
Let, for example, it is required to find the sum of the first n consecutive odd numbers. Consider special cases:
1+3+5+7+9=25=5 2
After considering these few special cases, the following general conclusion suggests itself:
1+3+5+…+(2n-1)=n 2
those. the sum of the first n consecutive odd numbers is n 2
Of course, the observation made cannot yet serve as a proof of the validity of the above formula.
Complete induction has only limited applications in mathematics. Many interesting mathematical statements cover an infinite number of special cases, and we cannot test 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.
Let it be necessary to prove the validity of a certain statement for any natural number n (for example, it is necessary to prove that the sum of the first n odd numbers is equal to n 2). A direct verification of this statement for each value of n is impossible, since the set of natural numbers is infinite. To prove this statement, first check its validity for n=1. Then it is proved that for any natural value of k, the validity of the statement under consideration for n=k implies its validity for n=k+1 as well.
Then the assertion is considered proven for all n. Indeed, the statement is true for n=1. But then it is also valid for the next number n=1+1=2. The validity of the assertion for n=2 implies its validity for n=2+
1=3. This implies the validity of the statement for n=4, and so on. It is clear that, in the end, we will reach any natural number n. Hence, the statement is true for any n.
Summarizing what has been said, we formulate the following general principle.
The principle of mathematical induction.
If the sentence A(n), which depends on a natural number n, is true for n=1, and from the fact that it is true for n=k (where k is any natural number), it follows that it is also true for the next number n=k +1, then Assumption A(n) is true for any natural number n.
In a number of cases, it may be necessary to prove the validity of a certain statement not for all natural numbers, but only for n>p, where p is a fixed natural number. In this case, the principle of mathematical induction is formulated as follows.
If proposition A(n) is true for n=p and if A(k)ÞA(k+1) for any k>p, then proposition A(n) is true for any n>p.
The proof by the method of mathematical induction is carried out as follows. First, the assertion to be proved is checked for n=1, i.e., the truth of the statement A(1) is established. This part of the proof is called the induction basis. This is followed by a part of the proof called the induction step. In this part, the validity of the statement for n=k+1 is proved under the assumption that the statement is true for n=k (the inductive assumption), i.e. prove that A(k)ÞA(k+1).
Prove that 1+3+5+…+(2n-1)=n 2 .
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 assertion is also true for the next natural number n=k+1, i.e. what
1+3+5+…+(2k+1)=(k+1) 2 .
Indeed,
1+3+5+…+(2k-1)+(2k+1)=k 2 +2k+1=(k+1) 2 .
So A(k)ÞA(k+1). Based on the principle of mathematical induction, we conclude that Assumption A(n) is true for any nОN.
Prove that
1+x+x 2 +x 3 +…+x n =(x n+1 -1)/(x-1), where x¹1
Solution: 1) For n=1 we get
1+x=(x 2 -1)/(x-1)=(x-1)(x+1)/(x-1)=x+1
therefore, for n=1 the formula is true; A(1) is true.
2) Let k be any natural number and let the formula be true for n=k, i.e.
1 + x + x 2 + x 3 + ... + x k \u003d (x k + 1 -1) / (x-1).
Let us prove that then the equality
1+x+x 2 +x 3 +…+x k +x k+1 =(x k+2 -1)/(x-1).
Indeed
1+х+х 2 +x 3 +…+х k +x k+1 =(1+x+x 2 +x 3 +…+x k)+x k+1 =
=(x k+1 -1)/(x-1)+x k+1 =(x k+2 -1)/(x-1).
So A(k)ÞA(k+1). Based on the principle of mathematical induction, we conclude that the formula is true for any natural number n.
Prove that the number of diagonals of a convex n-gon is n(n-3)/2.
Solution: 1) For n=3, the statement is true
And 3 is correct, because in a triangle
A 3 =3(3-3)/2=0 diagonals;
A 2 A(3) is true.
2) Suppose that in any
convex k-gon has-
A 1 sya A k \u003d k (k-3) / 2 diagonals.
A k Let us prove that then in a convex
(k+1)-gon number
diagonals A k+1 =(k+1)(k-2)/2.
Let А 1 А 2 А 3 …A k A k+1 -convex (k+1)-angle. Let's draw a diagonal A 1 A k in it. To count the total number of diagonals of this (k + 1)-gon, you need to count the number of diagonals in the k-gon A 1 A 2 ...A k , add k-2 to the resulting number, i.e. the number of diagonals of the (k+1)-gon emanating from the vertex A k+1 , and, in addition, the diagonal A 1 A k should be taken into account.
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 statement is true:
1 2 +2 2 +3 2 +…+n 2 =n(n+1)(2n+1)/6.
Solution: 1) Let n=1, then
X 1 \u003d 1 2 \u003d 1 (1 + 1) (2 + 1) / 6 \u003d 1.
Hence, for n=1 the statement is true.
2) Assume that n=k
X k \u003d k 2 \u003d k (k + 1) (2k + 1) / 6.
3) Consider this statement for n=k+1
Xk+1 =(k+1)(k+2)(2k+3)/6.
X k+1 =1 2 +2 2 +3 2 +…+k 2 +(k+1) 2 =k(k+1)(2k+1)/6+ +(k+1) 2 =(k (k+1)(2k+1)+6(k+1) 2)/6=(k+1)(k(2k+1)+
6(k+1))/6=(k+1)(2k 2 +7k+6)/6=(k+1)(2(k+3/2)(k+
2))/6=(k+1)(k+2)(2k+3)/6.
We have proved the validity of the equality for n=k+1, therefore, by virtue of the method of mathematical induction, the statement is true for any natural n.
Prove that for any natural n the equality is true:
1 3 +2 3 +3 3 +…+n 3 =n 2 (n+1) 2 /4.
Solution: 1) Let n=1.
Then X 1 =1 3 =1 2 (1+1) 2 /4=1.
We see that for n=1 the statement is true.
2) Assume that the equality is true for n=k
X k \u003d k 2 (k + 1) 2 / 4.
3) Let us prove the truth of this statement for n=k+1, i.e.
X k+1 =(k+1) 2 (k+2) 2 /4. X k+1 =1 3 +2 3 +…+k 3 +(k+1) 3 =k 2 (k+1) 2 /4+(k+1) 3 =(k 2 (k++1) 2 +4(k+1) 3)/4=(k+1) 2 (k 2 +4k+4)/4=(k+1) 2 (k+2) 2 /4.
From the above proof it is clear that the statement is true for n=k+1, therefore, the equality is true for any natural n.
Prove that
((2 3 +1)/(2 3 -1))´((3 3 +1)/(3 3 -1))´…´((n 3 +1)/(n 3 -1))= 3n(n+1)/2(n 2 +n+1), where n>2.
Solution: 1) For n=2 the identity looks like: (2 3 +1)/(2 3 -1)=(3´2´3)/2(2 2 +2+1),
those. it is correct.
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) We will prove the correctness of the expression for n=k+1.
(((2 3 +1)/(2 3 -1))´…´((k 3 +1)/(k 3 -1)))´(((k+1) 3 +
1)/((k+1) 3 -1))=(3k(k+1)/2(k 2 +k+1))´((k+2)((k+
1) 2 -(k+1)+1)/k((k+1) 2 +(k+1)+1))=3(k+1)(k+2)/2´
´((k+1) 2 +(k+1)+1).
We have proved the validity of the equality for n=k+1, therefore, due to the method of mathematical induction, the statement is true for any n>2
Prove that
1 3 -2 3 +3 3 -4 3 +…+(2n-1) 3 -(2n) 3 =-n 2 (4n+3)
for any natural n.
Solution: 1) Let n=1, then
1 3 -2 3 =-1 3 (4+3); -7=-7.
2) Assume that n=k, then
1 3 -2 3 +3 3 -4 3 +…+(2k-1) 3 -(2k) 3 =-k 2 (4k+3).
3) Let's prove the truth of this statement for n=k+1
(1 3 -2 3 +…+(2k-1) 3 -(2k) 3)+(2k+1) 3 -(2k+2) 3 =-k 2 (4k+3)+
+(2k+1) 3 -(2k+2) 3 =-(k+1) 3 (4(k+1)+3).
The validity of the equality for n=k+1 is also proved, therefore the statement is true for any natural number n.
Prove the validity of the identity
(1 2 /1´3)+(2 2 /3´5)+…+(n 2 /(2n-1)´(2n+1))=n(n+1)/2(2n+1)
for any natural n.
1) For n=1 the identity is true 1 2 /1´3=1(1+1)/2(2+1).
2) Assume that for n=k
(1 2 /1´3)+…+(k 2 /(2k-1)´(2k+1))=k(k+1)/2(2k+1).
3) 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).
It can be seen from the above proof that the assertion is true for any natural number n.
Prove that (11 n+2 +12 2n+1) is divisible by 133 without remainder.
Solution: 1) Let n=1, then
11 3 +12 3 \u003d (11 + 12) (11 2 -132 + 12 2) \u003d 23´133.
But (23´133) is divisible by 133 without a remainder, so for n=1 the statement is true; A(1) is true.
2) 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 2k+3 =11´11 k+2 +12 2´ 12 2k+1 =11´11 k+2 +
+(11+133)´12 2k+1 =11(11 k+2 +12 2k+1)+133´12 2k+1 .
The resulting sum is divisible by 133 without a remainder, since its first term is divisible by 133 without a remainder by assumption, and in the second one of the factors is 133. So, А(k)ÞА(k+1). By virtue of the method of mathematical induction, the assertion is proved.
Prove that for any n 7 n -1 is divisible by 6 without remainder.
Solution: 1) Let n=1, then X 1 =7 1 -1=6 is divided by 6 without a remainder. So for n=1 the statement is true.
2) Assume 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. So 7 n -1 is a multiple of 6 for any natural n. By virtue of the method of mathematical induction, the assertion is proved.
Prove that 3 3n-1 +2 4n-3 for arbitrary natural n is divisible by 11.
Solution: 1) Let n=1, then
X 1 \u003d 3 3-1 +2 4-3 \u003d 3 2 +2 1 \u003d 11 is divided by 11 without a remainder. Hence, for n=1 the statement is true.
2) Assume that for n=k
X k \u003d 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. Hence, the sum is also divisible by 11 without remainder for any natural n. By virtue of the method of mathematical induction, the assertion is proved.
Prove that 11 2n -1 for an arbitrary positive integer n is divisible by 6 without a remainder.
Solution: 1) Let n=1, then 11 2 -1=120 is divisible by 6 without a remainder. So for n=1 the statement is true.
2) Assume 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 number 120, and the second is divisible by 6 without a remainder by assumption. So the sum is divisible by 6 without a remainder. By virtue of the method of mathematical induction, the assertion is proved.
Prove that 3 3n+3 -26n-27 for an arbitrary positive integer n is divisible by 26 2 (676) without a remainder.
Solution: Let us first prove that 3 3n+3 -1 is divisible by 26 without a remainder.
- For n=0
- Suppose that for n=k
- Let us prove that the statement
3 3 -1=26 is divisible 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 3k+3 +(3 3k+3 -1) – divisible by 26
Now let us prove the assertion formulated in the condition of the problem.
1) It is obvious that for n=1 the statement is true
3 3+3 -26-27=676
2) Assume that for n=k
the expression 3 3k+3 -26k-27 is divisible by 26 2 without a remainder.
3) Let's prove that the statement is true for n=k+1
3 3k+6 -26(k+1)-27=26(3 3k+3 -1)+(3 3k+3 -26k-27).
Both terms are divisible by 26 2 ; the first is divisible by 26 2 because we have proved that the expression in the brackets is divisible by 26, and the second is divisible by the inductive hypothesis. By virtue of the method of mathematical induction, the assertion is proved.
Prove that if n>2 and x>0, then the inequality
(1+x) n >1+n´x.
Solution: 1) For n=2, the inequality is true, since
(1+x) 2 =1+2x+x 2 >1+2x.
So A(2) is true.
2) Let us prove that A(k)ÞA(k+1) if k> 2. Suppose 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.
Indeed, multiplying both sides of inequality (3) by a positive number 1+x, we obtain
(1+x) k+1 >(1+k´x)(1+x).
Consider the right side of the last unequal
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 valid 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) For m=1
(1+a+a 2) 1 > 1+a+(2/2)´a 2 both parts are equal.
2) Assume that for m=k
(1+a+a 2) k >1+k´a+(k(k+1)/2)´a 2
3) Let us prove that for m=k+1 the non-equality is true
(1+a+a 2) k+1 =(1+a+a 2)(1+a+a 2) k >(1+a+a 2)(1+k´a+
+(k(k+1)/2)´a 2)=1+(k+1)´a+((k(k+1)/2)+k+1)´a 2 +
+((k(k+1)/2)+k)´a 3 +(k(k+1)/2)´a 4 > 1+(k+1)´a+
+((k+1)(k+2)/2)´a 2 .
We have proved the validity of the inequality for m=k+1, therefore, by virtue of the method of mathematical induction, the inequality is true for any natural m.
Prove that for n>6 the inequality
3 n >n´2 n+1 .
Solution: Let's rewrite the inequality in the form
- For n=7 we have
- Suppose that for n=k
3 7 /2 7 =2187/128>14=2´7
the inequality is true.
3) Let us prove the correctness of the inequality for n=k+1.
3k+1 /2k+1 =(3k /2k)´(3/2)>2k´(3/2)=3k>2(k+1).
Since k>7, the last inequality is obvious.
By virtue of the method of mathematical induction, the inequality is valid for any natural n.
Prove that for n>2 the inequality
1+(1/2 2)+(1/3 2)+…+(1/n 2)<1,7-(1/n).
Solution: 1) For n=3 the inequality is true
1+(1/2 2)+(1/3 2)=245/180<246/180=1,7-(1/3).
- Suppose that for n=k
1+(1/2 2)+(1/3 2)+…+(1/k 2)=1.7-(1/k).
3) We will prove the validity of the non-
equalities 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)Û
w(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 non-equality is proved. Conclusion In particular, having studied the method of mathematical induction, I increased my knowledge in this area of mathematics, and also learned how to solve problems that were previously beyond my power. Basically, these were logical and entertaining tasks, i.e. just those that increase interest in mathematics itself as a science. The solution of such problems becomes an entertaining activity and can attract more and more inquisitive people to the 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, TASKS, SOLUTIONS Textbook / V. G. Boltyansky, Yu. V. Sidorov, M. I. Shabunin. Potpourri LLC 1996. ALGEBRA AND THE PRINCIPLES OF ANALYSIS Textbook / I.T. Demidov, A.N. Kolmogorov, S.I. Shvartsburg, O.S. Ivashev-Musatov, B.E. Veits. "Enlightenment" 1975. Lecture 6. Method of mathematical induction. New knowledge in science and life is obtained in different ways, but all of them (if you do not go into details) are divided into two types - the transition from the general to the particular and from the particular to the general. The first is deduction, the second is induction. Deductive reasoning is what is usually called in mathematics logical reasoning, and in mathematical science deduction is the only legitimate method of investigation. The rules of logical reasoning were formulated two and a half millennia ago by the ancient Greek scientist Aristotle. He created a complete list of the simplest correct reasoning, syllogisms– "bricks" of logic, at the same time pointing out typical reasoning, very similar to the right ones, but wrong (we often meet with such "pseudological" reasoning in the media). Induction (induction - in Latin guidance) is illustrated by the well-known legend of how Isaac Newton formulated the law of universal gravitation after an apple fell on his head. Another example from physics: in such a phenomenon as electromagnetic induction, an electric field creates, “induces” a magnetic field. "Newton's apple" is a typical example of a situation where one or more special cases, i.e. observations, "lead" to a general statement, the general conclusion is made on the basis of particular cases. The inductive method is the main one for obtaining general patterns in both natural and human sciences. But it has a very significant drawback: on the basis of particular examples, an incorrect conclusion can be drawn. Hypotheses arising from private observations are not always correct. Consider an example due to Euler. We will calculate the value of the trinomial for some first values n: Note that the numbers obtained as a result of calculations are prime. And one can directly verify that for each n 1 to 39 polynomial value Leibniz proved in the 17th century that for every positive integer n number The considered examples allow us to draw an important conclusion: a statement can be true in a number of special cases and at the same time unjust in general. The question of the validity of the statement in the general case can be solved by applying a special method of reasoning called by mathematical induction(complete induction, perfect induction). 6.1. The principle of mathematical induction. ♦ The method of mathematical induction is based on principle of mathematical induction
, consisting of the following: 1) the validity of this statement is verified forn=1
(induction basis)
,
2) this statement is assumed to be true forn=
k, wherekis an arbitrary natural number 1(induction assumption)
, and taking into account this assumption, its validity is established forn=
k+1.
Proof.
Assume the opposite, that is, suppose that the assertion is not true for every natural n. Then there is such a natural m, what: 1) approval for n=m not fair, 2) for everyone n, smaller m, the assertion is true (in other words, m is the first natural number for which the assertion fails). It's obvious that m>1, because for n=1 the statement is true (condition 1). Hence, Note that the proof used the axiom that any collection of natural numbers contains the smallest number. A proof based on the principle of mathematical induction is called by complete mathematical induction
.
Example6.1.
Prove that for any natural n number Decision. 1) When n=1 , so a 1 is divisible by 3 and the statement is true for n=1. 2) Assume that the statement is true for n=k,
Indeed, Because each term is divisible by 3, then their sum is also divisible by 3. ■
Example6.2.
Prove that the sum of the first n natural odd numbers is equal to the square of their number, that is, . Decision. We use the method of complete mathematical induction. 1) We check the validity of this statement for n=1: 1=1 2 is correct. 2) Suppose that the sum of the first k
( We use our assumption and get .
■
The method of complete mathematical induction is used to prove some inequalities. Let us prove Bernoulli's inequality. Example6.3.
Prove that when Decision. 1) When n=1 we get 2) We assume that at n=k there is an inequality Multiply both parts of the inequality (*) by the number That is (1+ Proof by method incomplete mathematical induction
some assertion depending on n, where Some problems do not explicitly formulate a statement that can be proved by mathematical induction. In such cases, it is necessary to establish a regularity and express a hypothesis about the validity of this regularity, and then test the proposed hypothesis by the method of mathematical induction. Example6.4.
Find the amount Decision. Let's find the sums S 1 ,
S 2 ,
S 3 . We have 1) When n=1 the hypothesis is true, because 2) Assume that the hypothesis is true for n=k,
Indeed, So, assuming that the hypothesis is true for n=k,
Example6.5.
In mathematics, it is proved that the sum of two uniformly continuous functions is a uniformly continuous function. Based on this statement, we need to prove that the sum of any number Decision. The basis of induction here is contained in the very formulation of the problem. Making the inductive assumption, consider This proves the assertion and will use it further. ■
Example6.6.
Find all natural n, for which the inequality Decision. Consider n=1, 2, 3, 4, 5, 6. We have: 2 1 >1 2 , 2 2 =2 2 , 2 3<3 2 ,
2 4 =4 2 ,
2 5 >5 2 , 2 6 >6 2 . Thus, we can make a hypothesis: the inequality 1) As stated above, this hypothesis is true for n=5. 2) Suppose it is true for n=k,
T. to. then we get that From pp. 1 and 2, based on the principle of incomplete mathematical induction, it follows that the inequality Example6.7.
Prove that for any natural number n the differentiation formula is valid Decision. At n=1 this formula has the form Q.E.D. ■
Example6.8.
Prove that the set consisting of n elements, has Decision. A set with one element a, has two subsets. This is true because all its subsets are the empty set and the set itself, and 2 1 =2. We assume that any set of n elements has The set B consists of n elements, and therefore, by the induction hypothesis, it has But in the second class there are the same number of subsets: each of them is obtained from exactly one subset of the first class by adding the element d. Therefore, in total, the set A Thus the assertion is proved. Note that it is also valid for a set consisting of 0 elements - an empty set: it has a single subset - itself, and 2 0 =1. ■
To do this, first check the truth of the statement with number 1 - induction base, and then it is proved that if the statement with the number n, then the following assertion with the number n + 1 - induction step, or inductive transition. The proof by induction can be visualized in the form of the so-called domino principle. Let any number of dominoes be placed in a row in such a way that each domino, falling, necessarily overturns the next domino (this is the inductive transition). Then, if we push the first bone (this is the base of induction), then all the bones in the row will fall. The logical basis for this method of proof is the so-called axiom of induction, the fifth of the Peano axioms that define the natural numbers. The correctness of the method of induction is equivalent to the fact that in any subset of natural numbers there is a minimum element. There is also a variation, the so-called principle of complete mathematical induction. Here is its strict wording: The principle of complete mathematical induction is also equivalent to the axiom of induction in Peano's axioms. Task. Prove that, whatever the natural n and real q≠ 1, the equality Proof. Induction on n. Base, n = 1: Transition: Let's pretend that Q.E.D. Comment: fidelity of the statement P n in this proof is the same as the validity of the equality Wikimedia Foundation. 2010 . Mathematical induction in mathematics is one of the proof methods. Used to prove the truth of some statement for all natural numbers. To do this, first the truth of the statement with number 1 is checked, the base of induction, and then ... ... Wikipedia A method of constructing a theory, in addition, it is based on some of its provisions - axioms or postulates - from which all other provisions of the theory (theorem) are derived by reasoning, called proofs m i. Rules, by the way ... ... Philosophical Encyclopedia Induction (Latin inductio guidance) is the process of inference based on the transition from a particular position to a general one. Inductive reasoning connects private premises with the conclusion not so much through the laws of logic, but rather through some ... ... Wikipedia GENETIC METHOD- a way to set the content and essence of the object under study not by convention, idealization or logical conclusion, but by studying its origin (based on the study of the reasons that led to its occurrence, the mechanism of formation). Wide... ... Philosophy of Science: Glossary of Basic Terms A method of constructing a scientific theory, in which it is based on some initial propositions (judgments) of an axiom (See Axiom), or Postulates, from which all other statements of this science (theorems (See Theorem)) must be derived ... ... Great Soviet Encyclopedia axiomatic method- AXIOMATIC METHOD (from the Greek axioma) the accepted position is a method of constructing a scientific theory, in which only axioms, postulates and statements previously derived from them are used in the evidence. Shown for the first time... Encyclopedia of Epistemology and Philosophy of Science One of the error theory methods for estimating unknown quantities from measurement results containing random errors. N. c. m. is also used for an approximate representation of a given function by other (simpler) functions and often turns out to be ... Mathematical Encyclopedia Mathematical induction is one of the methods of mathematical proof, used to prove the truth of some statement for all natural numbers. To do this, first check ... Wikipedia This term has other meanings, see Induction. Induction (Latin inductio guidance) is the process of inference based on the transition from a particular position to a general one. Inductive reasoning connects private premises ... ... Wikipedia Induction is a method of obtaining a general statement from particular observations. In the case when a mathematical statement concerns a finite number of objects, it can be proved by checking 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 realistic 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. The method of proof, in which a statement is verified for a finite number of cases, exhausting all possibilities, is called complete induction. This method is relatively rarely applicable, 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 refuted. Mathematical induction is a method of proving a certain statement for any natural n based on the principle of mathematical induction: “If a statement is true for n=1 and from its validity for n=k it follows that this statement is true 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: prove or directly verify 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 n=k and, based on this assumption, prove the validity of the statement for n=k+1. 1. Prove that for any natural n the number 3 2n+1 +2 n+2 is divisible by 7. Denote A(n)=3 2n+1 +2 n+2 . base of induction. If n=1, then A(1)=3 3 +2 3 =35 and obviously divisible by 7. Induction hypothesis. Let A(k) be divisible by 7. inductive 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. А(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 n. 2. Prove that for any positive integer n the number 2 3 n +1 is divisible by 3 n+1 and is 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 , i.e. 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 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 is not divisible by 3 k+3 . Therefore, the assertion is proved for any natural n. 3. It is known that x+1/x is an integer. Prove that х n +1/х n is also an integer for any integer n. Let's introduce the notation: a i \u003d x i +1 / x i and immediately note that a i \u003d a -i, so we will continue to talk about natural indices. Note: and 1 is an integer by condition; a 2 is an integer, since a 2 \u003d (a 1) 2 -2; and 0=2. Assume that a k is an integer for any positive integer 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, and n–1 is an integer by the induction hypothesis. Hence, а n+1 is also an integer. Therefore, х n +1/х n is an integer for any integer n, which was to be proved. 4. Prove that for any positive integer n greater than 1, the double inequality 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 \u003d 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 is proved for any natural number n > 1. 6. There are n circles on the plane. Prove that for any arrangement of these circles, the map formed by them can be correctly colored with two colors. Let's use the method of mathematical induction. For n=1 the assertion is obvious. Assume that the statement is true for any map formed by n circles, and let n + 1 circles be given on the plane. Removing one of these circles, we get a map that, by virtue of the assumption made, can be correctly colored with two colors (see the first figure below). We 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 get a map correctly colored with two colors, but only now with n + 1 circles, which was 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 neighboring vertices are painted in different colors; 3) at least one vertex of the polygon is colored in each of the three colors. Prove that any beautiful n-gon can be cut by non-intersecting diagonals into "beautiful" triangles. Let's use the method of mathematical induction. base of induction. For the least 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 hypothesis. Let us assume that the statement of the problem is true for any "beautiful" n-gon. induction step. Consider an arbitrary "beautiful" (n + 1)-gon and prove, using the inductive assumption, that it can be cut by some diagonals into "beautiful" triangles. Denote by А 1 , А 2 , А 3 , … А n , А n+1 – successive vertices of the (n+1)-gon. If only one vertex of the (n + 1)-gon is colored in any of the three colors, then by connecting this vertex with diagonals to all vertices 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 painted in each of the three colors, then we denote the color of the vertex A 1 by the number 1, and the color of the vertex A 2 by the number 2. Let k be the smallest number such that the vertex A k is colored in the third color. It is clear that k > 2. Let us cut off the triangle А k–2 А k–1 А k from the (n+1)-gon with the diagonal А k–2 А 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, due to 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 by 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 assertion is obvious. Let us assume that this assertion is true for an arbitrary n-gon and, using this, prove its validity for an arbitrary (n + 1)-gon. Assume that for an (n + 1)-gon this statement is not true. If no more than two chosen sides or diagonals emerge from each vertex of an (n+1)-gon, then there are at most n+1 of them chosen. Therefore, at least three chosen sides or diagonals AB, AC, AD emerge from some vertex A. Let AC lie between AB and AD. Since any side or diagonal that comes out of C other than CA cannot cross AB and AD at the same time, only one chosen diagonal CA comes out of C. Discarding the point C along with the diagonal CA, we get a convex n-gon in which more than n sides and diagonals are chosen, any two of which have a common point. Thus, we arrive at a contradiction with the assumption that the assertion is true for an arbitrary convex n-gon. So, for an (n + 1)-gon, the statement is true. In accordance with the principle of mathematical induction, the statement is true for any convex n-gon. 9. There are n lines drawn in the plane, no two of which are parallel and no three pass through the same point. Into how many parts do these lines divide the plane. With the help of elementary drawings, it is easy to make sure 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. Denote by N(n) the number of parts into which n lines divide the plane. It can be seen 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 by the method of mathematical induction. For n=1, the formula has already been verified. Having made the inductive assumption, consider k + 1 lines satisfying the condition of the problem. We arbitrarily select k straight lines from them. By the inductive hypothesis, they partition the plane into 1+ k(k+1)/2 parts. The remaining (k + 1)-th line will be divided by selected k lines into k + 1 parts and, therefore, will pass through 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, k+1 more parts 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, brackets 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 arranging brackets? First of all, it is clear that in the resulting fraction x 1 will be in the numerator. It is almost equally obvious that x 2 will be in the denominator for any arrangement of brackets (the division sign before x 2 refers either to x 2 itself, or to any 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 way. 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 be independently of the others in the numerator or denominator. Let us prove this assertion by induction. With n=3, you can get 2 fractions: so the statement is true. We assume that it is valid for n=k and prove it for n=k+1. Let the expression x 1: x 2: ...: x k, after some arrangement of brackets, be written as a fraction Q. If x k: x k+1 is substituted into this expression instead of x k, then x k will be in the same place as it was in fractions Q, and x k + 1 will not be where x k stood (if x k was in the denominator, then x k + 1 will be in the numerator and vice versa). Now let's prove that we can add x k+1 to the same place as x k . 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 is x k x k+1 . Thus, the number of possible fractions in the case of n=k+1 is 2 times greater than in the case of n=k and is equal to 2 k–2 ·2=2 (k+1)–2 . Thus the assertion is proved. Answer: 2 n-2 fractions. 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; f) 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|sinx| 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. Using the method of mathematical induction, prove that for any natural n the following equalities are true: Decision. a) When n= 1 equality is valid. Assuming the validity of equality for n, let us show that it is also valid for n+ 1. Indeed, Q.E.D. b) When n= 1 the validity of the equality is obvious. From the assumption of its fairness 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 for n + 1. Example 1 Prove the following equalities Decision. a) When n= 1 equality will take the form 1=1, therefore, P(1) true. Let us assume that this equality is true, that is, we have Thus, according to the method of mathematical induction, the original equality is valid for any natural n. Remark 2. This example could be solved in another way. Indeed, the sum 1 + 2 + 3 + ... + n is the sum of the first n members of an arithmetic progression with the first member a 1 = 1 and difference d= 1. By virtue of the well-known formula b) When n= 1 equality will take the form: 2 1 - 1 = 1 2 or 1=1, that is, P(1) true. Let us assume that the equality 1 + 3 + 5 + ... + (2n - 1) = n 2 and prove thatP(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 get 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 proved. Remark 3. This example can be solved (similarly to the previous one) without using the method of mathematical induction. c) When n= 1 the equality is true: 1=1. Assume that the equality is true d) When n= 1 equality is valid: 1=1. Let's assume that there is Really, e) Approval P(1) true: 2=2. Let's assume that the equality Therefore, the original equality holds for any natural n. f) P(1) true: Indeed, given that P(n) takes place, we get Thus, the equality is proved. g) When n= 1 we have a + b = b + a and hence the equality is true. Let Newton's binomial formula be valid for n = k, i.e, Example 2 Prove inequalities Decision. a) When n= 1 we obtain the 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 Because 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 i.e. 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 proposition implies that the following is true: 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 other number that is different from one (more precisely, less than one). Let be x n+ 1 > 1 and x n < 1. Рассмотрим n positive numbers Insofar as (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 = Remark 4. The equal sign occurs if and only if x 1 = x 2 = ... = x n = 1. c) Let x 1 ,x 2 ,...,x n are arbitrary positive numbers. Consider the following n positive numbers: Remark 5. Equality holds if and only if x 1 = x 2 = ... = x n . d) P(1) - a fair statement: sin 2 a + cos 2 a = 1. Suppose that P(n) is a true statement: Sin 2 n a + cos2 n a ≤ 1 and show that there isP(n+ 1). Really, sin2( n+ 1) a + cos 2( n+ 1) a \u003d sin 2 n a sin 2 a + cos 2 n a cos 2 a< sin 2n a + cos2 n a ≤ 1 (if sin 2 a ≤ 1, then cos 2 a < 1, и обратно: если cos
2 a ≤ 1, then sin 2 a < 1). Таким образом, для любого
n O N sin 2 n a + cos2 n ≤ 1 and the equal sign is reached only whenn = 1.
e) When n= 1 the statement is true: 1< 3 / 2 . Let's assume that f) Taking Remark 1 into account, we check P(10): 2 10 > 10 3 , 1024 > 1000, therefore, for n= 10 the statement is true. Suppose 2 n > n 3 (n> 10) and prove P(n+ 1), i.e. 2 n+1 > (n + 1) 3 . Since at n> 10 we have or 2n 3 > n 3 + 3n 2 + 3n+ 1 or n 3 > 3n 2 + 3n + 1. Taking into account 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 O N, n≥ 10 we have 2 n > n 3 . Example 3 Prove that for any n O N Decision. a) P(1) is a true statement (0 is divisible by 6). Let be 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 we have 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) is divisible by 6 for any n O N. b) Check P(1): 6 0 + 3 2 + 3 0 = 11, hence P(1) is a fair statement. It should be proved that if 6 2 n-2 + 3 n+1 + 3 n-1 is divisible by 11 ( P(n)), then 6 2 n + 3 n+2 + 3 n is 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 assertion is proved. Induction in geometry Example 4 Calculate the side of the correct 2 n-gon inscribed in a circle of radius R.
is a prime number. However, when n=40 we get the number 1681=41 2 , which is not prime. Thus, the hypothesis that could arise here, that is, the hypothesis that for each n number 
is simple, turns out to be false.
divisible by 3 
is divisible by 5, and so on. Based on this, he suggested that for every odd k and any natural n number 
divided by k, but soon noticed that 
is not divisible by 9.
- natural number. It turns out that for a natural number 
the statement is true, and for the next natural number m it is unfair. This contradicts condition 2. ■
is divisible by 3.
, that is, that number 
is divisible by 3 and find that n=k+1 number is divisible by 3.
) of odd numbers is equal to the square of the number of these numbers, that is, . Based on this equality, we establish that the sum of the first k+1 odd numbers is equal to 
, i.e .
and any natural n the inequality 
(Bernoulli's inequality).
, which is correct.
(*). Using this assumption, we prove that 
. Note that when 
this inequality holds, and therefore it suffices to consider the case 
.
and get:
.■
carried out in a similar way, but at the beginning, justice is established for the smallest value n.
.
,
,
. We hypothesize that for any natural n the formula is valid 
. To test this hypothesis, we use the method of complete mathematical induction.
.
, i.e 
. Using this formula, we establish that the hypothesis is true and for n=k+1, that is
, it is proved that it is true for n=k+1, and based on the principle of mathematical induction, we conclude that the formula is valid for any natural n.
■
of uniformly continuous functions is a uniformly continuous function. But since we have not yet introduced the concept of "uniformly continuous function", let's set the problem more abstractly: let it be known that the sum of two functions that have some property S, itself has the property S. Let us prove that the sum of any number of functions has the property S.
functions f 1 ,
f 2 ,
…, f n ,
f n+1 that have the property S. Then . On the right side, the first term has the property S by the induction hypothesis, the second term has the property S by condition. Therefore, their sum has the property S– for two terms, the basis of induction “works”.
.
has a place for everyone 
. To prove the truth of this hypothesis, we use the principle of incomplete mathematical induction.
, that is, the inequality 
. Using this assumption, we prove that the inequality 
.
and at 
there is an inequality 
at 
,
. So, the truth of the hypothesis n=k+1 follows from the assumption that it is true for n=k,
.
true for every natural 
.
■
.
, or 1=1, that is, it is true. Making the inductive assumption, we have:
subsets.
subsets. If the set A consists of n+1 elements, then we fix one element in it - denote it d, and divide all subsets into two classes - not containing d and containing d. All subsets from the first class are subsets of the set B obtained from A by removing the element d.
subsets, so in the first class 
subsets.
subsets.Examples
,
see also
Variations and Generalizations
Literature
See what the "Method of mathematical induction" is in other dictionaries:
Problems with solutions
Problems without solutions
a) 
;
b) 
.
, we get
1/3 = 1/3. Let there be equality P(n):a) Bernoulli's inequality: (1 + a ) n ≥ 1 + n a , a > -1, n O 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 arithmetic mean and the geometric mean
where x i > 0, , n ≥ 2.
d) sin 2 n a + cos2 n a ≤ 1, n O N.
e)
f) 2 n > n 3 , n O N, n ≥ 10.
and show that then we have(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) is fair. The inequality has been proven.
and prove that
Considering P(n), we get 
, follows that
