WEBVTT
1
00:00:00.000 --> 00:00:11.380
ly
2
00:00:11.380 --> 00:00:40.820
In the prior lecture, we describe the method of the principle of mathematical induction
3
00:00:40.820 --> 00:00:46.660
as a method of proof mathematicians use to prove mathematical propositions that are
4
00:00:46.660 --> 00:00:50.300
valid for all natural numbers.
5
00:00:50.300 --> 00:00:56.540
The principle of mathematical induction, as stated, is executed in just two steps, the
6
00:00:56.540 --> 00:01:03.780
basis step and the inductive step, and it allows us to arrive to the conclusion that
7
00:01:03.780 --> 00:01:15.900
the property is valid for all natural numbers.
8
00:01:15.900 --> 00:01:25.820
The basis step, the piece of one is true and then we prove the inductive step, assume
9
00:01:25.820 --> 00:01:32.820
the piece of K is true for some arbitrary K, derived from here that piece of K plus
10
00:01:32.820 --> 00:01:41.740
one is also true and therefore piece of K is valid for all K natural.
11
00:01:41.740 --> 00:01:48.460
In our prior example of the infinite line of dominos, we can guarantee that all the dominos
12
00:01:48.460 --> 00:01:55.060
in the line will fall if we know that any time we push a dominos, the next one of the line
13
00:01:55.060 --> 00:01:57.180
will also fall.
14
00:01:57.180 --> 00:02:04.300
So to make them all fall, what we need to do is to push the first one in the line.
15
00:02:04.300 --> 00:02:10.300
But if we are not careful placing the dominos in the line so that pushing one sometimes
16
00:02:10.300 --> 00:02:15.980
does not guarantee that the next one will fall, then not all the dominos in the line will
17
00:02:15.980 --> 00:02:19.780
fall when we push the first one.
18
00:02:19.780 --> 00:02:25.900
As you may have already imagined, we can always start from a place in the line of dominos
19
00:02:25.900 --> 00:02:32.580
where there is no gap in the line and when we push the first dominos, then all the others
20
00:02:32.580 --> 00:02:34.740
will fall as before.
21
00:02:34.740 --> 00:02:42.540
It also happens that sometime we find cases where the proposition in question is not valid
22
00:02:42.540 --> 00:02:44.780
for all natural numbers.
23
00:02:44.780 --> 00:02:50.100
To solve this problem, we should be able to reformulate the principle of mathematical
24
00:02:50.100 --> 00:02:55.300
induction so that we are able to start from an arbitrary natural.
25
00:02:55.300 --> 00:02:58.140
Let us call it A.
26
00:02:58.140 --> 00:03:05.620
Pistake is some proposition depending on K, we need to prove for all K greater than
27
00:03:05.620 --> 00:03:08.220
or equal to A natural.
28
00:03:08.220 --> 00:03:16.060
We first prove the basis step that Pistake is true and then we prove they in the previous
29
00:03:16.060 --> 00:03:17.060
step.
30
00:03:17.060 --> 00:03:23.980
Assume that Pistake is true for some arbitrary K natural, derived from here that Pistake
31
00:03:23.980 --> 00:03:27.060
plus 1 is also true.
32
00:03:27.060 --> 00:03:33.420
Then Pistake is valid for all K greater than or equal to A natural.
33
00:03:33.420 --> 00:03:40.140
For mutulating the principle this way, we will allow to solve those cases where a property
34
00:03:40.140 --> 00:03:44.140
may not be valid for all natural numbers.
35
00:03:44.140 --> 00:03:48.940
As an example of such properties, we have the following.
36
00:03:48.940 --> 00:04:00.300
3 to the power n greater than 3 times n plus 1 for all n natural with n greater than 1.
37
00:04:00.300 --> 00:04:04.580
We can see that this inequality is not valid for n equal 1.
38
00:04:04.580 --> 00:04:13.500
Replacing n equal 1, we get 3 to the power 1 greater than 3 times 1 plus 1 and therefore
39
00:04:13.500 --> 00:04:16.100
3 greater than 4.
40
00:04:16.100 --> 00:04:19.820
And this last inequality is false.
41
00:04:19.820 --> 00:04:28.500
We can try more values of n like n equal to and we get 3 square greater than 3 times
42
00:04:28.500 --> 00:04:30.700
2 plus 1.
43
00:04:30.700 --> 00:04:38.300
And this is equivalent to 9 greater than 7 and in this case the inequality is true.
44
00:04:38.300 --> 00:04:46.220
Then we can see already that 3 to the power n grows faster than 3 times n plus 1.
45
00:04:46.220 --> 00:04:53.500
So we are suspecting the inequality is valid for all n natural with n greater than 1.
46
00:04:53.500 --> 00:04:59.180
To prove this, we use the generalized principle of mathematical induction.
47
00:04:59.180 --> 00:05:07.860
We have already proved the basis step for n equal to since 3 square is greater than 3 times
48
00:05:07.860 --> 00:05:09.540
2 plus 1.
49
00:05:09.540 --> 00:05:13.940
And that is equivalent to 9 greater than 7.
50
00:05:13.940 --> 00:05:14.940
And this is true.
51
00:05:14.940 --> 00:05:19.220
And we need to prove next the endotivist step.
52
00:05:19.220 --> 00:05:27.040
That is if 3 to the power k is greater than 3 times k plus 1 is valid then 3 to the power
53
00:05:27.040 --> 00:05:33.460
k plus 1 is greater than 3 times k plus 1 plus 1 is also valid.
54
00:05:33.460 --> 00:05:41.180
So assuming that 3 to the power k is greater than 3 times k plus 1 is valid multiplying both
55
00:05:41.180 --> 00:05:52.740
sides by 3 we get 3 to the power k times 3 greater than 3 times 3 times k plus 3.
56
00:05:52.740 --> 00:06:00.020
And this is equivalent to 3 to the power k plus 1 greater than 9 times k plus 3.
57
00:06:00.020 --> 00:06:10.020
But if we prove that 9 times k plus 3 greater than 3 times k plus 1 plus 1 we have them
58
00:06:10.020 --> 00:06:17.980
proved that 3 to the power k plus 1 greater than 3 times k plus 1 plus 1.
59
00:06:17.980 --> 00:06:38.980
And this is equivalent to 6 times k greater than 1.
60
00:06:38.980 --> 00:06:44.300
And this last inequality is valid for any k natural.
61
00:06:44.300 --> 00:06:51.820
And for we have proved that inequality is valid for n natural greater than 1.
62
00:06:51.820 --> 00:06:59.100
As it's very typical in mathematics to reduce an unknown problem to a known one we could
63
00:06:59.100 --> 00:07:06.940
have also proved this inequality still using the principle of mathematical induction.
64
00:07:06.940 --> 00:07:08.900
Can you see how?
65
00:07:08.900 --> 00:07:18.740
We can transform the inequality 3 to the power n greater than 3 times n plus 1 for n natural
66
00:07:18.740 --> 00:07:29.140
n greater than 1 replacing n with n plus 1 deriving the equivalent inequality 3 to the power
67
00:07:29.140 --> 00:07:37.820
n plus 1 greater than 3 times n plus 4 valid for all n natural.
68
00:07:37.820 --> 00:07:42.620
The principle of mathematical induction is very surprising.
69
00:07:42.620 --> 00:07:50.980
As it let us prove some mathematical propositions for an infinite number of natural numbers.
70
00:07:50.980 --> 00:07:57.020
The surprise comes from the fact that we only need to prove the validity of the property
71
00:07:57.020 --> 00:07:59.780
only for two cases.
72
00:07:59.780 --> 00:08:02.500
One is the induction basis.
73
00:08:02.500 --> 00:08:09.780
One is to prove the properties valid for some initial case and secondly the inductive step
74
00:08:09.780 --> 00:08:15.620
where we assume the properties valid for some k and then prove that it is also valid for
75
00:08:15.620 --> 00:08:17.820
k plus 1.
76
00:08:17.820 --> 00:08:25.100
Therefore the principle of mathematical induction allows to reduce a proof with an infinite
77
00:08:25.100 --> 00:08:35.740
number of cases to a finite number.