Prove the formula using the method of mathematical induction. The principle of mathematical induction. Solution of examples

Lecture 6. Method mathematical induction.

New knowledge in science and life is obtained in different ways, but all of them (if you do not go into details) are divided into two types - the transition from the general to the particular and from the particular to the general. The first is deduction, the second is induction. Deductive reasoning is what is usually called in mathematics logical reasoning, and in mathematical science deduction is the only legitimate method of investigation. The rules of logical reasoning were formulated two and a half millennia ago by the ancient Greek scientist Aristotle. He created a complete list of the simplest correct reasoning, syllogisms– "bricks" of logic, at the same time pointing out typical reasoning, very similar to the correct ones, but wrong (we often meet with such "pseudological" reasoning in the media).

Induction (induction - in Latin guidance) is illustrated by the well-known legend of how Isaac Newton formulated the law gravity after an apple fell on his head. Another example from physics: in such a phenomenon as electromagnetic induction, an electric field creates, “induces” a magnetic field. "Newton's apple" is a typical example of a situation where one or more special cases, i.e. observations, "lead" to a general statement, the general conclusion is made on the basis of particular cases. The inductive method is the main one for obtaining general patterns in both natural and human sciences. But it has a very significant drawback: on the basis of particular examples, an incorrect conclusion can be drawn. Hypotheses arising from private observations are not always correct. Consider an example due to Euler.

We will calculate the value of the trinomial for some first values n:

Note that the numbers obtained as a result of calculations are prime. And one can directly verify that for each n 1 to 39 polynomial value
is a prime number. However, when n=40 we get the number 1681=41 2 , which is not prime. Thus, the hypothesis that could arise here, that is, the hypothesis that for each n number
is simple, turns out to be false.

Leibniz proved in the 17th century that for every positive integer n number
divisible by 3
is divisible by 5, and so on. Based on this, he suggested that for every odd k and any natural n number
divided by k, but soon noticed that
is not divisible by 9.

The considered examples allow us to draw an important conclusion: a statement can be true in a number of special cases and at the same time unjust in general. The question of the validity of the statement in the general case can be solved by applying a special method of reasoning called by mathematical induction (full induction, perfect induction).

6.1. The principle of mathematical induction.

♦ The method of mathematical induction is based on principle of mathematical induction , consisting of the following:

1) the validity of this statement is verified forn=1 (induction basis) ,

2) this statement is assumed to be true forn= k, wherekis an arbitrary natural number 1(induction assumption) , and taking into account this assumption, its validity is established forn= k+1.

Proof. Assume the opposite, that is, suppose that the assertion is not true for every natural n. Then there is such a natural m, what:

1) approval for n=m not fair,

2) for everyone n, smaller m, the assertion is true (in other words, m is the first natural number for which the assertion fails).

It's obvious that m>1, because for n=1 the statement is true (condition 1). Hence,
- natural number. It turns out that for a natural number
the statement is true, and for the next natural number m it is unfair. This contradicts condition 2. ■

Note that the proof used the axiom that any collection of natural numbers contains the smallest number.

A proof based on the principle of mathematical induction is called by complete mathematical induction .

 Example6.1. Prove that for any natural n number
is divisible by 3.

Decision.

1) When n=1 , so a 1 is divisible by 3 and the statement is true for n=1.

2) Assume that the statement is true for n=k,
, that is, that number
is divisible by 3 and find that n=k+1 number is divisible by 3.

Indeed,

Because each term is divisible by 3, then their sum is also divisible by 3. ■ 

 Example6.2. Prove that the sum of the first n natural odd numbers is equal to the square of their number, that is, .

Decision. We use the method of complete mathematical induction.

1) We check the validity of this statement for n=1: 1=1 2 is correct.

2) Suppose that the sum of the first k (
) of odd numbers is equal to the square of the number of these numbers, that is, . Based on this equality, we establish that the sum of the first k+1 odd numbers is equal to
, i.e .

We use our assumption and get

. ■ 

The method of complete mathematical induction is used to prove some inequalities. Let us prove Bernoulli's inequality.

 Example6.3. Prove that when
and any natural n the inequality
(Bernoulli's inequality).

Decision. 1) When n=1 we get
, which is correct.

2) We assume that at n=k there is an inequality
(*). Using this assumption, we prove that
. Note that when
this inequality holds, and therefore it suffices to consider the case
.

Multiply both parts of the inequality (*) by the number
and get:

That is (1+
.■ 

Proof by method incomplete mathematical induction some assertion depending on n, where
held the same way, but at the beginning justice is set for the smallest value n.

Some problems do not explicitly formulate a statement that can be proved by mathematical induction. In such cases, it is necessary to establish a regularity and express a hypothesis about the validity of this regularity, and then test the proposed hypothesis by mathematical induction.

 Example6.4. Find the amount
.

Decision. Let's find the sums S 1 , S 2 , S 3 . We have
,
,
. We hypothesize that for any natural n the formula is valid
. To test this hypothesis, we use the method of complete mathematical induction.

1) When n=1 the hypothesis is true, because
.

2) Assume that the hypothesis is true for n=k,
, i.e
. Using this formula, we establish that the hypothesis is true and for n=k+1, that is

Indeed,

So, assuming that the hypothesis is true for n=k,
, it is proved that it is true for n=k+1, and based on the principle of mathematical induction, we conclude that the formula is valid for any natural n. ■ 

 Example6.5. In mathematics, it is proved that the sum of two uniformly continuous functions is a uniformly continuous function. Based on this statement, we need to prove that the sum of any number
