Mathematical induction underlies one of the most common methods of mathematical proofs. With its help, you can prove most of the formulas with natural numbers n, for example, the formula for finding the sum of the first terms of the progression S n \u003d 2 a 1 + n - 1 d 2 n, Newton's binomial formula a + b n \u003d C n 0 a n C n 1 a n - 1 b + . . . + C n n - 1 a b n - 1 + C n n b n .
In the first paragraph, we will analyze the basic concepts, then we will consider the basics of the method itself, and then we will tell you how to use it to prove equalities and inequalities.
Concepts of induction and deduction
First, let's look at what induction and deduction are in general.
Definition 1
Induction is the transition from the particular to the general, and deduction on the contrary, from the general to the particular.
For example, we have a statement: 254 can be divided into two completely. From it we can draw many conclusions, among which there will be both true and false. For example, the statement that all integers that have the number 4 at the end can be divided by two without a remainder is true, but that any number of three digits is divisible by 2 is false.
In general, it can be said that with the help of inductive reasoning one can get many conclusions from one known or obvious reasoning. Mathematical induction allows us to determine how valid these conclusions are.
Suppose we have a sequence of numbers like 1 1 2 , 1 2 3 , 1 3 4 , 1 4 5 , . . . , 1 n (n + 1) , where n denotes some natural number. In this case, when adding the first elements of the sequence, we get the following:
S 1 \u003d 1 1 2 \u003d 1 2, S 2 \u003d 1 1 2 + 1 2 3 \u003d 2 3, S 3 \u003d 1 1 2 + 1 2 3 + 1 3 4 \u003d 3 4, S 4 = 1 1 2 + 1 2 3 + 1 3 4 + 1 4 5 = 4 5 , . . .
Using induction, we can conclude that S n = n n + 1 . In the third part we will prove this formula.
What is the method of mathematical induction
This method is based on the principle of the same name. It is formulated like this:
Definition 2
A certain statement will be true for a natural value n when 1) it will be true for n = 1 and 2) from the fact that this expression is true for an arbitrary natural value n = k, it follows that it will also be true for n = k + 1 .
The application of the method of mathematical induction is carried out in 3 stages:
- First, we check the correctness of the original statement in the case of an arbitrary natural value of n (usually the test is done for unity).
- After that, we check the fidelity at n = k .
- And then we prove the validity of the statement if n = k + 1 .
How to apply the method of mathematical induction when solving inequalities and equations
Let's take the example we talked about earlier.
Example 1
Prove the formula S n = 1 1 2 + 1 2 3 + . . . + 1 n (n + 1) = n n + 1 .
Solution
As we already know, to apply the method of mathematical induction, three consecutive steps must be performed.
- First, we check whether this equality will be valid for n equal to one. We get S 1 \u003d 1 1 2 \u003d 1 1 + 1 \u003d 1 2. Everything is correct here.
- Further, we make the assumption that the formula S k = k k + 1 is correct.
- In the third step, we need to prove that S k + 1 = k + 1 k + 1 + 1 = k + 1 k + 2 , based on the validity of the previous equality.
We can represent k + 1 as the sum of the first terms of the original sequence and k + 1:
S k + 1 = S k + 1 k + 1 (k + 2)
Since in the second step we got that S k = k k + 1, we can write the following:
S k + 1 = S k + 1 k + 1 (k + 2) .
Now we perform the necessary transformations. We will need to reduce the fraction to a common denominator, reduce like terms, apply the abbreviated multiplication formula and reduce what happened:
S k + 1 = S k + 1 k + 1 (k + 2) = k k + 1 + 1 k + 1 (k + 2) = = k (k + 2) + 1 k + 1 (k + 2) = k 2 + 2 k + 1 k + 1 (k + 2) = (k + 1) 2 k + 1 (k + 2) = k + 1 k + 2
Thus, we have proved the equality in the third point by performing all three steps of the method of mathematical induction.
Answer: the assumption about the formula S n = n n + 1 is correct.
Let's take a more complex problem with trigonometric functions.
Example 2
Give a proof of the identity cos 2 α · cos 4 α · . . . cos 2 n α \u003d sin 2 n + 1 α 2 n sin 2 α.
Solution
As we remember, the first step should be to check the correctness of equality when n is equal to one. To find out, we need to remember the basic trigonometric formulas.
cos 2 1 = cos 2 α sin 2 1 + 1 α 2 1 sin 2 α = sin 4 α 2 sin 2 α = 2 sin 2 α cos 2 α 2 sin 2 α = cos 2 α
Therefore, for n equal to one, the identity will be true.
Now suppose that its validity is preserved for n = k , i.e. it will be true that cos 2 α · cos 4 α · . . . cos 2 k α \u003d sin 2 k + 1 α 2 k sin 2 α.
We prove the equality cos 2 α · cos 4 α · . . . cos 2 k + 1 α = sin 2 k + 2 α 2 k + 1 sin 2 α for the case when n = k + 1, based on the previous assumption.
According to the trigonometric formula,
sin 2 k + 1 α cos 2 k + 1 α = = 1 2 (sin (2 k + 1 α + 2 k + 1 α) + sin (2 k + 1 α - 2 k + 1 α)) = = 1 2 sin (2 2 k + 1 α) + sin 0 = 1 2 sin 2 k + 2 α
Consequently,
cos 2 α cos 4 α . . . · cos 2 k + 1 α = = cos 2 α · cos 4 α · . . . cos 2 k α cos 2 k + 1 α = = sin 2 k + 1 α 2 k sin 2 α cos 2 k + 1 α = 1 2 sin 2 k + 1 α 2 k sin 2 α = sin 2 k + 2 α 2 k + 1 sin 2 α
An example of solving the problem of proving an inequality using this method, we have given in an article about the method least squares. Read the paragraph in which the formulas for finding the approximation coefficients are derived.
If you notice a mistake in the text, please highlight it and press Ctrl+Enter
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.
Proof by mathematical induction can begin not only with 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.
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.
AT 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 contributes to the identification of connections between various 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 which one common law give these examples.
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) 
2) 
3)
; 4) 
.
Greek letter "sigma".
Example #6.
Write the following sums using the sign 
:
2) 
Example #7.
Write the following expressions as products:
1) 
3) 
4) 
Example #8.
Write down the following works using the sign 
(capital Greek letter "pi")
1) 
2)
Example #9.
Computing the value of a polynomial 
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 this assumption correct?
Solution.
If each summand is divisible by a number, then the sum is divisible by that number, 
is not a prime number for any natural numberP.
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 at most three primes.
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
the truth of the identity follows 
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.
; 
. So this identity is true for allP
.
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 
for n≥2.
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
divided by 6
without a trace.
Proof.
At n=1
there is a division into6
without a trace, 
.
Let at n=k
expression 
multiple6.
Let us prove that when n=k+1
expression 
multiple6
.
Each term is a multiple 6 , so the sum is a multiple of 6 .
Example number 21.
on the5
without a trace.
Proof.
At n=1
expression is divisible 
.
Let at n=k
expression 
also divided into5
without a trace.
At n=k+1 divided by 5 .
Example #22.
Prove the divisibility of an expression 
on the16.
Proof.
At n=1 multiple 16 .
Let at n=k
multiple16.
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 
on the676.
Proof.
Let us first prove that 
divided by 
.
At n=0
.
Let at n=k
divided by26
.
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 
divided by26
2
.
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 
divided by5
without a trace.
Proof.
At n=1
divided by5.
At n=k
divided by5
without a trace.
At n=k+1 each term is divisible by5 without a trace.
Example #25.
Prove that 
divided by6
without a trace.
Proof.
At n=1
divided by6
without a trace.
Let at n=k
divided by6
without a trace.
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 
even number.
Example #26.
Prove that 
when dividing by9
gives the remainder 1
.
Proof.
Let's prove that 
divided by9
.
At n=1 
divided by 9
. Let at n=k
divided by9
.
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 
multiple5
(proved in example No. 21), the fourth and fifth terms are also multiples5
, which is obvious, then the sum is a multiple of15
.
Lesson number 8-9.
Proof of inequalities by mathematical induction
Example #28. 
.
At n=1 we have 
- right.
Let at n=k 
is a true inequality.
At n=k+1
Then the inequality is valid for any natural P.
Example #29. Prove that the inequality is true 
for any P.
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 
at 
then
Example #30.
for any natural P and any 
Let n=1 
, right.
Let us assume that the inequality holds for n=k: 
.
At n=k+1
Example number 31. Prove the validity of the inequality
for any natural P.
Let us first prove that for any natural t the inequality
Multiply both sides of the inequality by 
. We obtain an equivalent inequality or 
; 
; - this inequality holds for any natural t.
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 
, then for all natural valuesP
the inequality
Proof.
At n=1
the inequality being proved takes the form 
and obviously right. Let's assume it's true forn=k
, that is, what 
.
Since according to the condition 
, then 
, and therefore the inequality does not change its meaning when both its parts are multiplied by 
:
Because 
, then we get that
.
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:
Consider the inequality
The last inequality holds if 
Test on the topic n=1 is given recurrently: n≥5 , where P- -natural number.
One of the most important methods of mathematical proof is rightly method of mathematical induction. The vast majority of formulas relating to all natural numbers n can be proved by mathematical induction (for example, the formula for the sum of the first n terms of an arithmetic progression, Newton's binomial formula, etc.).
In this article, we will first dwell on the basic concepts, then consider the method of mathematical induction itself and analyze examples of its application in proving equalities and inequalities.
Page navigation.
Induction and deduction.
by induction called the transition from particular to general statements. On the contrary, the transition from general statements to particular ones is called deduction.
An example of a private statement: 254 is divisible by 2 without a remainder.
From this particular statement, one can formulate a lot of more general statements, both true and false. For example, the more general statement that all integers ending in 4 are divisible by 2 without remainder is true, while the statement that all three-digit numbers are divisible by 2 without remainder is false.
Thus, induction makes it possible to obtain many general statements based on known or obvious facts. And the method of mathematical induction is designed to determine the validity of the statements received.
As an example, consider the numeric sequence: 
, n is an arbitrary natural number. Then the sequence of sums of the first n elements of this sequence will be the following 
Based on this fact, by induction it can be argued that .
We present the proof of this formula.
Method of mathematical induction.
The method of mathematical induction is based on principle of mathematical induction.
It consists in the following: a certain statement is true for any natural n if
- it is valid for n = 1 and
- from the validity of the statement for any arbitrary natural n = k it follows that it is true for n = k+1 .
That is, the proof by the method of mathematical induction is carried out in three stages:
- firstly, the validity of the statement is checked for any natural number n (usually the check is done for n = 1 );
- secondly, the validity of the statement is assumed for any natural n=k ;
- thirdly, the validity of the statement for the number n=k+1 is proved, starting from the assumption of the second point.
Examples of proofs of equations and inequalities by the method of mathematical induction.
Let's go back to the previous example and prove the formula 
.
Proof.
The method of mathematical induction involves a three-point proof.
Thus, all three steps of the method of mathematical induction have been completed, and thus our assumption about the formula has been proved.
Let's look at the trigonometric problem.
Example.
Prove Identity 
.
Solution.
First, we check the equality for n = 1 . To do this, we need the basic formulas of trigonometry. 
That is, the equality is true for n = 1 .
Secondly, suppose that the equality is true for n = k , that is, the identity 
Third, we turn to the proof of the equality 
for n = k+1 , based on the second point. 
Since according to the formula from trigonometry 
then
The proof of the equality from the third point is completed, therefore, the original identity is proved by the method of mathematical induction.
Can be proven by mathematical induction.
An example of proving the inequality by mathematical induction can be found in the section on the method of least squares when deriving formulas for finding approximation coefficients.
Bibliography.
- Sominsky I.S., Golovina L.I., Yaglom I.M. On mathematical induction.
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, justify and demonstrate practical value 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 to this day remains dominant in the practical work of 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 huge force beliefs 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 called a conclusion 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 prime numbers. 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 a 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. .
Add to both sides of this equality and transform 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 n-th 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 with n=1 and from the fact that it is satisfied with 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.
Application
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 given formula true at 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 is 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 new information, different from the one included in the school curriculum. While studying the method of mathematical induction, I used various literature, Internet resources, and also consulted with a teacher.
Conclusion: Having generalized and systematized knowledge on mathematical induction, I became convinced of the need for knowledge on this topic in reality. A positive quality of 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.
