Introduction
Main part
1. Complete and incomplete induction
2. The principle of mathematical induction
3. Method of mathematical induction
4. Solution of examples
5. Equalities
6. Division of numbers
7. 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 what useful to man they will bring those two or three lessons for which he hears five words of theory, solves five primitive problems, and, as a result, gets an A for not knowing anything.
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 представимо в виде суммы двух prime numbers. To do this, we take all such numbers and write out the corresponding expansions:4=2+2; 6=3+3; 8=5+3; 10=7+3; 12=7+5;
14=7+7; 16=11+5; 18=13+5; 20=13+7.
These nine equalities show that each of the numbers 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 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 sentence A(n) depending on the natural numbern, true forn=1 and from the fact that it is true forn=k(wherek-any natural number), it follows that it is also true for the next numbern=k+1, then assumption A(n) is true for any natural numbern.
In a number of cases, it may be necessary to prove the validity of a certain statement not for all natural numbers, but only for n>p, where p is a fixed natural number. In this case, the principle of mathematical induction is formulated as follows. If sentence A(n) is true forn=pand if A(k) Þ BUT(k+1)for anyonek>p,then sentence A(n)true for anyonen>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 (induction assumption), i.e. prove that A(k)ÞA(k+1).
EXAMPLE 1
Prove that 1+3+5+…+(2n-1)=n 2 .
Solution: 1) We have n=1=1 2 . 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.
EXAMPLE 2
Prove that
1+x+x 2 +x 3 +…+x n =(x n+1 -1)/(x-1), where x¹1
Solution: 1) For n=1 we get
1+x=(x 2 -1)/(x-1)=(x-1)(x+1)/(x-1)=x+1
therefore, for n=1 the formula is 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.
EXAMPLE 3
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 total number 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.
EXAMPLE 4
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.
EXAMPLE 5
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
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 P, 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 but\u003d 15 2 (ZHN +1 is divisible by 8.
Let's convert the number but:
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 but 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 but= /r+n+41 for natural /?.
Let's find the values but for some values P.
Let be n= I. Then a = 43 is a prime number.
Let /7=2. Then but= 4+2+41 = 47 is prime.
Let l=3. Then but= 9+3+41 = 53 is prime.
Let /7=4. Then but= 16+4+41 = 61 is prime.
Take as values P numbers following the quad, such as 5, 6, 7, and make sure the number but will be simple.
We conclude: “For all natural /? number but will be simple."
The result is a false statement. Here is a counterexample: /7=41. Make sure that with this P number but 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 but 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, i.e but= 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 but" = 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 be 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 n= 2. then S, = but, + but? = - + - = - = -.
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 from. 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 from.
Inductive transition. 1) We assume that the proposal BUT true for some value to variable /?, which is greater than or equal to from.
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 be 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).
Savelyeva Ekaterina
The paper considers the application of the method of mathematical induction in solving divisibility problems, to the summation of series. Examples of the application of the method of mathematical induction to the proof of inequalities and to the solution of geometric problems are considered. The work is illustrated with a presentation.
Download:
Preview:
Ministry of Science and Education of the Russian Federation
State educational institution
secondary school No. 618
Course: Algebra and Beginnings of Analysis
Project work topic
"Method of mathematical induction and its application to problem solving"
Work completed: Savelyeva E, 11B class
Supervisor : Makarova T.P., mathematics teacher, secondary school №618
1. Introduction.
2.Method of mathematical induction in solving divisibility problems.
3. Application of the method of mathematical induction to the summation of series.
4. Examples of application of the method of mathematical induction to the proof of inequalities.
5. Application of the method of mathematical induction to the solution of geometric problems.
6. 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. But it is so important to be able to think inductively. The application of this principle in solving problems and proving theorems is on a par with the consideration in school practice of other mathematical principles: the excluded middle, inclusion-exclusion, Dirichlet, etc. This essay contains problems from different branches of mathematics, in which the main tool is the use method of mathematical induction. Speaking about the importance of this method, A.N. Kolmogorov noted that "the understanding and ability to apply the principle of mathematical induction is a good criterion for maturity, which is absolutely necessary for a mathematician." The method of induction in its broadest sense consists in the transition from private observations to universal, general pattern or general wording. In this interpretation, the method is, of course, the main technique for conducting research in any experimental natural science.
human activity. The method (principle) of mathematical induction in its simplest form is used when it is necessary to prove a statement for all natural numbers.
Problem 1. In his article “How I Became a Mathematician” A.N. Kolmogorov writes: “I learned the joy of mathematical “discovery” early, having noticed at the age of five or six years the pattern
1 =1 2 ,
1 + 3 = 2 2 ,
1 + 3 + 5 \u003d W 2,
1 + 3 + 5 + 7 = 4 2 and so on.
The school published the magazine "Spring Swallows". In it, my discovery was published ... "
We do not know what kind of proof was given in this journal, but it all started with private observations. The very hypothesis, which probably arose after the discovery of these particular equalities, is that the formula
1 + 3 + 5 + ... + (2n - 1) = n 2
true for any given number n = 1, 2, 3, ...
To prove this conjecture, it suffices to establish two facts. First, for n = 1 (and even for n = 2, 3, 4) the desired statement is true. Second, suppose that the statement is true for n = k, and verify that then it is also true for n = k + 1:
1 + 3 + 5+…+ (2k - 1) + (2k + 1) = (1 + 3 + 5 + ... + (2k - 1)) + (2k + 1) = k 2 + (2k + 1) = (k + I) 2 .
Hence, the assertion being proved is true for all values n: for n = 1 it is true (this has been verified), and by virtue of the second fact, for n = 2, whence for n = 3 (due to the same second fact), etc.
Problem 2. Consider all possible ordinary fractions with numerator 1 and any (positive integer)
denominator: Prove that for any n> 3 can be represented as a sum P various fractions of this kind.
Solution, Let us first check this assertion for n = 3; we have:
Therefore, the basic assertion is satisfied
Suppose now that the statement of interest to us is true for some number to, and prove that it is also true for the number following it to + 1. In other words, suppose there is a representation
in which k terms and all denominators are different. Let us prove that then it is possible to obtain a representation of the unit in the form of a sum from to + 1 fractions of the desired type. We will assume that the fractions are decreasing, that is, the denominators (in the representation of the unit by the sum to terms) increase from left to right so that T is the largest of the denominators. We will get the representation we need in the form of a sum(to + 1)th fraction, if we split one fraction, for example the last one, into two. This can be done because
And therefore
In addition, all fractions remain different, since T was the biggest denominator, and t + 1 > t, and
m(t + 1) > m.
Thus, we have established:
- for n = 3 this statement is true;
- if the statement we are interested in is true for to,
then it is also true for to + 1.
On this basis, we can assert that the statement under consideration is true for all natural numbers, starting from three. Moreover, the above proof also implies an algorithm for finding the desired partition of unity. (What algorithm is this? Imagine the number 1 as the sum of 4, 5, 7 terms yourself.)
In solving the previous two problems, two steps were taken. The first step is called basis induction, the secondinductive transitionor an induction step. The second step is the most important, and it involves an assumption (the statement is true for n = k) and conclusion (the statement is true for n = k + 1). The parameter p itself is called induction parameter.This logical scheme (device), which makes it possible to conclude that the statement under consideration is true for all natural numbers (or for all, starting from some), since both the basis and the transition are valid, is calledthe principle of mathematical induction, on which and the method of mathematical induction is based.The term "induction" itself comes from the Latin word inductio (guidance), which means the transition from single knowledge about individual objects of a given class to a general conclusion about all objects of a given class, which is one of the main methods of knowledge.
The principle of mathematical induction, in the usual form of two steps, first appeared in 1654 in Blaise Pascal's Treatise on the Arithmetic Triangle, in which a simple way to calculate the number of combinations (binomial coefficients) was proved by induction. D. Poya quotes B. Pascal in the book with minor changes given in square brackets:
“Despite the fact that the proposition under consideration [an explicit formula for binomial coefficients] contains an infinite number of special cases, I will give a very short proof for it, based on two lemmas.
The first lemma states that the conjecture is true for the base - this is obvious. [At P = 1 the explicit formula is valid...]
The second lemma states the following: if our assumption is true for an arbitrary base [for an arbitrary r], then it will be true for the following base [for n + 1].
These two lemmas necessarily imply the validity of the proposition for all values P. Indeed, by virtue of the first lemma, it is valid for P = 1; therefore, by virtue of the second lemma, it is valid for P = 2; therefore, again by virtue of the second lemma, it is valid for n = 3 and so on ad infinitum.
Problem 3. The towers of Hanoi puzzle consists of three rods. On one of the rods there is a pyramid (Fig. 1), consisting of several rings of different diameters, decreasing from bottom to top
Fig 1
This pyramid must be transferred to one of the other rods, transferring only one ring each time and not placing the larger ring on the smaller one. Can it be done?
Solution. So, we need to answer the question: is it possible to move a pyramid consisting of P rings of different diameters, from one rod to another, following the rules of the game? Now the problem is, as they say, parametrized by us (a natural number P), and it can be solved by mathematical induction.
- base of induction. For n = 1, everything is clear, since a pyramid of one ring can obviously be moved to any rod.
- step of induction. Suppose that we can move any pyramids with the number of rings p = k.
Let us prove that then we can also move the pyramid mid from n = k + 1.
Pyramid from to rings lying on the largest(to + 1)-th ring, we can, according to the assumption, move to any other pivot. Let's do it. motionless(to + 1)th ring will not interfere with us to carry out the displacement algorithm, since it is the largest. After moving to rings, move this largest(to + 1)th ring onto the remaining rod. And then we again apply the moving algorithm known to us by the inductive assumption to rings, and move them to the rod with the(to + 1)th ring. Thus, if we can move the pyramids with to rings, then we can move the pyramids and to + 1 rings. Therefore, according to the principle of mathematical induction, it is always possible to move the pyramid, consisting of n rings, where n > 1.
The method of mathematical induction in solving divisibility problems.
Using the method of mathematical induction, one can prove various statements regarding the divisibility of natural numbers.
Task 4 . If n is a natural number, then the number is even.
For n=1 our statement is true: - an even number. Let's assume that is an even number. Since a 2k is an even number, so is it. So, parity is proved for n=1, parity is deduced from parity. Hence, even for all natural values of n.
Task 3. Prove that the number Z 3 + 3 - 26n - 27 with an arbitrary natural n is divisible by 26 2 without a remainder.
Solution. Let us first prove by induction an auxiliary assertion that 3 3n+3 1 is divisible by 26 with no remainder n > 0.
- base of induction. For n = 0 we have: Z 3 - 1 \u003d 26 - divided by 26.
step of induction. Suppose 3 3n + 3 - 1 is divisible by 26 when n = k, and Let us prove that in this case the assertion will be true for n = k + 1. Since 3
then from the inductive assumption we conclude that the number 3 3k + 6 - 1 is divisible by 26.
Let us now prove the assertion formulated in the condition of the problem. And again by induction.
- base of induction. It is obvious that at n = 1 statement is true: since 3 3+3 - 26 - 27 = 676 = 26 2 .
- step of induction. Let's assume that at n = k
expression 3 3k + 3 - 26k - 27 is divisible by 26 2 without remainder, and prove that the assertion is true for n = k + 1,
i.e. that number
divisible by 26 2 without a trace. In the last sum, both terms are divided without a remainder by 26 2 . The first is because we have proved that the expression in brackets is divisible by 26; the second, by the inductive hypothesis. By virtue of the principle of mathematical induction, the necessary statement is completely proved.
Application of the method of mathematical induction to the summation of series.
Task 5. Prove the formula
N is a natural number.
Solution.
For n=1, both parts of the equality turn into one and, therefore, the first condition of the principle of mathematical induction is satisfied.
Assume that the formula is true for n=k, i.e.
Let's add to both sides of this equality and transform the right side. Then we get
Thus, from the fact that the formula is true for n=k, it follows that it is true for n=k+1 as well. This statement is true for any natural value of k. So, the second condition of the principle of mathematical induction is also satisfied. The formula has been proven.
A task 6. Two numbers are written on the board: 1.1. Entering their sum between the numbers, we get the numbers 1, 2, 1. Repeating this operation again, we get the numbers 1, 3, 2, 3, 1. After three operations, the numbers will be 1, 4, 3, 5, 2, 5, 3, 4, 1. What will be the sum of all the numbers on the board after 100 operations?
Solution. Do all 100 operations would be very time consuming and time consuming. So, we need to try to find some general formula for the sum S numbers after n operations. Let's look at the table:
Did you notice any pattern here? If not, you can take one more step: after four operations, there will be numbers
1, 5, 4, 7, 3, 8, 5, 7, 2, 7, 5, 8, 3, 7, 4, 5, 1,
whose sum S 4 is 82.
In fact, you can not write out the numbers, but immediately say how the sum will change after adding new numbers. Let the sum be equal to 5. What will it become when new numbers are added? Let's split each new number into the sum of two old ones. For example, from 1, 3, 2, 3, 1 we go to 1,
1 + 3, 3, 3 + 2, 2, 2 + 3, 3, 3 + 1, 1.
That is, each old number (except for the two extreme ones) now enters the sum three times, so the new sum is 3S - 2 (subtract 2 to take into account the missing units). Therefore S 5 = 3S 4 - 2 = 244, and in general
What is the general formula? If it were not for the subtraction of two units, then each time the sum would increase three times, as in the powers of the triple (1, 3, 9, 27, 81, 243, ...). And our numbers, as you can now see, are one more. Thus, it can be assumed that
Let us now try to prove this by induction.
base of induction. See table (for n = 0, 1, 2, 3).
step of induction. Let's pretend that
Let us prove then that S to + 1 \u003d Z to + 1 + 1.
Really,
So, our formula is proven. It shows that after a hundred operations, the sum of all the numbers on the board will be equal to 3 100 + 1.
Consider one remarkable example of the application of the principle of mathematical induction, in which you first need to introduce two natural parameters and then carry out induction on their sum.
A task 7. Prove that if= 2, x 2 = 3 and for every natural n> 3
x n \u003d Zx n - 1 - 2x n - 2,
then
2 n - 1 + 1, n = 1, 2, 3, ...
Solution. Note that in this problem the initial sequence of numbers(x n ) is determined by induction, since the terms of our sequence, except for the first two, are given inductively, that is, through the previous ones. So given sequences called recurrent, and in our case this sequence is determined (by specifying its first two terms) in a unique way.
base of induction. It consists of checking two assertions: n=1 and n=2.B In both cases, the assertion is true by assumption.
step of induction. Let's assume that for n = k - 1 and n = k assertion is made, that is
Let us then prove the assertion for n = k + 1. We have:
x 1 = 3(2 + 1) - 2(2 + 1) = 2 + 1, which was to be proved.
Task 8. Prove that any natural number can be represented as the sum of several different members of the recurrent sequence of Fibonacci numbers:
for k > 2.
Solution. Let p - natural number. We will carry out induction on P.
base of induction. For n = 1 statement is true, since the unit is itself a Fibonacci number.
step of induction. Assume that all natural numbers less than some number P, can be represented as the sum of several different terms of the Fibonacci sequence. Find the largest Fibonacci number F t , not exceeding P; so F t n and F t +1 > n.
Insofar as
By the induction hypothesis, the number p- F t can be represented as a sum of 5 different members of the Fibonacci sequence, and from the last inequality it follows that all the members of the Fibonacci sequence involved in the sum of 8 are less than F t . Therefore, the expansion of the number n = 8 + F t satisfies the condition of the problem.
Examples of application of the method of mathematical induction to the proof of inequalities.
Task 9. (Bernoulli's inequality.)Prove that when x > -1, x 0, and for integer n > 2 the inequality
(1 + x) n > 1 + xn.
Solution. We will again carry out the proof by induction.
1. Base of induction. Let us verify the validity of the inequality for n = 2. Indeed,
(1 + x) 2 = 1 + 2x + x 2 > 1 + 2x.
2. Step of induction. Let's assume that for the number n = k the statement is true, that is
(1 + x) k > 1 + xk,
Where k > 2. We prove it for n = k + 1. We have: (1 + x) k + 1 = (1 + x) k (1 + x)> (1 + kx) (1 + x) =
1 + (k + 1)x + kx 2 > 1 + (k + 1)x.
So, based on the principle of mathematical induction, it can be argued that Bernoulli's inequality is valid for any n > 2.
Not always in the conditions of problems solved using the method of mathematical induction, the general law that needs to be proved is clearly formulated. Sometimes it is necessary, by observing particular cases, to first discover (guess) what general law they lead to, and only then prove the stated hypothesis by mathematical induction. In addition, the induction variable can be masked, and before solving the problem, it is necessary to determine on which parameter the induction will be carried out. As examples, consider the following tasks.
Problem 10. Prove that
for any natural n > 1.
Solution, Let's try to prove this inequality by mathematical induction.
The induction basis is easily verified:1+
By the inductive hypothesis
and it remains for us to prove that
Using the inductive hypothesis, we will assert that
Although this equality is actually true, it does not give us a solution to the problem.
Let's try to prove a stronger assertion than is required in the original problem. Namely, we will prove that
It may seem that proving this assertion by induction is hopeless.
However, at p = 1 we have: the statement is true. To justify the inductive step, suppose that
and then we will prove that
Really,
Thus, we have proved a stronger assertion, from which the assertion contained in the condition of the problem immediately follows.
The instructive thing here is that although we had to prove a stronger assertion than required in the problem, we could also use a stronger assumption in the inductive step. This explains why the straightforward application of the principle of mathematical induction does not always lead to the goal.
The situation that arose in solving the problem is calledthe inventor's paradox.The paradox itself is that more complex plans can be implemented with greater success if they are based on a deeper understanding of the essence of the matter.
Problem 11. Prove that 2m + n - 2m for any natural type.
Solution. Here we have two options. Therefore, you can try to carry out the so-calleddouble induction(an induction within an induction).
We will carry out inductive reasoning on P.
1. Base of induction according to p. For n = 1 need to check that 2 t ~ 1 > t. To prove this inequality, we use induction on T.
but) Base of induction by vol. For t = 1 in progress
equality, which is acceptable.
b) Step of induction according to t.Let's assume that at t = k statement is true, that is 2 k ~ 1 > k. Then up
Let us say that the assertion is true even if m = k + 1.
We have:
at natural k.
Thus, the inequality 2 performed for any natural T.
2. Step of induction according to itemChoose and fix some natural number T. Let's assume that at n = I the statement is true (for a fixed t), i.e. 2 t +1 ~ 2 > t1, and prove that then the assertion will be true for n = l + 1.
We have:
for any natural type.
Therefore, based on the principle of mathematical induction (according to P) the statement of the problem is true for any P and for any fixed T. Thus, this inequality holds for any natural type.
Problem 12. Let m, n and k are natural numbers, and t > p Which of the two numbers is greater:
In every expression to square root signs, t and n alternate.
Solution. Let us first prove some auxiliary assertion.
Lemma. For any natural t and n (t > n) and non-negative (not necessarily integer) X the inequality
Proof. Consider the inequality
This inequality is true, since both factors on the left side are positive. Expanding the brackets and converting, we get:
Taking the square root of both parts of the last inequality, we obtain the assertion of the lemma. So the lemma is proved.
Now let's move on to solving the problem. Let's denote the first of these numbers by but, and the second through b to . Let's prove that a for any natural to. The proof will be carried out by the method of mathematical induction separately for even and odd to.
base of induction. For k = 1 we have the inequality
y[t > y/n , which is valid due to the fact that m > n. = 2, the desired result is obtained from the proved lemma by substituting x = 0.
step of induction. Suppose, for some to the inequality a >b to fair. Let's prove that
From the assumption of induction and the monotonicity of the square root, we have:
On the other hand, it follows from the proved lemma that
Combining the last two inequalities, we get:
According to the principle of mathematical induction, the assertion is proved.
Task 13. (Cauchy's inequality.)Prove that for any positive numbers..., a p the inequality
Solution. For n = 2 the inequality
the arithmetic mean and the geometric mean (for two numbers) will be considered known. Let be n= 2, k = 1, 2, 3, ... and first carry out induction on to. The basis of this induction holds. Assuming now that the desired inequality has already been established for n = 2 , we will prove it for P = 2 . We have (using the inequality for two numbers):
Therefore, by the induction hypothesis
Thus, by induction on k, we have proved the inequality for all p 9 which are powers of two.
To prove the inequality for other values P we will use the "induction down", that is, we will prove that if the inequality is satisfied for arbitrary non-negative P numbers, it is also valid for(P - 1)th number. To verify this, we note that, according to the assumption made, for P numbers, the inequality
that is, a r + a 2 + ... + a n _ x > (n - 1) A. Dividing both parts into P - 1, we obtain the required inequality.
So, first we established that the inequality holds for an infinite number of possible values P, and then showed that if the inequality holds for P numbers, it is also valid for(P - 1) numbers. From this we now conclude that Coty's inequality holds for a set of P any non-negative numbers for any n = 2, 3, 4, ...
Problem 14. (D. Uspensky.) For any triangle ABC with angles = CAB, = CBA are commensurable, there are inequalities
Solution. The angles and are commensurable, and this (by definition) means that these angles have a common measure, for which = p, = (p, q are natural coprime numbers).
Let us use the method of mathematical induction and draw it over the sum n = p + q natural coprime numbers..
base of induction. For p + q = 2 we have: p = 1 and q = 1. Then the triangle ABC is isosceles, and the necessary inequalities are obvious: they follow from the triangle inequality
step of induction. Suppose now that the desired inequalities are established for p + q = 2, 3, ..., k - 1, where k > 2. Let us prove that the inequalities are also valid for p + q = k.
Let ABC is a given triangle with> 2. Then the sides AC and BC cannot be equal: let AC > BC. Now let's build, as in Figure 2, an isosceles triangle ABC; we have:
AC \u003d DC and AD \u003d AB + BD, therefore,
2AC > AB + BD (1)
Consider now the triangle VDC, whose angles are also comparable:
DCB = (q - p), BDC = p.
Rice. 2
This triangle satisfies the inductive hypothesis, and therefore
(2)
Adding (1) and (2), we have:
2AC+BD>
and therefore
From the same triangle WBS by the induction hypothesis we conclude that
Considering the previous inequality, we conclude that
Thus, the inductive transition is obtained, and the statement of the problem follows from the principle of mathematical induction.
Comment. The statement of the problem remains valid even when the angles a and p are not commensurable. In the basis of consideration in the general case, we already have to apply another important mathematical principle - the principle of continuity.
Problem 15. Several straight lines divide the plane into parts. Prove that it is possible to color these parts white
and black colors so that adjacent parts that have a common border segment are of different colors (as in Figure 3 when n = 4).
pic 3
Solution. We use induction on the number of lines. So let P - the number of lines dividing our plane into parts, n > 1.
base of induction. If there is only one straight(P = 1), then it divides the plane into two half-planes, one of which can be colored white and the other black, and the statement of the problem is true.
step of induction. To make the proof of the inductive step more clear, consider the process of adding one new line. If we draw the second line(P= 2), then we get four parts that can be colored in the desired way by painting the opposite corners in the same color. Let's see what happens if we draw the third straight line. It will divide some of the "old" parts, while new sections of the border will appear, on both sides of which the color is the same (Fig. 4).
Rice. 4
Let's proceed as follows:On the one sidefrom the new straight line we will change colors - we will make white black and vice versa; at the same time, those parts that lie on the other side of this straight line are not repainted (Fig. 5). Then this new coloring will satisfy the necessary requirements: on the one side of the straight line it was already alternating (but with different colors), and on the other side it was necessary. In order for the parts that have a common border belonging to the drawn line to be painted in different colors, we repainted the parts only on one side of this drawn line.
Fig.5
Let us now prove the inductive step. Suppose that for somen = kthe statement of the problem is valid, that is, all parts of the plane into which it is divided by thesetostraight, you can paint in white and black so that the neighboring parts are of different colors. Let us prove that then there exists such a coloring forP= to+ 1 straight. Let us proceed similarly to the case of transition from two straight lines to three. Let's spend on the planetodirect. Then, by the inductive assumption, the resulting "map" can be colored in the desired way. Let's spend now(to+ 1)-th straight line and on one side of it we change the colors to the opposite ones. So now(toThe + 1)-th straight line everywhere separates sections of different colors, while the "old" parts, as we have already seen, remain correctly colored. According to the principle of mathematical induction, the problem is solved.
A task16. On the edge of the desert there is a large supply of gasoline and a car that, with a full gas station, can travel 50 kilometers. In unlimited quantities, there are canisters into which you can drain gasoline from the gas tank of the car and leave it for storage anywhere in the desert. Prove that the car can travel any integer distance greater than 50 kilometers. It is not allowed to carry cans of gasoline, empty cans can be carried in any quantity.
Solution.Let's try to prove it by induction onP,that the car can drivePkilometers from the edge of the desert. AtP= 50 is known. It remains to carry out the step of induction and explain how to get theren = k+ 1 km if knownn = kkilometers can be driven.
However, here we encounter a difficulty: after we have passedtokilometers, gasoline may not even be enough for the return trip (not to mention storage). And in this case, the way out is to strengthen the assertion being proved (the inventor's paradox). We will prove that it is possible not only to drivePkilometers, but also to make an arbitrarily large supply of gasoline at a point at a distancePkilometers from the edge of the desert, being at this point after the end of transportation.
base of induction.Let a unit of gasoline be the amount of gasoline required to complete one kilometer of travel. Then a 1 kilometer trip and back requires two units of gasoline, so we can leave 48 units of gasoline in storage a kilometer from the edge and return for more. Thus, for several trips to the storage, we can make a stock of an arbitrary size that we need. At the same time, in order to create 48 units of stock, we spend 50 units of gasoline.
step of induction.Let's assume that at a distanceP= tofrom the edge of the desert you can store any amount of gasoline. Let us prove that then it is possible to create a repository at a distancen = k+ 1 km with any predetermined supply of gasoline and be at this storage at the end of the transportation. Because at the pointP= tothere is an unlimited supply of gasoline, then (according to the induction base) we can, in several trips to the pointn = k+ 1 to make a pointP= to4- 1 stock of any size you need.
The truth of a more general statement than in the condition of the problem now follows from the principle of mathematical induction.
Conclusion
In particular, having studied the method of mathematical induction, I improved 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. Solving 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.
Literature
1.Vulenkin INDUCTION. Combinatorics. Handbook FOR teachers. M., Enlightenment,
1976.-48 p.
2. Golovina L.I., Yaglom I.M. Induction in geometry. - M.: Gosud. publisher lit. - 1956 - S.I00. A manual on mathematics for applicants to universities / Ed. Yakovleva G.N. The science. -1981. - P.47-51.
3. Golovina L.I., Yaglom IM. Induction in geometry. —
M .: Nauka, 1961. - (Popular lectures on mathematics.)
4. I.T. Demidov, A.N. Kolmogorov, S.I. Shvartsburg, O.S. Ivashev-Musatov, B.E. Veits. Textbook / “Enlightenment” 1975.
5.R. Courant, G Robbins "What is Mathematics?" Chapter 1, § 2
6. Popa D. Mathematics and plausible reasoning. — M: Nauka, 1975.
7. Popa D. Mathematical discovery. — M.: Nauka, 1976.
8. Rubanov I.S. How to teach the method of mathematical induction / Mathematics school. - Nl. - 1996. - S.14-20.
9. Sominsky I.S., Golovina L.I., Yaglom I.M. On the method of mathematical induction. - M .: Nauka, 1977. - (Popular lectures on mathematics.)
10. Solominsky I.S. Method of mathematical induction. - M.: Science.
63s.
11. Solominsky I.S., Golovina L.I., Yaglom I.M. On mathematical induction. - M.: Science. - 1967. - S.7-59.
12.http://w.wikiredia.org/wiki
13.htt12:/ /www.refeshtcollestiop.ru/40 124.html
The text of the work is placed without images and formulas.
Full version work is available in the "Files of work" tab in PDF format
Introduction
This topic is relevant, since every day people solve various problems in which they use different methods of solving, but there are tasks in which the method of mathematical induction cannot be dispensed with, and in such cases knowledge in this area will be very useful.
I chose this topic for research, because in the school curriculum the method of mathematical induction is given little time, the student learns superficial information that will help him get only a general idea of \u200b\u200bthis method, but self-development will be required to study this theory in depth. It will really be useful to learn more about this topic, as it expands the horizons of a person and helps in solving complex problems.
Objective:
Get acquainted with the method of mathematical induction, systematize knowledge on this topic and apply it in solving mathematical problems and proving theorems, substantiate and clearly show the practical significance of the method of mathematical induction as a necessary factor for solving problems.
Work tasks:
Analyze the literature and summarize knowledge on the topic.
Understand the principles of mathematical induction.
Explore the application of the method of mathematical induction to problem solving.
Formulate conclusions and conclusions on the work done.
Main body of research
Origin history:
Only towards the end of the 19th century did the standard of requirements for logical rigor develop, which remains to this day dominant in practical work mathematicians on the development of individual mathematical theories.
Induction is a cognitive procedure by means of which a statement generalizing them is deduced from a comparison of available facts.
In mathematics, the role of induction is largely that it underlies the chosen axiomatics. After a long practice showed that a straight path is always shorter than a curved or broken one, it was natural to formulate an axiom: for any three points A, B and C, the inequality is satisfied.
The awareness of the method of mathematical induction as a separate important method goes back to Blaise Pascal and Gersonides, although some cases of application are found even in ancient times by Proclus and Euclid. The modern name for the method was introduced by de Morgan in 1838.
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 logically develop his thought, which means that nature itself has destined him to think inductively.
Induction and deduction
It is known that there are both particular and general statements, and the two given terms are based on the transition from one to the other.
Deduction (from lat. deductio - derivation) - the transition in the process of cognition from general knowledge to private And single. In deduction, general knowledge serves as the starting point of reasoning, and this general knowledge is assumed to be "ready", existing. The peculiarity of deduction is that the truth of its premises guarantees the truth of the conclusion. Therefore, deduction has a great power of persuasion and is widely used not only to prove theorems in mathematics, but also wherever reliable knowledge is needed.
Induction (from Latin inductio - guidance) is a transition in the process of cognition from private knowledge to general In other words, it is a method of research, knowledge, associated with the generalization of the results of observations and experiments. A feature of induction is its probabilistic nature, i.e. given the truth of the initial premises, the conclusion of the induction is only probably true, and in the final result it may turn out to be both true and false.
Complete and incomplete induction
Inductive reasoning is a form of abstract thinking in which thought develops from knowledge of a lesser degree of generality to knowledge of a greater degree of generality, and the conclusion that follows from the premises is predominantly probabilistic.
In the course of research, I found out that induction is divided into two types: complete and incomplete.
A complete induction is an inference in which a general conclusion about a class of objects is made on the basis of the study of all objects of this class.
For example, let it be required to establish that every natural even number n within 6≤ n≤ 18 can be represented as the sum of two prime numbers. To do this, we take all such numbers and write out the corresponding expansions:
6=3+3; 8=5+3; 10=7+3; 12=7+5;14=7+7; 16=11+5; 18=13+5;
These equalities show that each of the numbers of interest to us is indeed represented as the sum of two simple terms.
Consider the following example: the sequence yn= n 2 +n+17; Let's write out the first four terms: y 1 =19; y2=23; y3=29; y4=37; Then we can assume that the whole sequence consists of primes. But this is not so, let's take y 16 = 16 2 +16+17=16(16+1)+17=17*17. This is a composite number, which means our assumption is wrong, thus, incomplete induction does not lead to completely reliable conclusions, but allows us to formulate a hypothesis, which later requires mathematical proof or refutation.
Method of mathematical induction
Complete induction has only limited applications in mathematics. Many interesting mathematical statements cover an infinite number of special cases, and we cannot test for all these situations. But how to test for an infinite number of cases? This method was proposed by B. Pascal and J. Bernoulli, this is a method of mathematical induction, which is based on principle of mathematical induction.
If 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 the sentence A(n) is true for n=p and if A(k) A(k+1) for any k>p, then the sentence A(n) is true for any n>p.
Algorithm (it consists of four stages):
1.base(we show that the assertion being proved is true for some simplest special cases ( P = 1));
2.guess(we assume that the assertion is proved for the first to cases); 3 .step(under this assumption we prove the assertion for the case P = to + 1); 4.output (y statement is true for all cases, that is, for all P) .
Note that not all problems can be solved by the method of mathematical induction, but only problems parameterized by some variable. This variable is called the induction variable.
Application of the method of mathematical induction
Let's apply all this theory in practice and find out in which problems this method is used.
Problems for the proof of inequalities.
Example 1 Prove the Bernoulli inequality (1+x)n≥1+n x, x>-1, n € N.
1) For n=1, the inequality is true, since 1+х≥1+х
2) Assume that the inequality is true for some n=k, i.e.
(1+x) k ≥1+k x.
Multiplying both sides of the inequality by positive number 1+x, we get
(1+x) k+1 ≥(1+kx)(1+ x) =1+(k+1) x + kx 2
Considering that kx 2 ≥0, we arrive at the inequality
(1+x) k+1 ≥1+(k+1) x.
Thus, the assumption that Bernoulli's inequality is true for n=k implies that it is true for n=k+1. Based on the method of mathematical induction, it can be argued that Bernoulli's inequality is valid for any n ∈ N.
Example 2 Prove that for any natural number n>1, .
Let us prove using the method of mathematical induction.
Denote the left side of the inequality by.
1), therefore, for n=2 the inequality is true.
2) Let for some k. Let us prove that then and We have .
Comparing and, we have, i.e. .
For any positive integer k, the right side of the last equality is positive. That's why. But, therefore, and. We proved the validity of the inequality for n=k+1, therefore, by virtue of the method of mathematical induction, the inequality is true for any natural n>1.
Problems for the proof of identities.
Example 1 Prove that for any natural n the equality is true:
1 3 +2 3 +3 3 +…+n 3 =n 2 (n+1) 2 /4.
Let n=1, then X 1 =1 3 =1 2 (1+1) 2 /4=1.
We see that for n=1 the statement is true.
2) Suppose that the equality is true for n=kX k =k 2 (k+1) 2 /4.
3) Let us prove the truth of this statement for n=k+1, i.e. X k+1 =(k+1) 2 (k+2) 2 /4. X k+1 =1 3 +2 3 +…+k 3 +(k+1) 3 =k 2 (k+1) 2 /4+(k+1) 3 =(k 2 (k+1) 2 +4(k+1) 3)/4=(k+1) 2 (k 2 +4k+4)/4=(k+1) 2 (k+2) 2 /4.
From the above proof it is clear that the statement is true for n=k+1, therefore, the equality is true for any natural n.
Example 2 Prove that for any natural n the equality
1) Check that this identity is true for n = 1.; - right.
2) Let the identity be true for n = k as well, i.e.
3) Let us prove that this identity is also true for n = k + 1, i.e.;
Because equality is true for n=k and n=k+1, then it is true for any natural n.
Summation tasks.
Example 1 Prove that 1+3+5+…+(2n-1)=n 2 .
Solution: 1) We have n=1=1 2 . Therefore, the statement is true for n=1, i.e. A(1) is true.
2) Let us prove that А(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 the assumption A(n) is true for any n N.
Example 2 Prove the formula, n is a natural number.
Solution: When n=1, both parts of the equality turn into one and, therefore, the first condition of the principle of mathematical induction is satisfied.
Assume that the formula is true for n=k, i.e. .
Let's add to both sides of this equality and transform the right side. Then we get
Thus, from the fact that the formula is true for n=k, it follows that it is true for n=k+1, then this statement is true for any natural n.
divisibility tasks.
Example 1 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.
(23 × 133) is divisible by 133 without a remainder, so for n=1 the statement is true;
2) Suppose that (11 k+2 +12 2k+1) is divisible by 133 without a remainder.
3) Let us prove that in this case
(11 k+3 +12 2k+3) is divisible by 133 without a remainder. Indeed, 11 k+3 +12 2n+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, A(k) → A(k+1), then based on the method of mathematical induction, the statement is true for any natural n.
Example 2 Prove that 3 3n-1 +2 4n-3 for an arbitrary positive integer n is divisible by 11.
Solution: 1) Let n=1, then X 1 =3 3-1 +2 4-3 =3 2 +2 1 =11 is divisible by 11 without a remainder. 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 a remainder for any natural n.
Tasks from real life.
Example 1 Prove that the sum Sn of interior angles of any convex polygon is ( P- 2)π, where P is the number of sides of this polygon: Sn = ( P- 2)π (1).
This statement does not make sense for all natural P, but only for P > 3, since the minimum number of angles in a triangle is 3.
1) When P= 3 our statement takes the form: S 3 = π. But the sum of the interior angles of any triangle is indeed π. Therefore, when P= 3 formula (1) is true.
2) Let this formula be true for n =k, that is, S k = (k- 2)π, where k > 3. Let us prove that in this case the formula also holds: S k+ 1 = (k- 1) π.
Let A 1 A 2 ... A k A k+ 1 - arbitrary convex ( k+ 1) -gon (Fig. 338).
By connecting points A 1 and A k , we get convex k-gon A 1 A 2 ... A k — 1A k . Obviously, the sum of the angles ( k+ 1) -gon A 1 A 2 ... A k A k+ 1 equals the sum of the angles k-gon A 1 A 2 ... A k plus the sum of the angles of triangle A 1 A k A k+ one . But the sum of the angles k-gon A 1 A 2 ... A k is assumed to be ( k- 2)π, and the sum of the angles of the triangle A 1 A k A k+ 1 is equal to pi. That's why
S k+ 1=S k + π = ( k- 2)π + π = ( k- 1) π.
So, both conditions of the principle of mathematical induction are satisfied, and therefore formula (1) is true for any natural P > 3.
Example 2 There is a staircase, all the steps of which are the same. It is required to indicate the minimum number of positions that would guarantee the possibility of "climbing" any step by number.
Everyone agrees that there should be a condition. We must be able to climb the first step. Next, they must be able to climb from the first step to the second. Then in the second - on the third, etc. to the nth step. Of course, in the aggregate, "n" statements guarantee nm that we will be able to get to the nth step.
Let's now look at the 2, 3,…., n positions and compare them with each other. It is easy to see that they all have the same structure: if we got to the k step, then we can climb the (k + 1) step. From here, such an axiom for the validity of statements that depend on "n" becomes natural: if the sentence A (n), in which n is a natural number, is satisfied for n=1 and from the fact that it is satisfied for n=k (where k is any natural number), it follows that it also holds for n=k+1, then Assumption A(n) holds for any natural number n.
Appendix
Tasks using the method of mathematical induction when entering universities.
Note that upon admission to higher educational establishments There are also problems that are solved by this method. Let's consider them on specific examples.
Example 1 Prove that any natural P fair equality
1) When n=1 we get the correct equality Sin.
2) Having made the inductive assumption that for n= k equality is true, consider the sum on the left side of the equality, for n =k+1;
3) Using the reduction formulas, we transform the expression:
Then, by virtue of the method of mathematical induction, the equality is true for any natural n.
Example 2 Prove that for any natural n the value of the expression 4n +15n-1 is a multiple of 9.
1) With n=1: 2 2 +15-1=18 - multiple of 9 (because 18:9=2)
2) Let equality hold for n=k: 4k +15k-1 is a multiple of 9.
3) Let us prove that the equality holds for the next number n=k+1
4k+1 +15(k+1)-1=4k+1 +15k+15-1=4.4k +60k-4-45k+18=4(4k +15k-1)-9(5k- 2)
4(4k +15k-1) - multiple of 9;
9(5k-2) - multiple of 9;
Consequently, the entire expression 4(4 k +15k-1)-9(5k-2) is a multiple of 9, which was to be proved.
Example 3 Prove that for any natural number P condition is met: 1∙2∙3+2∙3∙4+…+ n(n+1)(n+2)=.
1) Check that this formula is true for n=1: Left side = 1∙2∙3=6.
Right part = . 6 = 6; true at n=1.
2) Assume that this formula is true for n =k:
1∙2∙3+2∙3∙4+…+k(k+1)(k+2)=. S k =.
3) Let us prove that this formula is true for n =k+1:
1∙2∙3+2∙3∙4+…+(k+1)(k+2)(k+3)=.
S k+1 =.
Proof:
So, this condition is true in two cases and proved that it is true for n =k+1, therefore it is true for any natural number P.
Conclusion
To summarize, in the process of research, I found out what induction is, which can be complete or incomplete, got acquainted with the method of mathematical induction based on the principle of mathematical induction, considered many problems using this method.
I also learned a lot of new information, different from what is included in the school curriculum. While studying the method of mathematical induction, I used various literature, Internet resources, and also consulted with a teacher.
Output: Having generalized and systematized knowledge on mathematical induction, I became convinced of the need for knowledge on this topic in reality. positive quality The method of mathematical induction is its wide application in solving problems: in the field of algebra, geometry and real mathematics. Also, this knowledge increases interest in mathematics as a science.
I am sure that the skills acquired during the work will help me in the future.
Bibliography
Sominsky I.S. Method of mathematical induction. Popular lectures on mathematics, issue 3-M.: Nauka, 1974.
L. I. Golovina, I. M. Yaglom. Induction in geometry. - Fizmatgiz, 1961. - T. 21. - 100 p. — (Popular lectures on mathematics).
Dorofeev G.V., Potapov M.K., Rozov N.Kh. Mathematics manual for applicants to universities (Selected questions of elementary mathematics) - Ed.5th, revised, 1976 - 638s.
A. Shen. Mathematical induction. - MTsNMO, 2004. - 36 p.
M.L. Galitsky, A.M. Goldman, L.I. Zvavich Collection of problems in algebra: textbook for 8-9 cells. with a deep the study of mathematics 7th ed. - M .: Education, 2001. - 271 p.
Yu.N. - M .: Pro-sve-shche-nie, 2002.
Wikipedia is the free encyclopedia.