uniformly continuous functions is uniformly continuous function. But since we have not yet introduced the concept of "uniformly continuous function", let's set the problem more abstractly: let it be known that the sum of two functions that have some property S, itself has the property S. Let us prove that the sum of any number of functions has the property S.

Decision. The basis of induction here is contained in the very formulation of the problem. Making the inductive assumption, consider
functions f 1 , f 2 , …, f n , f n+1 that have the property S. Then . On the right side, the first term has the property S by the induction hypothesis, the second term has the property S by condition. Therefore, their sum has the property S– for two terms, the basis of induction “works”.

This proves the assertion and will use it further. ■ 

 Example6.6. Find all natural n, for which the inequality

.

Decision. Consider n=1, 2, 3, 4, 5, 6. We have: 2 1 >1 2 , 2 2 =2 2 , 2 3<3 2 , 2 4 =4 2 , 2 5 >5 2 , 2 6 >6 2 . Thus, we can make a hypothesis: the inequality
has a place for everyone
. To prove the truth of this hypothesis, we use the principle of incomplete mathematical induction.

1) As stated above, this hypothesis is true for n=5.

2) Suppose it is true for n=k,
, that is, the inequality
. Using this assumption, we prove that the inequality
.

T. to.
and at
there is an inequality

at
,

then we get that
. So, the truth of the hypothesis n=k+1 follows from the assumption that it is true for n=k,
.

From pp. 1 and 2, based on the principle of incomplete mathematical induction, it follows that the inequality
true for every natural
. ■ 

 Example6.7. Prove that for any natural number n the differentiation formula is valid
.

Decision. At n=1 this formula has the form
, or 1=1, that is, it is true. Making the inductive assumption, we have:

Q.E.D. ■ 

 Example6.8. Prove that the set consisting of n elements, has subsets.

Decision. A set with one element a, has two subsets. This is true because all its subsets are the empty set and the set itself, and 2 1 =2.

We assume that any set of n elements has subsets. If the set A consists of n+1 elements, then we fix one element in it - denote it d, and divide all subsets into two classes - not containing d and containing d. All subsets from the first class are subsets of the set B obtained from A by removing the element d.

The set B consists of n elements, and therefore, by the induction hypothesis, it has subsets, so in the first class subsets.

But in the second class there are the same number of subsets: each of them is obtained from exactly one subset of the first class by adding the element d. Therefore, in total, the set A
subsets.

Thus the assertion is proved. Note that it is also valid for a set consisting of 0 elements - an empty set: it has a single subset - itself, and 2 0 =1. ■ 

Induction is a method of obtaining a general statement from particular observations. In the case when a mathematical statement concerns a finite number of objects, it can be proved by checking for each object. For example, the statement: “Every two-digit even number is the sum of two prime numbers," - follows from a series of equalities that are quite realistic to establish:

10=5+5 12=5+7 14=7+7 16=5+11 . . . 92=3+89 94=5+89 96=7+89 98=19+79.

The method of proof, in which a statement is verified for a finite number of cases, exhausting all possibilities, is called complete induction. This method is relatively rarely applicable, since mathematical statements, as a rule, concern not finite, but infinite sets of objects. For example, the statement about even two-digit numbers proved above by complete induction is only a special case of the theorem: "Any even number is the sum of two prime numbers." This theorem has not yet been proven or refuted.

Mathematical induction is a method of proving a certain statement for any natural n based on the principle of mathematical induction: “If a statement is true for n=1 and from its validity for n=k it follows that this statement is true for n=k+1, then it is true for all n ". The method of proof by mathematical induction is as follows:

1) base of induction: prove or directly verify the validity of the statement for n=1 (sometimes n=0 or n=n 0);

2) induction step (transition): they assume the validity of the statement for some natural n=k and, based on this assumption, prove the validity of the statement for n=k+1.

Problems with solutions

1. Prove that for any natural n the number 3 2n+1 +2 n+2 is divisible by 7.

Denote A(n)=3 2n+1 +2 n+2 .

base of induction. If n=1, then A(1)=3 3 +2 3 =35 and obviously divisible by 7.

Induction hypothesis. Let A(k) be divisible by 7.

inductive transition. Let us prove that A(k+1) is divisible by 7, that is, the validity of the statement of the problem for n=k.

А(k+1)=3 2(k+1)+1 +2 (k+1)+2 =3 2k+1 3 2 +2 k+2 2 1 =3 2k+1 9+2 k+2 2=

3 2k+1 9+2 k+2 (9–7)=(3 2k+1 +2 k+2) 9–7 2 k+2 =9 A(k)–7 2 k +2 .

The last number is divisible by 7, since it is the difference of two integers divisible by 7. Therefore, 3 2n+1 +2 n+2 is divisible by 7 for any natural n.

2. Prove that for any positive integer n the number 2 3 n +1 is divisible by 3 n+1 and is not divisible by 3 n+2 .

Let's introduce the notation: a i =2 3 i +1.

For n=1 we have, and 1 =2 3 +1=9. So, a 1 is divisible by 3 2 and not divisible by 3 3 .

Let for n=k the number a k is divisible by 3 k+1 and not divisible by 3 k+2 , i.e. a k =2 3 k +1=3 k+1 m, where m is not divisible by 3. Then

and k+1 =2 3 k+1 +1=(2 3 k) 3 +1=(2 3 k +1)(2 3 k 2 –2 3 k +1)=3 k+1 m m ((2 3 k +1) 2 –3 2 3 k)=3 k+1 m ((3 k+1 m) 2 –3 2 3 k)=

