Math induction formula. Methodical development "method of mathematical induction". The principle of mathematical induction and its proof
A proof method based on Peano's axiom 4 is used to prove many mathematical properties and various statements. The basis for this is the following theorem.
Theorem. If the statement BUT(n) with natural variable n true for n= 1 and from the fact that it is true for n=k, it follows that it is also true for the next number n=k, then the statement BUT(n) n.
Proof. Denote by M the set of those and only those natural numbers for which the statement BUT(n) true. Then from the condition of the theorem we have: 1) 1 M; 2) k MkM. Hence, on the basis of Axiom 4, we conclude that M =N, i.e. statement BUT(n) true for any natural n.
The method of proof based on this theorem is called method of mathematical induction, and the axiom is the axiom of induction. This proof has two parts:
1) prove that the statement BUT(n) true for n= A(1);
2) assume that the statement BUT(n) true for n=k, and, starting from this assumption, prove that the statement A(n) true for n=k+ 1, i.e. that the statement is true A(k) A(k + 1).
If a BUT( 1) BUT(k) A(k + 1) is a true statement, then they conclude that the statement A(n) true for any natural number n.
The proof by mathematical induction can begin not only with the confirmation of the truth of the statement for n= 1, but also from any natural number m. In this case, the statement BUT(n) will be proved for all natural numbers nm.
Problem. Let's prove that for any natural number the equality 1 + 3 + 5 ... + (2 n- 1) = n.
Solution. Equality 1 + 3 + 5 ... + (2 n- 1) = n is a formula that can be used to find the sum of the first consecutive odd natural numbers. For example, 1 + 3 + 5 + 7 = 4= 16 (the sum contains 4 terms), 1 + 3 + 5 + 7 + 9 + 11 = 6= 36 (the sum contains 6 terms); if this sum contains 20 terms of the indicated type, then it is equal to 20 = 400, etc. Having proved the truth of this equality, we will be able to find the sum of any number of terms of the specified type using the formula.
1) Verify the truth of this equality for n= 1. When n= 1 the left side of the equality consists of one term equal to 1, the right side is equal to 1= 1. Since 1 = 1, then for n= 1 this equality is true.
2) Assume that this equality is true for n=k, i.e. that 1 + 3 + 5 + … + (2 k- 1) = k. Based on this assumption, we prove that it is true for n=k+ 1, i.e. 1 + 3 + 5 + ... + (2 k- 1) + (2(k + 1) - 1) = (k + 1).
Consider the left side of the last equality.
By assumption, the sum of the first k terms is k and therefore 1 + 3 + 5 + ... + (2 k- 1) + (2(k + 1) - 1) = 1 + 3 + 5 + … + (2k- 1) + (2k+ 1)=
= k+(2k + 1) = k+ 2k + 1. Expression k+ 2k + 1 is identically equal to the expression ( k + 1).
Therefore, the truth of this equality for n=k+ 1 is proven.
Thus, this equality is true for n= 1 and from its truth for n=k follows the truth for n=k+ 1.
This proves that this equality is true for any natural number.
Using the method of mathematical induction, one can prove the truth of not only equalities, but also inequalities.
A task. Prove that where nN.
Solution. Let us check the truth of the inequality for n= 1. We have - a true inequality.
Let us assume that the inequality is true for n=k, those. - true inequality. Let us prove, based on the assumption, that it is true for
n=k+ 1, i.e. 
(*).
We transform the left side of the inequality (*), taking into account that : .
But, that means 
.
So this inequality is true for n= 1, and, from the fact that the inequality is true for some n= k, we found that it is also true for n= k + 1.
Thus, using Axiom 4, we have proved that this inequality is true for any natural number.
Other assertions can also be proved by the method of mathematical induction.
A task. Prove that the statement is true for any natural number.
Solution. Let us check the truth of the statement for n= 1: -true statement.
Let us assume that this statement is true for n=k: . Let us show, using this, the truth of the statement for n=k+ 1: 
.
Let's transform the expression: . Let's find the difference k and k+ 1 members. If it turns out that the resulting difference is a multiple of 7, and by assumption the subtrahend is divisible by 7, then the minuend is also a multiple of 7:
The product is a multiple of 7, therefore, and .
Thus, this statement is true for n= 1 and from its truth for n=k follows the truth for n=k+ 1.
This proves that this statement is true for any natural number.
A task. Prove that for any natural number n 2 statement (7-1)24 is true.
Solution. 1) Check the truth of the statement for n= 2: - true statement.
The method of proof, which will be discussed in this section, is based on one of the axioms of the natural series.
Axiom of induction. Let a sentence be given that depends on the variable P, instead of which you can substitute any natural numbers. Let's denote it A(p). Let also the sentence BUT is true for the number 1 and from the fact that BUT true for number to, follows that BUT true for number k+ 1. Then offer BUT true for all natural values P.
Symbolic notation of the axiom:
Here peak- variables over the set of natural numbers. From the axiom of induction, the following inference rule is obtained: 
So, in order to prove the truth of the proposition BUT, we can first prove two statements: the truth of the statement BUT( 1), as well as the corollary A(k) => A(k+ 1).
Considering the above, we describe the entity method
mathematical induction.
Let it be required to prove that the sentence A(n) true for all natural P. The proof is divided into two stages.
- 1st stage. base of induction. We take as a value P number 1 and check that BUT( 1) is a true statement.
- 2nd stage. Inductive transition. We prove that for any natural number to the implication is true: if A(k), then A(k+ 1).
The inductive passage begins with the words: “Take an arbitrary natural number to, such that A(k)", or "Let for a natural number to right A(k)". Instead of the word "let" they often say "suppose that ...".
After these words, the letter to denotes some fixed object for which the relation holds A(k). Coming from A(k) we deduce consequences, that is, we build a chain of sentences A(k) 9 R, Pi, ..., Rn = A(k+ 1), where each sentence R, is a true statement or a consequence of the previous sentences. The last sentence R" must match with A(k+ one). From this we conclude: from A(k) should A(k+).
The execution of an inductive transition can be divided into two steps:
- 1) Inductive assumption. Here we assume that BUT to variable n.
- 2) Based on the assumption, we prove that BUT right for number?+1.
Example 5.5.1. Let's prove that the number p+p is even for all natural P.
Here A(n) = "n 2 + n- even number". It is required to prove that BUT - identically true predicate. We apply the method of mathematical induction.
base of induction. Let's take l=1. Substitute in the expression P+//, we get n 2 +n= I 2 + 1 = 2 is an even number, that is, /1(1) is a true statement.
Let's formulate inductive hypothesis A(k)= "Number to 2 + to - even." You can say this: "Take an arbitrary natural number to such that to 2 + to is an even number.
We deduce from this the assertion A(kA-)= "Number (k+ 1) 2 + (? + 1) - even.
By the properties of operations, we perform transformations:
The first term of the resulting sum is even by assumption, the second is even by definition (because it has the form 2 P). So the sum is an even number. Sentence A(k+ 1) proved.
By the method of mathematical induction, we conclude: the sentence A(n) true for all natural P.
Of course, there is no need to enter the notation every time A(p). However, it is still recommended to formulate the inductive assumption and what is required to be deduced from it in a separate line.
Note that the assertion from Example 5.5.1 can be proved without using the method of mathematical induction. To do this, it suffices to consider two cases: when P even and when P odd.
Many divisibility problems are solved by mathematical induction. Let's look at a more complex example.
Example 5.5.2. Let us prove that the number 15 2u_| +1 is divisible by 8 for all natural numbers P.
Bacha induction. Let's take /1=1. We have: number 15 2|_| +1 = 15+1 = 16 is divisible by 8.
, which for some
natural number to the number 15 2 * '+1 is divisible by 8.
Let's prove what then is the number a\u003d 15 2 (ZHN +1 is divisible by 8.
Let's convert the number a:
By assumption, the number 15 2A1 +1 is divisible by 8, which means that the entire first term is divisible by 8. The second term 224=8-28 is also divisible by 8. Thus, the number a as the difference of two numbers that are multiples of 8 is divisible by 8. The inductive step is justified.
Based on the method of mathematical induction, we conclude that for all natural P the number 15 2 "-1 -*-1 is divisible by 8.
Let us make some remarks on the solved problem.
The proved statement can be formulated a little differently: "The number 15" "+1 is divisible by 8 for any odd natural / and".
Secondly, from the proven general statement, one can draw a particular conclusion, the proof of which can be given as a separate problem: the number 15 2015 +1 is divisible by 8. Therefore, it is sometimes useful to generalize the problem by denoting a particular value by a letter, and then apply the method mathematical induction.
In the most general sense, the term "induction" means that general conclusions are made on the basis of particular examples. For example, having considered some examples of sums of even numbers 2+4=6, 2+8=10, 4+6=10, 8+12=20, 16+22=38, we conclude that the sum of any two even numbers is even number.
In the general case, such an induction can lead to incorrect conclusions. Let us give an example of such incorrect reasoning.
Example 5.5.3. Consider the number a= /r+n+41 for natural /?.
Let's find the values a for some values P.
Let n= I. Then a = 43 is a prime number.
Let /7=2. Then a= 4+2+41 = 47 is prime.
Let l=3. Then a= 9+3+41 = 53 is prime.
Let /7=4. Then a= 16+4+41 = 61 is prime.
Take as values P numbers following the quad, such as 5, 6, 7, and make sure the number a will be simple.
We conclude: “For all natural /? number a will be simple."
The result is a false statement. Here is a counterexample: /7=41. Make sure that with this P number a will be composite.
The term "mathematical induction" has a narrower meaning, since the use of this method allows you to always get the right conclusion.
Example 5.5.4. Based on inductive reasoning, we obtain a formula for the general term of an arithmetic progression. Recall that the arithmetic profession is a numerical sequence, each member of which differs from the previous one by the same number, called the progression difference. In order to uniquely specify an arithmetic profession, you need to specify its first member a and difference d.
So by definition a p+ = a n + d, at n> 1.
In the school course of mathematics, as a rule, the formula of the general term of the arithmetic profession is established on the basis of particular examples, that is, precisely by induction.
If /7=1, THEN FROM 7| = I|, THEN I am| = tf|+df(l -1).
If /7=2, then i 2 = a + d, that is a= I|+*/(2-1).
If /7=3, then i 3 = i 2 + = (a+d)+d = a+2d, i.e. i 3 = i|+(3-1).
If /7=4, then i 4 = i 3 +*/ = ( a+2d)+d\u003d R1 + 3, etc.
The given particular examples allow us to put forward a hypothesis: the general term formula has the form a" = a+(n-)d for all /7>1.
Let us prove this formula by the method of mathematical induction.
base induction verified in previous discussions.
Let to - such a number at which I * - a+(k-)d (inductive assumption).
Let's prove that I*+! = a+((k+)-)d, i.e. i*+1 = ax+kd.
By definition i*+1 = ab + d. a to= i | +(to-1 )d, means, ac+\u003d i i + (A: -1) ^ / + c / \u003d i | +(A-1+1 )d= i i +kd, which was required to prove (to justify the inductive transition).
Now the formula i„ = a+(n-)d proved for any natural number /;.
Let some sequence i b i 2 , i, „ ... (not
necessarily an arithmetic or geometric progression). Often there are problems where it is required to sum the first P members of this sequence, that is, specify the sum R|+i 2 +...+i and a formula that allows you to find the values of this sum without calculating the members of the sequence.
Example 5.5.5. Let us prove that the sum of the first P natural numbers is
/?(/7 + 1)
Denote the sum 1+2+...+/7 by Sn. Let's find the values S n for some /7.
Note that in order to find the sum S 4 , you can use the value 5 3 calculated earlier, since 5 4 = 5 3 +4.
n(n +1)
If we substitute the considered values \u200b\u200b/? in term --- something
we get, respectively, the same sums 1, 3, 6, 10. These observations
. _ n(n + 1)
suggest that the formula S„=--- can be used when
any //. Let us prove this conjecture by the method of mathematical induction.
base induction verified. Let's do it inductive transition.
Suppose that the formula is true for some natural number
, k(k + 1)
k, then the network is the sum of the first to natural numbers is ----.
Let's prove that the sum of the first (?+1) natural numbers is equal to
- (* + !)(* + 2)
Let's express?*+1 through S k . To do this, in the sum S*+i we group the first to terms, and write the last term separately:
By the inductive hypothesis S k = So to find
the sum of the first (? + 1) natural numbers, is sufficient to the already calculated
. „ k(k + 1) _ .. ..
the sum of the first to numbers equal to ---, add one term (k + 1).
The inductive transition is justified. Thus, the hypothesis put forward at the beginning is proved.
We have proved the formula S n = n ^ n+ method
mathematical induction. Of course, there is other evidence as well. For example, you can write the sum S, in ascending order of terms, and then in descending order of terms:
The sum of the terms in one column is constant (in one sum, each next term decreases by 1, and in the other increases by 1) and is equal to (/r + 1). Therefore, summing up the resulting sums, we have P terms equal to (u+1). So double the amount S „ is equal to n(n+ 1).
The formula just proved can be obtained as a special case of the formula for the sum of the first P members of an arithmetic progression.
Let us return to the method of mathematical induction. Note that the first stage of the method of mathematical induction (the base of induction) is always necessary. The absence of this step may lead to an incorrect conclusion.
Example 5.5.6. Let's "prove" the sentence: "The number 7" + 1 is divisible by 3 for any natural number ".
“Suppose that for some natural value to the number 7*+1 is divisible by 3. Let's prove that the number 7 x +1 is divisible by 3. Perform the transformations:
The number 6 is obviously divisible by 3. The number 1 to + is divisible by 3 by the inductive hypothesis, so the number 7-(7* + 1) is also divisible by 3. Therefore, the difference of numbers divisible by 3 will also be divisible by 3.
Proposal proven."
The proof of the original proposition is incorrect, despite the fact that the inductive step is correct. Indeed, at n= I have the number 8, with n=2 - the number 50, ..., and none of these numbers is divisible by 3.
Let us make an important remark about the notation of a natural number when performing an inductive transition. When formulating a proposal A(n) letter P we denoted a variable, instead of which any natural numbers can be substituted. When formulating the inductive hypothesis, we denoted the value of the variable by the letter to. However, very often instead of a new letter to use the same letter as the variable. This does not affect the structure of the reasoning when performing the inductive transition.
Let's consider a few more examples of problems for which the method of mathematical induction can be applied.
Example 5.5.7. Find the value of the sum
Variable in the task P does not appear. However, consider the sequence of terms:
Denote S, \u003d a + a 2 + ... + a „. Let's find S„ for some P. If /1= 1, then S, = a, =-.
If a n= 2. then S, = a, + a? = - + - = - = -.
If /?=3, then S-, = a,+a 7+ i, = - + - + - = - + - = - = -.
3 1 - 3 2 6 12 3 12 12 4
You can calculate the values yourself S „ at /7 = 4; 5. Arises
natural guess: S n= -- for any natural /7. Let's prove
This is by mathematical induction.
base induction checked above.
Let's do it inductive transition, denoting an arbitrary
variable value P the same letter, that is, we prove that from the equality
0 /7 _ /7 +1
S n=-follows equality S, =-.
/7+1 /7 + 2
Suppose that the equality is true S= - P -.
Let's allocate in total S„+ first P terms:
Applying the inductive assumption, we get:
Reducing the fraction by (/7+1), we will have the equality S n +1 - , L
The inductive transition is justified.
This proves that the sum of the first P terms
- 1 1 1 /7 ^
- - +-+...+- is equal to -. Now let's go back to the original
- 1-2 2-3 /?(// +1) /7 + 1
task. To solve it, it suffices to take as the value P number 99.
Then the sum -!- + -!- + -!- + ...+ --- will be equal to the number 0.99.
1-2 2-3 3-4 99100
Try to calculate this amount in a different way.
Example 5.5.8. Let us prove that the derivative of the sum of any finite number of differentiable functions is equal to the sum of the derivatives of these functions.
Let the variable /? denotes the number of given features. In the case when only one function is given, it is this function that is understood as the sum. Therefore, if /7=1, then the statement is obviously true: /" = /".
Suppose that the statement is true for a set of P functions (here again instead of the letter to letter taken P), that is, the derivative of the sum P functions is equal to the sum of derivatives.
Let's prove that the derivative of the sum of (n + 1) functions is equal to the sum of the derivatives. Take an arbitrary set consisting of n+ differentiable function: /1,/2, . Let us represent the sum of these functions
as g+f„+ 1, where g=f +/g + ... +/t- sum P functions. By the inductive hypothesis, the derivative of the function g is equal to the sum of derivatives: g" = ft + ft + ... +ft. Therefore, the following chain of equalities holds:
The inductive transition is completed.
Thus, the original proposition is proved for any finite number of functions.
In some cases, it is required to prove the truth of the proposition A(n) for all natural i, starting from some value With. The proof by mathematical induction in such cases is carried out according to the following scheme.
base of induction. We prove that the proposal BUT true for value P, equal With.
Inductive transition. 1) We assume that the proposal BUT true for some value to variable /?, which is greater than or equal to With.
2) We prove that the proposition BUT true for /? equal to
Note again that instead of the letter to often leave the variable designation P. In this case, the inductive transition begins with the words: “Suppose that for some value n>s right A(p). Let's prove that then A(n+ one)".
Example 5.5.9. Let us prove that for all natural n> 5 the inequality 2” > and 2 is true.
base of induction. Let n= 5. Then 2 5 =32, 5 2 =25. Inequality 32>25 is true.
Inductive transition. Suppose, that the inequality 2 P>n 2 for some natural number n> 5. Let's prove, which is then 2" +| > (n+1) 2 .
By properties of powers 2” +| = 2-2". Since 2" > n 2 (by the inductive hypothesis), then 2-2" > 2n 2 (I).
Let us justify that 2 p 2 greater than (i+1) 2 . This can be done in many ways. It is enough to solve the quadratic inequality 2x 2 >(x+) 2 in the set of real numbers and see that all natural numbers greater than or equal to 5 are its solutions.
We will proceed as follows. Let's find the difference of numbers 2 p 2 and (i+1) 2:
Since and > 5, then i + 1 > 6, which means (i + 1) 2 > 36. Therefore, the difference is greater than 0. So, 2i 2 > (i + 1) 2 (2).
By the properties of the inequalities, it follows from (I) and (2) that 2*2" > (n + 1) 2 , which was required to prove to justify the inductive transition.
Based on the method of mathematical induction, we conclude that the inequality 2" > i 2 is true for any natural numbers i.
Consider another form of the method of mathematical induction. The difference lies in the inductive transition. To implement it, two steps are required:
- 1) assume that the offer A(n) true for all values of the variable i less than some number R;
- 2) from the assumption made, deduce that the proposal A(n) true for number R.
Thus, the inductive step requires proof of the corollary: [(Ui?) A(n)] => A(p). Note that the corollary can be rewritten as: [(Yn^p) A(n)] => A(p+ 1).
In the original formulation of the method of mathematical induction in proving the proposition A(p) we relied only on the "previous" proposal A(p- one). The formulation of the method given here allows deriving A(p), assuming that all proposals A(n), where i am less R, are true.
Example 5.5.10. Let's prove the theorem: "The sum of the interior angles of any i-gon is 180°(i-2)".
For a convex polygon, the theorem is easy to prove if it is divided by diagonals drawn from one vertex into triangles. However, for a non-convex polygon, such a procedure may not be possible.
Let us prove the theorem for an arbitrary polygon by mathematical induction. We assume that the following assertion is known, which, strictly speaking, requires a separate proof: "In any //-gon, there is a diagonal that lies entirely in its inner part."
Instead of a variable //, you can substitute any natural numbers that are greater than or equal to 3. For n=b The theorem is true because the sum of the angles in a triangle is 180°.
Take some /7-gon (p> 4) and suppose that the sum of the angles of any //-gon, where // p, is equal to 180°(//-2). Let us prove that the sum of the angles of the //-gon is equal to 180°(//-2).
Let's draw a diagonal //-gon lying inside it. It will split the //-gon into two polygons. Let one of them have to sides, the other to 2 sides. Then k + k 2 -2 \u003d p, since the resulting polygons have a common side drawn diagonal, which is not a side of the original //-gon.
Both numbers to and to 2 less //. Let us apply the inductive assumption to the resulting polygons: the sum of the angles of the A]-gon is 180°-(?i-2), and the sum of the angles? 2-gon is equal to 180 ° - (Ar 2 -2). Then the sum of the angles of the //-gon will be equal to the sum of these numbers:
180 ° * (Ar | -2) -n 180 ° (Ar2-2) \u003d 180 o (Ar, -Ar 2 -2-2) \u003d 180 ° - (//-2).
The inductive transition is justified. Based on the method of mathematical induction, the theorem is proved for any //-gon (//>3).
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, it is given little time 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, with the help of 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 . Consequently,
the statement is true for n=1, i.e. A(1) is true.
2) Let us prove that A(k)ÞA(k+1).
Let k be any natural number and let the statement be true for n=k, i.e.
1+3+5+…+(2k-1)=k 2 .
Let us prove that then the assertion is also true for the next natural number n=k+1, i.e. what
1+3+5+…+(2k+1)=(k+1) 2 .
Indeed,
1+3+5+…+(2k-1)+(2k+1)=k 2 +2k+1=(k+1) 2 .
So A(k)ÞA(k+1). Based on the principle of mathematical induction, we conclude that Assumption A(n) is true for any nОN.
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.
In this way,
k+1 = k +(k-2)+1=k(k-3)/2+k-1=(k+1)(k-2)/2.
So A(k)ÞA(k+1). Due to the principle of mathematical induction, the statement is true for any convex n-gon.
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. MATHS: 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. In many areas of mathematics, one has to prove the truth of a statement that depends on , i.e., truth of the proposition p(n) for " nнN (for any n ON p(n) right). This can often be proven method of mathematical induction. This method is based on the principle of mathematical induction. It is usually chosen as one of the axioms of arithmetic and hence accepted without proof. According to the principle of mathematical induction, the sentence p(n) is considered true for all natural values of the variable if two conditions are met: 1. Offer p(n) true for n= 1. 2. From the sentence that p(n) true for n =k (k - arbitrary natural number) it follows that it is true for n =k+ 1. The method of mathematical induction is understood as the following method of proof 1. Check the truth of the statement for n= 1 is the base of induction. 2. Assume that the statement is true for n = k - inductive assumption. 3. Prove that then it is also true for n =k+ 1 inductive transition. Sometimes a suggestion p(n) turns out to be true not for all natural n, and starting from some for n = n 0. In this case, the truth is checked in the induction base p(n) at n = n 0. Example 1 Let . Prove that 1. Induction base: when n= 1 by definition S 1 = 1 and by the formula we get one result. The statement is correct. n=k and . n=k+ 1. Let us prove that . Indeed, by the inductive assumption Let's transform this expression The inductive transition is proved. Comment. It is useful to write down what is given (an inductive assumption) and what needs to be proved! Example 2 Prove 1. Base of induction. At n= 1, the assertion is obviously true. 2. Inductive assumption. Let n=k and 3. Inductive transition. Let n=k+ 1. Let us prove: Indeed, let's square the right side as the sum of two numbers: Using the inductive assumption and the formula for the sum of an arithmetic progression: , we obtain Example 3 Prove the inequality 1. The basis of induction in this case is the verification of the truth of the statement for , i.e. inequality needs to be checked. To do this, it suffices to square the inequality: or 63< 64 – неравенство верно. 2. Let the inequality be true for , i.e. 3. Let , prove: We use the induction hypothesis Knowing what the right side should look like in the inequality being proved, we select this part It remains to establish that the extra factor does not exceed unity. Really, Example 4 Prove that for any natural number ends with a digit. 1. The smallest natural number from which the statement is true is equal to . . 2. Let the number for end in . This means that this number can be written as , where is some natural number. Then . 3. Let . Let's prove that it ends in . Using the resulting representation, we get The last number has exactly ones. Application 1.4. Method of mathematical induction As you know, mathematical statements (theorems) must be substantiated, proven. We will now get acquainted with one of the methods of proof - the method of mathematical induction. In a broad sense, induction is a way of reasoning that allows you to move from particular statements to general ones. The reverse transition, from general statements to particular ones, is called deduction. Deduction always leads to correct conclusions. For example, we know the general result: all integers ending in zero are divisible by 5. From this, of course, we can conclude that any specific number ending in 0, such as 180, is divisible by 5. At the same time, induction can lead to incorrect conclusions. For example, noticing that the number 60 is divisible by the numbers 1, 2, 3, 4, 5, 6, we have no right to conclude that 60 is divisible by any number at all. The method of mathematical induction makes it possible in many cases to rigorously prove the validity of the general assertion P(n), the formulation of which includes a natural number n. The application of the method includes 3 stages. 1) Base of induction: we check the validity of the statement P(n) for n = 1 (or for another, private value of n, starting from which the validity of P(n) is assumed). 2) Assumption of induction: we assume that P(n) is true for n = k. 3) Step of induction: using the assumption, we prove that P(n) is true for n = k + 1. As a result, we can conclude that P(n) is valid for any n ∈ N. Indeed, for n = 1 the assertion is true (the base of the induction). And therefore, it is also true for n = 2, since the transition from n = 1 to n = 2 is justified (induction step). Applying the step of induction again and again, we obtain the validity of P(n) for n = 3, 4, 5, . . ., i.e., the validity of P(n) for all n. Example 14. The sum of the first n odd natural numbers is n2: 1 + 3 + 5 + ... + (2n - 1) = n2. The proof will be carried out by the method of mathematical induction. 1) Base: for n=1, there is only one term on the left, we get: 1 = 1. The statement is correct. 2) Assumption: we assume that for some k the equality is true: 1 + 3 + 5 + ... + (2k - 1) = k2. The general statement of the problem is as follows: The probability of hitting the target with one shot is equal to $p$. $n$ shots fired. Find the probability that the target will be hit exactly $k$ times (there will be $k$ hits). We apply the Bernoulli formula and get: $$ P_n(k)=C_n^k \cdot p^k \cdot (1-p)^(n-k) = C_n^k \cdot p^k \cdot q^(n-k). Here $C_n^k$ is the number of combinations from $n$ to $k$. If the problem involves several arrows with different probabilities hitting the target, theory, solution examples and a calculator you can find here. Watch our video on solving Bernoulli shooting problems, learn how to use Excel to solve common problems.
The Excel calculation file from the video can be downloaded for free and used to solve your problems. Let's look at a few typical examples. Example 1 Fired 7 shots. The probability of hitting with one shot is 0.705. Find the probability that there will be exactly 5 hits. We get that the problem deals with repeated independent tests (shots at the target), $n=7$ shots are fired in total, the probability of hitting with each $p=0.705$, the probability of missing $q=1-p=1-0.705=0.295 $. We need to find that there will be exactly $k=5$ hits. We substitute everything into formula (1) and get: $$ P_7(5)=C_(7)^5 \cdot 0.705^5 \cdot 0.295^2 = 21\cdot 0.705^5 \cdot 0.295^2= 0.318. $$ Example 2 The probability of hitting the target with one shot is 0.4. Four independent shots are fired at the target. Find the probability that there will be at least one hit on the target. We study the problem and write down the parameters: $n=4$ (shot), $p=0.4$ (hit probability), $k \ge 1$ (there will be at least one hit). We use the formula for the probability of the opposite event (there is no hit): $$ P_4(k \ge 1) = 1-P_4(k \lt 1) = 1-P_4(0)= $$ $$ =1-C_(4)^0 \cdot 0.4^0 \cdot 0 ,6^4 =1- 0.6^4=1- 0.13=0.87. $$ The probability of hitting at least once in four is 0.87 or 87%. Example 3 The probability of hitting the target by the shooter is 0.3. Find the probability that with 6 shots the target will be hit three to six times. Unlike the previous problems, here you need to find the probability that the number of hits will be in a certain interval (and not exactly equal to some number). But the formula is the same. Let's find the probability that the target will be hit from three to six times, that is, there will be either 3, or 4, or 5, or 6 hits. These probabilities are calculated by formula (1): $$ P_6(3)=C_(6)^3 \cdot 0.3^3\cdot 0.7^3 = 0.185. $$ $$ P_6(4)=C_(6)^4 \cdot 0.3^4\cdot 0.7^2 = 0.06. $$ $$ P_6(5)=C_(6)^5 \cdot 0.3^5\cdot 0.7^1 = 0.01. $$ $$ P_6(6)=C_(6)^6 \cdot 0.3^6\cdot 0.7^0 = 0.001. Since the events are incompatible, the desired probability can be found using the probabilities addition formula: $$ P_6(3 \le k \le 6)=P_6(3)+P_6(4)+P_6(5)+P_6(6)=$$ $$ = 0.185+0.06+0.01+0.001=0.256.$$ Example 4 The probability of at least one hit on the target with four shots is 0.9984. Find the probability of hitting the target with one shot. Let us denote the probability of hitting the target with one shot. Let's enter an event: Let us write down the formula for the probability of the event $A$. Let's write down the known values: $n=4$, $P(A)=0.9984$. Substitute in formula (1) and get: $$ P(A)=1-P(\overline(A))=1-P_4(0)=1-C_(4)^0 \cdot p^0 \cdot (1-p)^4=1- (1-p)^4=0.9984. We solve the resulting equation: $$ 1-(1-p)^4=0.9984,\\ (1-p)^4=0.0016,\\ 1-p=0.2,\\ p=0.8. $$ So, the probability of hitting the target with one shot is 0.8. Thank you for reading and sharing with others Find ready-made tasks in the solution: Online calculations using the Bernoulli formula Inequality in mathematics applies to all equations, where "=" is replaced by any of the following characters: \ [> \] \ [\geq \] \ [ * linear; * square; * fractional; * indicative; * trigonometric; * logarithmic. Depending on this, the inequalities are called linear, partial, etc. You should be aware of these signs: * inequalities with greater than (>) or less than ( * Inequalities with icons that are greater than or equal to \[\geq\] less than or equal to [\leq\] are called unprofessional; * the icon is not the same \[\ne\] alone, but cases with this icon need to be resolved all the time. Such inequality is solved by transformations of identities. Also read our article "Solve the Complete Solution for an Online Equation" Let us assume that the following inequality holds: We solve it in the same way as a linear equation, but we should carefully monitor the sign of inequality. First, we move the terms from the unknown to the left, from the known to the right, reversing the symbols: We then divide both sides by -4 and reverse the inequality sign: This is the answer to this equation. You can solve the equation on our website pocketteacher.ru. In seconds, a free online rescue solution will solve an online equation of any complexity. All you have to do is enter your details into the rescue. You can also watch video instructions and learn how to solve the equation on our website. And if you have questions, you can ask them in our Vkontakte group: pocketteacher. Join our group, we will be happy to help you. Equation Solving / Differential Equations © RU test - online calculators the equation: With the calculator you can solve differential equations of varying complexity. MBOU Lyceum "Technical and Economic"
METHOD OF MATHEMATICAL INDUCTION
METHOD OF MATHEMATICAL INDUCTION.
EXPLANATORY NOTE
The methodological development "Method of mathematical induction" was compiled for students of the 10th grade of the mathematical profile. Primary goals: to acquaint students with the method of mathematical induction and teach how to apply it in solving various problems. In the methodological development, questions of elementary mathematics are considered: divisibility problems, proof of identities, proof of inequalities, problems of varying degrees of complexity are proposed, including problems offered at olympiads. The role of inductive inferences in the experimental sciences is very great. They give those provisions, from which further conclusions are then made by deduction. Name method of mathematical induction deceptively - in fact, this method is deductive and gives a rigorous proof of the statements guessed by induction. The method of mathematical induction helps to identify links between different sections of mathematics, helps to develop the mathematical culture of the student. Definition of the method of mathematical induction. Complete and incomplete induction. Proof of inequalities. Proof of identities. Solving divisibility problems. Solving various problems on the topic "Method of mathematical induction". LITERATURE FOR THE TEACHER
1. M.L. Galitsky. In-depth study of the course of algebra and mathematical analysis. - M. Enlightenment. 1986. 2. L.I. Zvavich. Algebra and the beginnings of analysis. Didactic materials. M. Drofa. 2001. 3. N.Ya. Vilenkin. Algebra and mathematical analysis. M Enlightenment. 1995. 4. Yu.V. Mikheev. Method of mathematical induction. NGU.1995. LITERATURE FOR STUDENTS
1. N.Ya. Vilenkin. Algebra and mathematical analysis. M Enlightenment. 1995. 2. Yu.V. Mikheev. Method of mathematical induction. NGU.1995. KEYWORDS
Induction, axiom, principle of mathematical induction, complete induction, incomplete induction, assertion, identity, inequality, divisibility. DIDACTIC APPENDIX TO THE TOPIC
"METHOD OF MATHEMATICAL INDUCTION".
Lesson #1
Definition of the method of mathematical induction.
The method of mathematical induction is one of the highly effective methods for finding new results and proving the truth of the assumptions put forward. Although this method is not new in mathematics, interest in it does not wane. For the first time in a clear presentation, the method of mathematical induction was applied in the 17th century by the outstanding French scientist Blaise Pascal in proving the properties of a number triangle, which has since been named after him. However, the idea of mathematical induction was known to the ancient Greeks. The method of mathematical induction is based on the principle of mathematical induction, which is accepted as an axiom. We will consider the idea of mathematical induction with examples. Example #1.
The square is divided by a segment into two parts, then one of the resulting parts is divided into two parts, and so on. Determine how many parts the square is divided into P steps? Solution. After the first step, we, by condition, get 2 parts. In the second step, we leave one part unchanged, and divide the second into 2 parts and get 3 parts. In the third step, we leave 2 parts unchanged, and divide the third into two parts and get 4 parts. In the fourth step, we leave 3 parts unchanged, and divide the last part into two parts and get 5 parts. In the fifth step, we will get 6 parts. The suggestion is made that through P steps we get (n+1) part. But this proposition needs to be proven. Let's assume that through to steps the square is divided into (k+1) part. Then on (k+1) step we to parts will be left unchanged, and (k+1) divide the part into two parts and get (k+2) parts. You notice that you can argue like this for as long as you like, ad infinitum. That is, our assumption is that P steps square will be divided into (n+1) part, becomes proven. Example #2.
My grandmother had a granddaughter who was very fond of jam, and especially the one in a liter jar. But the grandmother did not allow him to touch. And the granddaughters decided to deceive their grandmother. He decided to eat every day 1/10 liter from this jar and top it up with water, mixing thoroughly. After how many days will grandmother discover the deception if the jam remains the same in appearance when diluted with water by half? Solution. Find how much pure jam will remain in the jar after P days. After the first day, the mixture will remain in the jar, consisting of 9/10 jam and 1/10 water. After two days, 1/10 of the mixture of water and jam will disappear from the jar and remain (1 liter of the mixture contains 9/10 liters of jam, 1/10 liters of the mixture contains 9/100 liters of jam) 9/10 - 9/100=81/100=(9/10) 2 liters of jam. On the third day, 1/10 liter of a mixture consisting of 81/100 jam and 19/100 water will disappear from the jar. In 1 liter of the mixture there are 81/100 liters of jam, in 1/10 liters of the mixture 81/1000 liters of jam. 81/100 – 81/1000= 729/1000=(9/10) 3 liters of jam will be left after 3 days, and the rest will be taken up by water. A pattern emerges. Through P days left in the bank (9/10) P l jam. But again, this is just our guess. Let to is an arbitrary natural number. Let's assume that through to days in the bank will remain (9/10) to l jam. Let's see what will be in the bank in another day, that is, in (k+1) day. Will disappear from the bank 1/10l a mixture of (9/10)
to l jam and water. AT 1l mixture is (9/10)
to l jam, in 1/10l mixtures (9/10)
k+1 l jam. Now we can safely say that through P days left in the bank (9/10)
P l jam. In 6 days the bank will have 531444/1000000l jams, after 7 days - 4782969/10000000l jam, that is, less than half. Answer: after 7 days, the grandmother will discover the deception. Let us try to single out the most basic in the solutions of the considered problems. We began to solve each of them by considering separate or, as they say, special cases. Then, based on our observations, we made some assumptions P(n), depending on the natural P.
the assertion was checked, that is, proved P(1), P(2), P(3);
suggested that P(n) valid for n=k and deduced that then it will be valid for the next n, n=k+1.
And then they argued something like this: P(1) right, P(2) right, P(3) right, P(4) right... that's right P(n).
The principle of mathematical induction.
Statement P(n), depending on the natural P, is valid for all natural P, if 1) the validity of the assertion for n=1;
2) from the assumption of the validity of the statement P(n) at n=k should justice P(n) at n=k+1.
In mathematics, the principle of mathematical induction is chosen, as a rule, as one of the axioms that define the natural series of numbers, and, therefore, is accepted without proof. The method of proof by the principle of mathematical induction is usually called the method of mathematical induction. Note that this method is widely used in proving theorems, identities, inequalities in solving divisibility problems and many other problems. Lesson #2
Complete and incomplete induction.
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." The method of proof in which we test a statement for a finite number of cases is called complete mathematical induction. This method is used relatively rarely, since statements are most often considered on infinite sets. For example, the theorem "Any even number is equal to the sum of two prime numbers" has neither been proven nor refuted so far. Even if we tested this theorem for the first billion, it would not bring us one step closer to proving it. In the natural sciences, incomplete induction is used, testing the experiment several times, transferring the result to all cases. Example #3
Guess using incomplete induction formula for the sum of cubes of natural numbers. Solution. 1 3 =1; 1 3 +2 3 =(1+2) 2 ; 1 3 +2 3 +3 3 =(1+2+3) 2 ; 1 3 +2 3 +3 3 +4 3 =(1+2+3+4) 2 ;
1 3 +2 3 +3 3 +4 3 +5 3 =(1+2+3+4+5) 2 ; …; 1 3 +2 3 +…+n 3 =(1+2+…+n) 2 . Proof. Let it be true for n=k.
Let's prove that is true for n=k+1.
Conclusion: the formula for the sum of cubes of natural numbers is true for any natural P.
Example #4
Consider the equalities and guess what general law these examples lead to. Solution. 1=0+1
2+3+4=1+8
5+6+7+8+9=8+27
10+11+12+13+14+15+16=27+64
17+18+19+20+21+22+23+24+25=64+125
……………………………………………………………..
Example #5
Write the following expressions as a sum: 1) Example #6.
Write the following sums using the sign 2) Example #7.
Write the following expressions as products: 1) 3) Example #8.
Write down the following works using the sign (capital Greek letter "pi") 1) Example #9.
Computing the value of a polynomial Is this assumption correct? Solution. If each summand is divisible by a number, then the sum is divisible by that number, The analysis of a finite number of cases plays an important role in mathematics: without giving a proof of one or another statement, it helps to guess the correct formulation of this statement, if it is not yet known. This is how Goldbach, a member of the St. Petersburg Academy of Sciences, came to the conjecture that any natural number, starting from two, is the sum of no more than three prime numbers. Lesson #3
The method of mathematical induction allows us to prove various identities. Example #10. Let us prove that for all P the identity Solution. Let's put We need to prove that Let us prove that Then from the truth of the identity By the principle of mathematical induction, the truth of the identity for all P.
Example #11.
Let's prove the identity Proof. term-by-term equalities. Lesson number 4.
Proof of identities by mathematical induction.
Example #12.
Let's prove the identity Proof. Applying the principle of mathematical induction, we proved that the equality is true for all P.
Example #13.
Let's prove the identity Proof. Applying the principle of mathematical induction, we proved that the statement is true for any natural P.
Example #14.
Let's prove the identity Proof. Example #15.
Let's prove the identity 1)
n=1;
2) for n=k
equality 3) prove that the equality holds for n=k+1:
Conclusion: the identity is valid for any natural P.
Example #16. Let's prove the identity Proof. If a n=1
, then Let the identity hold for n=k.
Let us prove that the identity holds for n=k+1.
Then the identity is valid for any natural P.
Lesson number 5.
Proof of identities by mathematical induction.
Example #17. Let's prove the identity Proof. If a n=2
, then we get the correct equality: Let the equality be true forn=k:
Let us prove the validity of the assertion for n=k+1.
According to the principle of mathematical induction, the identity is proved. Example #18.
Let's prove the identity At n=2
this identity can be rewritten in a very simple form and obviously true. Let at n=k really Let us prove the validity of the assertion forn=k+1,
that is, the equality is satisfied: . So, we have proved that the identity is true for any natural n≥2.
Example #19.
Let's prove the identity At n=1
we get the correct equality: Let's assume that at n=k we also get the correct equality: Let us prove that the validity of the equality is observed for n=k+1:
Then the identity is valid for any natural P.
Lesson number 6.
Solving divisibility problems.
Example #20. Prove by mathematical induction that Proof. At n=1
there is a division into6
without a trace, Let at n=k
expression Let us prove that when n=k+1
expression Each term is a multiple 6
, so the sum is a multiple of 6
.
Example number 21.
Proof. At n=1
expression is divisible Let at n=k
expression At n=k+1 divided by 5
.
Example #22.
Prove the divisibility of an expression Proof. At n=1 multiple 16
.
Let at n=k
At n=k+1
All terms are divisible by 16:
the first is obviously the second by assumption, and the third has an even number in brackets. Example #23.
Prove divisibility Proof. Let us first prove that At n=0
Let at n=k
Then at n=k+1 divided by 26
.
Let us now prove the assertion formulated in the condition of the problem. At n=1 divided by 676.
At n=k
it is true that At n=k+1
.
Both terms are divisible by 676
; the first is because we have proved the divisibility by 26
expression in brackets, and the second is divisible by the inductive hypothesis. Lesson number 7.
Solving divisibility problems.
Example number 24.
Prove that Proof. At n=1
At n=k
At n=k+1
each term is divisible by5
without a trace. Example #25.
Prove that Proof. At n=1
Let at n=k
At n=k+1 divided by 6
no remainder, since each term is divisible by6
without a remainder: the first term, by the inductive assumption, the second, obviously, the third, because Example #26.
Prove that Proof. Let's prove that At n=1 At n=k+1 divided by 9
.
Example number 27.
Prove that is divisible by15
without a trace. Proof. At n=1 divided by 15
.
Let at n=k divided by 15
without a trace. At n=k+1
The first term is a multiple15
by the induction hypothesis, the second term is a multiple of15
– obviously, the third term is a multiple of15
, because Lesson number 8-9.
Proof of inequalities by mathematical induction
Example #28. At n=1 we have Let at n=k At n=k+1 Then the inequality is valid for any natural P. Example #29. Prove that the inequality is true At n=1 we get the correct inequality 4 >1.
Let at n=k the inequality Let us prove that when n=k+1 the inequality For any natural to inequality is observed. If a Example #30. Let n=1 Let us assume that the inequality holds for n=k: At n=k+1 Example number 31. Prove the validity of the inequality Let us first prove that for any natural t the inequality At n=1 original inequality is true Let the inequality hold for n=k: At n=k+1 Lesson number 10.
Solving problems on the topic
Method of mathematical induction.
Example #32. Prove Bernoulli's inequality. If a Proof. At n=1
the inequality being proved takes the form Since according to the condition Because So the inequality is true for n=1, and from its truth at n=k it follows that it is true and n=k+1. Hence, by mathematical induction, it holds for all natural P.
For example, Example number 33.
Find all natural valuesP
, for which the inequality Solution. At n=1 the inequality is right. At n=2 inequality is also true. At n=3 the inequality is no longer satisfied. Only when n=6 the inequality holds, so that for the induction basis we can take n=6.
Assume that the inequality is true for some natural to:
The last inequality holds if Solving problems about the probability of hits during shots
Video Tutorial and Excel Template
Examples of solving problems on hitting the target in a series of shots
$A = $ (Of four shots, at least one will hit the target),
as well as its opposite event, which can be written as:
$\overline(A) = $ (All 4 shots will miss the target, no hits).useful links
Solving an Inequality with a Calculator
Where can I solve the inequality on the Internet?
Bernoulli Inequality Calculator
Full mathematical induction method
Solution of differential equations
Enter diff.
Examples of Solved Differential Equations
2) 
3)
; 4) 
.
Greek letter "sigma".
:
4) 
2)
f
(
n
)=
n
2
+
n
+11
, at n=1,2,3,4.5,6,7
it can be assumed that for any naturalP number f
(
n
)
simple.
is not a prime number for any natural numberP.
the truth of the identity follows 
; 
. So this identity is true for allP
.
for n≥2.
.
divided by 6
without a trace.
.
multiple6.
multiple6
.
on the5
without a trace.
.
also divided into5
without a trace.
on the16.
multiple16.
on the676.
divided by 
.
.
divided by26
.
divided by26
2
.
divided by5
without a trace.
divided by5.
divided by5
without a trace.
divided by6
without a trace.
divided by6
without a trace.
divided by6
without a trace.
even number.
when dividing by9
gives the remainder 1
.
divided by9
.
divided by 9
. Let at n=k
divided by9
.
multiple5
(proved in example No. 21), the fourth and fifth terms are also multiples5
, which is obvious, then the sum is a multiple of15
.
.
- right.
is a true inequality.
for any P.
.
at 
then
for any natural P and any 
, right.
.
for any natural P.
Multiply both sides of the inequality by 
. We obtain an equivalent inequality or 
; 
; - this inequality holds for any natural t.
; 
; 
.
.
, then for all natural valuesP
the inequality
and obviously right. Let's assume it's true forn=k
, that is, what 
.
, then 
, and therefore the inequality does not change its meaning when both its parts are multiplied by 
:
, then we get that
.
Consider the inequality
Test work on the topic n=1 is given recurrently: n≥5 , where P- -natural number.