3 k+2 m (3 2k+1 m 2 –2 3 k).

Obviously, a k+1 is divisible by 3 k+2 and is not divisible by 3 k+3 .

Therefore, the assertion is proved for any natural n.

3. It is known that x+1/x is an integer. Prove that х n +1/х n is also an integer for any integer n.

Let's introduce the notation: a i \u003d x i +1 / x i and immediately note that a i \u003d a -i, so we will continue to talk about natural indices.

Note: and 1 is an integer by condition; a 2 is an integer, since a 2 \u003d (a 1) 2 -2; and 0=2.

Assume that a k is an integer for any positive integer k not exceeding n. Then a 1 ·a n is an integer, but a 1 ·a n =a n+1 +a n–1 and a n+1 =a 1 ·a n –a n–1. However, and n–1 is an integer by the induction hypothesis. Hence, а n+1 is also an integer. Therefore, х n +1/х n is an integer for any integer n, which was to be proved.

4. Prove that for any positive integer n greater than 1, the double inequality

5. Prove that for natural n > 1 and |х|

(1–x)n +(1+x)n

For n=2 the inequality is true. Really,

(1–x) 2 + (1 + x) 2 \u003d 2 + 2 x 2

If the inequality is true for n=k, then for n=k+1 we have

(1–x)k+1 +(1+x)k+1

The inequality is proved for any natural number n > 1.

6. There are n circles on the plane. Prove that for any arrangement of these circles, the map formed by them can be correctly colored with two colors.

Let's use the method of mathematical induction.

For n=1 the assertion is obvious.

Assume that the statement is true for any map formed by n circles, and let n + 1 circles be given on the plane. Removing one of these circles, we get a map that, by virtue of the assumption made, can be correctly colored with two colors (see the first figure below).

We then restore the discarded circle and on one side of it, for example inside, change the color of each area to the opposite (see the second picture). It is easy to see that in this case we get a map correctly colored with two colors, but only now with n + 1 circles, which was to be proved.

7. We will call a convex polygon “beautiful” if the following conditions are met:

1) each of its vertices is painted in one of three colors;

2) any two neighboring vertices painted in different colors;

3) at least one vertex of the polygon is colored in each of the three colors.

Prove that any beautiful n-gon can be cut by non-intersecting diagonals into "beautiful" triangles.

Let's use the method of mathematical induction.

base of induction. For the smallest possible n=3, the statement of the problem is obvious: the vertices of the "beautiful" triangle are colored in three different colors and no cuts needed.

Induction hypothesis. Let us assume that the statement of the problem is true for any "beautiful" n-gon.

induction step. Consider an arbitrary "beautiful" (n + 1)-gon and prove, using the induction hypothesis, that it can be cut by some diagonals into "beautiful" triangles. Denote by А 1 , А 2 , А 3 , … А n , А n+1 – successive vertices of the (n+1)-gon. If only one vertex of the (n + 1)-gon is colored in any of the three colors, then by connecting this vertex with diagonals to all vertices not adjacent to it, we obtain the necessary partition of the (n + 1)-gon into “beautiful” triangles.

If at least two vertices of an (n + 1)-gon are painted in each of the three colors, then we denote the color of the vertex A 1 by the number 1, and the color of the vertex A 2 by the number 2. Let k be the smallest number such that the vertex A k is colored in the third color. It is clear that k > 2. Let us cut off the triangle А k–2 А k–1 А k from the (n+1)-gon with the diagonal А k–2 А k . In accordance with the choice of the number k, all the vertices of this triangle are painted in three different colors, that is, this triangle is "beautiful". The convex n-gon A 1 A 2 ... A k–2 A k A k+1 ... A n+1 , which remains, will also, due to the inductive assumption, be “beautiful”, which means it is divided into “beautiful” triangles, which and needed to be proven.

8. Prove that in a convex n-gon it is impossible to choose more than n diagonals so that any two of them have a common point.

Let's carry out the proof by the method of mathematical induction.

Let us prove a more general statement: in a convex n-gon, it is impossible to choose more than n sides and diagonals so that any two of them have a common point. For n = 3 the assertion is obvious. Let us assume that this assertion is true for an arbitrary n-gon and, using this, prove its validity for an arbitrary (n + 1)-gon.

Assume that for an (n + 1)-gon this statement is not true. If no more than two chosen sides or diagonals emerge from each vertex of an (n+1)-gon, then there are at most n+1 of them chosen. Therefore, at least three chosen sides or diagonals AB, AC, AD emerge from some vertex A. Let AC lie between AB and AD. Since any side or diagonal that comes out of C other than CA cannot cross AB and AD at the same time, only one chosen diagonal CA comes out of C.

Discarding the point C along with the diagonal CA, we get a convex n-gon in which more than n sides and diagonals are chosen, any two of which have a common point. Thus, we arrive at a contradiction with the assumption that the assertion is true for an arbitrary convex n-gon.

So, for an (n + 1)-gon, the statement is true. In accordance with the principle of mathematical induction, the statement is true for any convex n-gon.

9. There are n lines drawn in the plane, no two of which are parallel and no three pass through the same point. Into how many parts do these lines divide the plane.

With the help of elementary drawings, it is easy to make sure that one straight line divides the plane into 2 parts, two straight lines into 4 parts, three straight lines into 7 parts, and four straight lines into 11 parts.

Denote by N(n) the number of parts into which n lines divide the plane. It can be seen that

N(2)=N(1)+2=2+2,

N(3)=N(2)+3=2+2+3,

N(4)=N(3)+4=2+2+3+4.

It is natural to assume that

N(n)=N(n–1)+n=2+2+3+4+5+…+n,

or, as is easy to establish, using the formula for the sum of the first n terms arithmetic progression,

N(n)=1+n(n+1)/2.

Let us prove the validity of this formula by the method of mathematical induction.

For n=1, the formula has already been verified.

Having made the inductive assumption, consider k + 1 lines satisfying the condition of the problem. We arbitrarily select k straight lines from them. By the inductive hypothesis, they partition the plane into 1+ k(k+1)/2 parts. The remaining (k + 1)-th line will be divided by selected k lines into k + 1 parts and, therefore, will pass through the (k + 1)-th part into which the plane has already been divided, and each of these parts will be divided into 2 parts, that is, k+1 more parts will be added. So,

N(k+1)=N(k)+k+1=1+ k(k+1)/2+k+1=1+(k+1)(k+2)/2,

Q.E.D.

10. In the expression x 1: x 2: ...: x n, brackets are placed to indicate the order of actions and the result is written as a fraction:

(in this case, each of the letters x 1, x 2, ..., x n is either in the numerator of the fraction or in the denominator). How many different expressions can be obtained in this way with all possible ways of arranging brackets?

First of all, it is clear that in the resulting fraction x 1 will be in the numerator. It is almost equally obvious that x 2 will be in the denominator for any arrangement of brackets (the division sign before x 2 refers either to x 2 itself, or to any expression containing x 2 in the numerator).

It can be assumed that all other letters x 3 , x 4 , ... , x n can be located in the numerator or denominator in a completely arbitrary way. It follows that in total you can get 2 n-2 fractions: each of the n-2 letters x 3, x 4, ..., x n can be independently of the others in the numerator or denominator.

Let us prove this assertion by induction.

With n=3, you can get 2 fractions:

so the statement is true.

We assume that it is valid for n=k and prove it for n=k+1.

Let the expression x 1: x 2: ...: x k, after some arrangement of brackets, be written as a fraction Q. If x k: x k+1 is substituted into this expression instead of x k, then x k will be in the same place as it was in fractions Q, and x k + 1 will not be where x k stood (if x k was in the denominator, then x k + 1 will be in the numerator and vice versa).

Now let's prove that we can add x k+1 to the same place as x k . In the fraction Q, after placing the brackets, there will necessarily be an expression of the form q:x k, where q is the letter x k–1 or some expression in brackets. Replacing q: x k with the expression (q: x k): x k + 1 = q: (x k x k + 1), we obviously get the same fraction Q, where instead of x k is x k x k+1 .

Thus, the number of possible fractions in the case of n=k+1 is 2 times greater than in the case of n=k and is equal to 2 k–2 ·2=2 (k+1)–2 . Thus the assertion is proved.

Answer: 2 n-2 fractions.

Problems without solutions

1. Prove that for any natural n:

a) the number 5 n -3 n + 2n is divisible by 4;

b) the number n 3 +11n is divisible by 6;

c) the number 7 n +3n–1 is divisible by 9;

d) the number 6 2n +19 n –2 n+1 is divisible by 17;

e) the number 7 n+1 +8 2n–1 is divisible by 19;

f) the number 2 2n–1 –9n 2 +21n–14 is divisible by 27.

2. Prove that (n+1)·(n+2)· …·(n+n) = 2 n ·1·3·5·…·(2n–1).

3. Prove the inequality |sin nx| n|sinx| for any natural n.

4. Find integers a, b, c that are not divisible by 10 and such that for any natural n the numbers a n + b n and c n have the same last two digits.

5. Prove that if n points do not lie on the same line, then among the lines that connect them, there are at least n different ones.

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.

Yandex.RTB R-A-339285-1

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:

1. 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).
2. After that, we check the fidelity at n = k .
3. 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 .

Decision

As we already know, to apply the method of mathematical induction, three consecutive steps must be performed.

1. 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.
2. Further, we make the assumption that the formula S k = k k + 1 is correct.
3. 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 need to reduce the fraction to common denominator, bringing 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 more difficult task 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 α.

Decision

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 α

Hence,

cos 2 α cos 4 α . . . · cos 2 k + 1 α = = cos 2 α · cos 4 α · . . . cos 2 k α cos 2 k + 1 α = = sin 2 k + 1 α 2 k sin 2 α cos 2 k + 1 α = 1 2 sin 2 k + 1 α 2 k sin 2 α = sin 2 k + 2 α 2 k + 1 sin 2 α

An example of solving the problem of proving an inequality using this method is given in the article on the least squares method. 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

True knowledge at all times was based on establishing a pattern and proving its veracity in certain circumstances. For such a long period of existence of logical reasoning, the formulations of the rules were given, and Aristotle even compiled a list of "correct reasoning." Historically, it is customary to divide all inferences into two types - from the concrete to the plural (induction) and vice versa (deduction). It should be noted that the types of evidence from particular to general and from general to particular exist only in interconnection and cannot be interchanged.

Induction in mathematics

The term "induction" (induction) has Latin roots and literally translates as "guidance". Upon close study, one can distinguish the structure of the word, namely the Latin prefix - in- (denotes directed action inward or being inside) and -duction - introduction. It is worth noting that there are two types - complete and incomplete induction. Full form characterize the conclusions made on the basis of the study of all subjects of a certain class.

Incomplete - conclusions applied to all subjects of the class, but made on the basis of the study of only some units.

Complete mathematical induction is a conclusion based on a general conclusion about the entire class of any objects that are functionally related by relations of the natural series of numbers based on knowledge of this functional connection. In this case, the proof process takes place in three stages:

• at the first stage, the correctness of the statement of mathematical induction is proved. Example: f = 1, induction;
• the next stage is based on the assumption that the position is valid for all natural numbers. That is, f=h, this is the inductive assumption;
• at the third stage, the validity of the position for the number f=h+1 is proved, based on the correctness of the position of the previous paragraph - this is an induction transition, or a step of mathematical induction. An example is the so-called if the first bone in the row falls (basis), then all the bones in the row fall (transition).

Both jokingly and seriously

For ease of perception, examples of solutions by the method of mathematical induction are denounced in the form of joke problems. This is the Polite Queue task:

• The rules of conduct forbid a man to take a turn in front of a woman (in such a situation, she is let in front). Based on this statement, if the last one in line is a man, then all the rest are men.

A striking example of the method of mathematical induction is the problem "Dimensionless flight":

• It is required to prove that any number of people fit in the minibus. It is true that one person can fit inside the transport without difficulty (basis). But no matter how full the minibus is, 1 passenger will always fit in it (induction step).

familiar circles

Examples of solving problems and equations by mathematical induction are quite common. As an illustration of this approach, we can consider the following problem.

Condition: h circles are placed on the plane. It is required to prove that, for any arrangement of the figures, the map formed by them can be correctly colored with two colors.

Decision: for h=1 the truth of the statement is obvious, so the proof will be built for the number of circles h+1.

Let us assume that the statement is true for any map, and h + 1 circles are given on the plane. By removing one of the circles from the total, you can get a map correctly colored in two colors (black and white).

When restoring a deleted circle, the color of each area changes to the opposite (in this case, inside the circle). It turns out a map correctly colored in two colors, which was required to be proved.

Examples with natural numbers

The application of the method of mathematical induction is clearly shown below.

Solution examples:

Prove that for any h the equality will be correct:

1 2 +2 2 +3 2 +…+h 2 =h(h+1)(2h+1)/6.

1. Let h=1, then:

R 1 \u003d 1 2 \u003d 1 (1 + 1) (2 + 1) / 6 \u003d 1

It follows from this that for h=1 the statement is correct.

2. Assuming that h=d, the following equation is obtained:

R 1 \u003d d 2 \u003d d (d + 1) (2d + 1) / 6 \u003d 1

3. Assuming that h=d+1, it turns out:

R d+1 =(d+1) (d+2) (2d+3)/6

R d+1 = 1 2 +2 2 +3 2 +…+d 2 +(d+1) 2 = d(d+1)(2d+1)/6+ (d+1) 2 =(d( d+1)(2d+1)+6(d+1) 2)/6=(d+1)(d(2d+1)+6(k+1))/6=

(d+1)(2d 2 +7d+6)/6=(d+1)(2(d+3/2)(d+2))/6=(d+1)(d+2)( 2d+3)/6.

Thus, the validity of the equality for h=d+1 has been proven, so the statement is true for any natural number, which is shown in the solution example by mathematical induction.

Task

Condition: proof is required that for any value of h, the expression 7 h -1 is divisible by 6 without a remainder.

Decision:

1. Let's say h=1, in this case:

R 1 \u003d 7 1 -1 \u003d 6 (i.e. divided by 6 without a remainder)

Therefore, for h=1 the statement is true;

2. Let h=d and 7 d -1 is divisible by 6 without a remainder;

3. The proof of the validity of the statement for h=d+1 is the formula:

R d +1 =7 d +1 -1=7∙7 d -7+6=7(7 d -1)+6

In this case, the first term is divisible by 6 by the assumption of the first paragraph, and the second term is equal to 6. The statement that 7 h -1 is divisible by 6 without a remainder for any natural h is true.

Fallacy of judgment

Often, incorrect reasoning is used in proofs, due to the inaccuracy of the logical constructions used. Basically, this happens when the structure and logic of the proof are violated. An example of incorrect reasoning is the following illustration.

Task

Condition: requires a proof that any pile of stones is not a pile.

Decision:

1. Let's say h=1, in this case there is 1 stone in the pile and the statement is true (basis);

2. Let it be true for h=d that a pile of stones is not a pile (assumption);

3. Let h=d+1, from which it follows that when one more stone is added, the set will not be a heap. The conclusion suggests itself that the assumption is valid for all natural h.

The error lies in the fact that there is no definition of how many stones form a pile. Such an omission is called hasty generalization in the method of mathematical induction. An example shows this clearly.

Induction and the laws of logic

Historically, they always "walk hand in hand." Such scientific disciplines as logic, philosophy describe them in the form of opposites.

From the point of view of the law of logic, inductive definitions are based on facts, and the veracity of the premises does not determine the correctness of the resulting statement. Often conclusions are obtained with a certain degree of probability and plausibility, which, of course, must be verified and confirmed by additional research. An example of induction in logic would be the statement:

Drought in Estonia, drought in Latvia, drought in Lithuania.

Estonia, Latvia and Lithuania are the Baltic states. Drought in all Baltic states.

From the example, we can conclude that new information or truth cannot be obtained using the method of induction. All that can be counted on is some possible veracity of the conclusions. Moreover, the truth of the premises does not guarantee the same conclusions. However, this fact does not mean that induction vegetates in the backyard of deduction: a huge number of provisions and scientific laws are substantiated using the method of induction. Mathematics, biology and other sciences can serve as an example. This is mainly due to the method of complete induction, but in some cases partial is also applicable.

The venerable age of induction allowed it to penetrate into almost all spheres of human activity - this is science, economics, and everyday conclusions.

Induction in the scientific environment

The method of induction requires a scrupulous attitude, since too much depends on the number of studied particulars of the whole: the larger the number studied, the more reliable the result. Based on this feature, the scientific laws obtained by induction are tested for a long time at the level of probabilistic assumptions in order to isolate and study all possible structural elements, connections and influences.

In science, the inductive conclusion is based on significant features, with the exception of random provisions. This fact important due to the nature scientific knowledge. This is clearly seen in the examples of induction in science.

There are two types of induction in scientific world(in connection with the method of study):

1. induction-selection (or selection);
2. induction - exclusion (elimination).

The first type is distinguished by methodical (scrutinous) sampling of a class (subclasses) from its different areas.

An example of this type of induction is as follows: silver (or silver salts) purifies water. The conclusion is based on long-term observations (a kind of selection of confirmations and refutations - selection).

The second type of induction is based on conclusions that establish causal relationships and exclude circumstances that do not correspond to its properties, namely, universality, observance of the temporal sequence, necessity and unambiguity.

Induction and deduction from the standpoint of philosophy

If you look at the historical retrospective, the term "induction" was first mentioned by Socrates. Aristotle described examples of induction in philosophy in a more approximate terminological dictionary, but the question of incomplete induction remains open. After the persecution of the Aristotelian syllogism, the inductive method began to be recognized as fruitful and the only possible one in natural science. Bacon is considered the father of induction as an independent special method, but he failed to separate, as his contemporaries demanded, induction from the deductive method.

Further development of induction was carried out by J. Mill, who considered the induction theory from the standpoint of four main methods: agreement, difference, residues and corresponding changes. It is not surprising that today the listed methods, when considered in detail, are deductive.

Awareness of the inconsistency of the theories of Bacon and Mill led scientists to investigate the probabilistic basis of induction. However, even here there were some extremes: attempts were made to reduce the induction to the theory of probability, with all the ensuing consequences.

The induction receives a vote of confidence when practical application in certain subject areas and thanks to the metric accuracy of the inductive basis. An example of induction and deduction in philosophy can be considered the law of universal gravitation. At the date of discovery of the law, Newton was able to verify it with an accuracy of 4 percent. And when checking after more than two hundred years, the correctness was confirmed with an accuracy of 0.0001 percent, although the check was carried out by the same inductive generalizations.

Modern philosophy pays more attention to deduction, which is dictated by a logical desire to derive new knowledge (or truth) from what is already known, without resorting to experience, intuition, but using "pure" reasoning. When referring to true premises in the deductive method, in all cases, the output is a true statement.

This very important characteristic should not overshadow the value inductive method. Since induction, based on the achievements of experience, also becomes a means of its processing (including generalization and systematization).

Application of induction in economics

Induction and deduction have long been used as methods of studying the economy and predicting its development.

The range of use of the induction method is quite wide: the study of the fulfillment of forecast indicators (profit, depreciation, etc.) and a general assessment of the state of the enterprise; formation of an effective enterprise promotion policy based on facts and their relationships.

The same method of induction is used in Shewhart's charts, where, under the assumption that processes are divided into controlled and unmanaged, it is stated that the framework of the controlled process is inactive.

It should be noted that scientific laws are justified and confirmed using the method of induction, and since economics is a science that often uses mathematical analysis, risk theory and statistical data, then it is not surprising that induction is among the main methods.

The following situation can serve as an example of induction and deduction in economics. An increase in the price of food (from the consumer basket) and essential goods pushes the consumer to think about the emerging high cost in the state (induction). At the same time, from the fact of high cost with the help of mathematical methods it is possible to derive indicators of price growth for individual goods or categories of goods (deduction).

Most often, management personnel, managers, and economists turn to the induction method. In order to be able to predict the development of an enterprise, market behavior, and the consequences of competition with sufficient truthfulness, an inductive-deductive approach to the analysis and processing of information is necessary.

An illustrative example of induction in economics, referring to fallacious judgments:

• the company's profit decreased by 30%;
  a competitor has expanded its product line;
  nothing else has changed;
• the production policy of a competing company caused a profit cut of 30%;
• therefore, the same production policy needs to be implemented.

The example is a colorful illustration of how the inept use of the method of induction contributes to the ruin of an enterprise.

Deduction and induction in psychology

Since there is a method, then, logically, there is also a properly organized thinking (for using the method). Psychology as a science that studies mental processes, their formation, development, relationships, interactions, pays attention to "deductive" thinking, as one of the forms of manifestation of deduction and induction. Unfortunately, on the pages of psychology on the Internet, there is practically no justification for the integrity of the deductive-inductive method. Although professional psychologists more often they encounter manifestations of induction, or rather, erroneous conclusions.

An example of induction in psychology, as an illustration of erroneous judgments, is the statement: my mother is a deceiver, therefore, all women are deceivers. There are even more “erroneous” examples of induction from life:

• a student is not capable of anything if he received a deuce in mathematics;
• he is a fool;
• he is smart;
• I can do everything;

And many other value judgments based on absolutely random and sometimes insignificant messages.

It should be noted: when the fallacy of a person's judgments reaches the point of absurdity, a front of work appears for the psychotherapist. One example of induction at a specialist appointment:

“The patient is absolutely sure that the red color carries only danger for him in any manifestations. As a result, a person has excluded this color scheme from his life - as far as possible. In the home environment, there are many opportunities for comfortable living. You can refuse all red items or replace them with analogues made in a different color scheme. But in public places, at work, in the store - it is impossible. Getting into a situation of stress, the patient each time experiences a “tide” of completely different emotional states which may pose a danger to others."

This example of induction, and unconsciously, is called "fixed ideas." If this happens with mental a healthy person, we can talk about the lack of organization of mental activity. Elementary development can become a way to get rid of obsessive states deductive thinking. In other cases, psychiatrists work with such patients.

The above examples of induction indicate that "ignorance of the law does not exempt from the consequences (erroneous judgments)."

Psychologists, working on the topic of deductive thinking, have compiled a list of recommendations designed to help people master this method.

The first step is problem solving. As can be seen, the form of induction used in mathematics can be considered "classical", and the use of this method contributes to the "discipline" of the mind.

The next condition for the development of deductive thinking is the expansion of horizons (those who think clearly, clearly state). This recommendation directs the "suffering" to the treasuries of science and information (libraries, websites, educational initiatives, travel, etc.).

Separately, mention should be made of the so-called "psychological induction". This term, although infrequently, can be found on the Internet. All sources do not give at least a brief definition of this term, but refer to "examples from life", while passing off as the new kind induction either suggestion, or some forms of mental illness, or extreme states of the human psyche. From all of the above, it is clear that an attempt to derive a “new term” based on false (often untrue) premises dooms the experimenter to receive an erroneous (or hasty) statement.

It should be noted that the reference to the 1960 experiments (without indicating the venue, the names of the experimenters, the sample of subjects, and most importantly, the purpose of the experiment) looks, to put it mildly, unconvincing, and the statement that the brain perceives information bypassing all the organs of perception (the phrase “experienced” in this case would fit in more organically), makes one think about the gullibility and uncriticality of the author of the statement.

Instead of a conclusion

The queen of sciences - mathematics, not in vain uses all possible reserves of the method of induction and deduction. The considered examples allow us to conclude that the superficial and inept (thoughtless, as they say) application of even the most accurate and reliable methods always leads to erroneous results.

AT mass consciousness the method of deduction is associated with the famous Sherlock Holmes, who in his logical constructions often uses examples of induction, using deduction in necessary situations.

The article considered examples of the application of these methods in various sciences and spheres of human life.

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(p) true for all natural P. The proof is divided into two stages.

• 1st stage. base of induction. We take as a value P number 1 and check that BUT( 1) is a true statement.
• 2nd stage. Inductive transition. We prove that for any natural number to the implication is true: if A(k), then A(k+ 1).

The inductive passage begins with the words: “Take an arbitrary natural number to, such that A(k)", or "Let for a natural number to right A(k)". Instead of the word "let" they often say "suppose that ...".

After these words, the letter to denotes some fixed object for which the relation holds A(k). Coming from A(k) we deduce consequences, that is, we build a chain of sentences A(k) 9 R, Pi, ..., Rn = A(k+ 1), where each sentence R, is a true statement or a consequence of the previous sentences. The last sentence R" must match with A(k+ one). From this we conclude: from A(k) should A(k+).

The execution of an inductive transition can be divided into two steps:

• 1) Inductive assumption. Here we assume that BUT to variable n.
• 2) Based on the assumption, we prove that BUT right for number?+1.

Example 5.5.1. Let's prove that the number p+p is even for all natural P.

Here A(p) = "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. Offer A(k+ 1) proved.

By the method of mathematical induction, we conclude: the sentence A(p) true for all natural P.

Of course, there is no need to enter the notation every time A(p). However, it is still recommended to formulate the inductive assumption and what is required to be deduced from it in a separate line.

Note that the assertion from Example 5.5.1 can be proved without using the method of mathematical induction. To do this, it suffices to consider two cases: when P even and when P odd.

Many divisibility problems are solved by mathematical induction. Let's look at a more complex example.

Example 5.5.2. Let us prove that the number 15 2u_| +1 is divisible by 8 for all natural numbers P.

Bacha induction. Let's take /1=1. We have: number 15 2|_| +1 = 15+1 = 16 is divisible by 8.

, which for some

natural number to the number 15 2 * '+1 is divisible by 8.

Let's prove what then is the number a\u003d 15 2 (ZHN +1 is divisible by 8.

Let's convert the number a:

By assumption, the number 15 2A1 +1 is divisible by 8, which means that the entire first term is divisible by 8. The second term 224=8-28 is also divisible by 8. Thus, the number a as the difference of two numbers that are multiples of 8 is divisible by 8. The inductive step is justified.

Based on the method of mathematical induction, we conclude that for all natural P the number 15 2 "-1 -*-1 is divisible by 8.

Let us make some remarks on the solved problem.

The proved statement can be formulated a little differently: "The number 15" "+1 is divisible by 8 for any odd natural / and".

Secondly, from the proven general statement, one can draw a particular conclusion, the proof of which can be given as a separate problem: the number 15 2015 +1 is divisible by 8. Therefore, it is sometimes useful to generalize the problem by denoting a particular value by a letter, and then apply the method mathematical induction.

In the most general sense, the term "induction" means that, on the basis of particular examples, general conclusions. For example, having considered some examples of sums of even numbers 2+4=6, 2+8=10, 4+6=10, 8+12=20, 16+22=38, we conclude that the sum of any two even numbers is even number.

In the general case, such an induction can lead to incorrect conclusions. Let us give an example of such incorrect reasoning.

Example 5.5.3. Consider the number a= /r+n+41 for natural /?.

Let's find the values a for some values P.

Let be n= I. Then a = 43 is a prime number.

Let /7=2. Then a= 4+2+41 = 47 is prime.

Let l=3. Then a= 9+3+41 = 53 is prime.

Let /7=4. Then a= 16+4+41 = 61 is prime.

Take as values P numbers following the quad, such as 5, 6, 7, and make sure the number a will be simple.

We conclude: “For all natural /? number a will be simple."

The result is a false statement. Here is a counterexample: /7=41. Make sure that with this P number a will be composite.

The term "mathematical induction" has a narrower meaning, since the use of this method allows you to always get the right conclusion.

Example 5.5.4. Based on inductive reasoning, we obtain a formula for the general term of an arithmetic progression. Recall that the arithmetic profession is a numerical sequence, each member of which differs from the previous one by the same number, called the progression difference. In order to uniquely specify an arithmetic profession, you need to specify its first member a and difference d.

So by definition a p+ = a n + d, at n> 1.

In the school course of mathematics, as a rule, the formula of the general term of the arithmetic profession is established on the basis of particular examples, that is, precisely by induction.

If /7=1, THEN With 7| = I|, THEN I am| = tf|+df(l -1).

If /7=2, then i 2 = a + d, i.e a= I|+*/(2-1).

If /7=3, then i 3 = i 2 + = (a+d)+d = a+2d, i.e. i 3 = i|+(3-1).

If /7=4, then i 4 = i 3 +*/ = ( a+2d)+d\u003d R1 + 3, etc.

The given particular examples allow us to put forward a hypothesis: the general term formula has the form a" = a+(n-)d for all /7>1.

Let us prove this formula by the method of mathematical induction.

base induction verified in previous discussions.

Let 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 | +(k-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 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(p) letter P we denoted a variable, instead of which any natural numbers can be substituted. When formulating the inductive hypothesis, we denoted the value of the variable by the letter to. However, very often instead of a new letter to use the same letter as the variable. This does not affect the structure of the reasoning when performing the inductive transition.

Let's consider a few more examples of problems for which the method of mathematical induction can be applied.

Example 5.5.7. Find the value of the sum

Variable in the task P does not appear. However, consider the sequence of terms:

Denote S, \u003d a + a 2 + ... + a „. Let's find S„ for some P. If /1= 1, then S, = a, =-.

If a n= 2. then S, = a, + a? = - + - = - = -.

If /?=3, then S-, = a,+a 7+ i, = - + - + - = - + - = - = -.

3 1 - 3 2 6 12 3 12 12 4

You can calculate the values ​​yourself S „ at /7 = 4; 5. Arises

natural guess: S n= -- for any natural /7. Let's prove

This is by mathematical induction.

base induction checked above.

Let's do it inductive transition, denoting an arbitrary

variable value P the same letter, that is, we prove that from the equality

0 /7 _ /7 +1

S n=-follows equality S, =-.

/7+1 /7 + 2

Suppose that the equality is true S= - P -.

Let's allocate in total S„+ first P terms:

Applying the inductive assumption, we get:

Reducing the fraction by (/7+1), we will have the equality S n +1 - , L

The inductive transition is justified.

This proves that the sum of the first P terms

• 1 1 1 /7 ^
• - +-+...+- is equal to -. Now let's go back to the original
• 1-2 2-3 /?(// +1) /7 + 1

task. To solve it, it suffices to take as the value P number 99.

Then the sum -!- + -!- + -!- + ...+ --- will be equal to the number 0.99.

1-2 2-3 3-4 99100

Try to calculate this amount in a different way.

Example 5.5.8. Let us prove that the derivative of the sum of any finite number of differentiable functions is equal to the sum of the derivatives of these functions.

Let the variable /? denotes the number of given features. In the case when only one function is given, it is this function that is understood as the sum. Therefore, if /7=1, then the statement is obviously true: /" = /".

Suppose that the statement is true for a set of P functions (here again instead of the letter to letter taken P), that is, the derivative of the sum P functions is equal to the sum of derivatives.

Let's prove that the derivative of the sum of (n + 1) functions is equal to the sum of the derivatives. Take an arbitrary set consisting of n+ differentiable function: /1,/2, . Let us represent the sum of these functions

as g+f„+ 1, where g=f +/g + ... +/t- sum P functions. By the inductive hypothesis, the derivative of the function g is equal to the sum of derivatives: g" = ft + ft + ... +ft. Therefore, the following chain of equalities holds:

The inductive transition is completed.

Thus, the original proposition is proved for any finite number of functions.

In some cases, it is required to prove the truth of the proposition A(p) for all natural i, starting from some value with. The proof by mathematical induction in such cases is carried out according to the following scheme.

base of induction. We prove that the proposal BUT true for value P, equal with.

Inductive transition. 1) We assume that the proposal BUT true for some value to variable /?, which is greater than or equal to with.

2) We prove that the proposition BUT true for /? equal to

Note again that instead of the letter to often leave the variable designation P. In this case, the inductive transition begins with the words: “Suppose that for some value n>s right A(p). Let's prove that then A(n+ one)".

Example 5.5.9. Let us prove that for all natural n> 5 the inequality 2” > and 2 is true.

base of induction. Let 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 . It can be done different ways. enough to decide square inequality 2x 2 >(x+) 2 in multitude 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(p) true for all values ​​of the variable i less than some number R;
• 2) from the assumption made, deduce that the proposal A(p) 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 internal corners of any i-gon is equal to 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. Let's assume it's known the following statement, 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 smaller //. 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).