(notes by Roberto Bigoni)
Many mathematical theorems state that a property is true for every element of a definite set. If A is the set and a is an element of A and we use the logical symbolism, we can write:
The translation of this statement may be:"It is always true that, if a is a A, then a has the property P.
Most of these theorems can be demonstrated using the deductive method: starting from the hypothesis, recalling postulates and/or previously demonstrated theorems and applying general logical laws, one can reach the thesis.
Example: "(It is always true that) if τ is a triangle, then the sum of its internal angles equals the straight angle".
Let ABC be a triangle and let α, β and γ be their internal
angles. Let DE be the straight line parallel to AB through C (which exists and is unique: postulate). The angle DCA = α'=α because it is the internal alternate angle with respect to the angle ABC (theorem). The angle ECB = β'=β because it is the internal alternate angle with respect to the angle CBA (theorem). α'+γ+β' = DCE which is a straight angle. Sums of equal quantities are equal (general logical principle) so also α+β+γ is straight angle. |
Mathematicians can also use proofs by contradiction: the falsity of the thesis would imply contradictory consequences, so the thesis must be true.
For example: "The prime numbers are infinite".
As is known, prime numbers are natural numbers greater than 1 and divisible only by themselves and 1.
If we suppose that the number of primes is finite, we must admit the existence of their maximum m and of the number p given by the product of all the primes from 2 to m:
We must also admit the existence of the natural number s immediately following p:
This number s can't be prime, because it is greater than m, but if we divide it by any prime number from 2 to m, we get the remainder 1, so it is not divisible by any prime number less than or equal to m; then it should be divisible by some prime numbers greater than m, but our assumption is that these numbers do not exist.
Therefore, if we admit that the number of primes is finite, we get a contradictory conclusion; so we must admit that the number of primes is infinite.
In order to give the mathematics an axiomatic foundation, some mathematicians in the late 19th century, mainly J. W. R. Dedekind and G. Peano, found it necessary to admit a further way to demonstrate the trueness of the logical statements P(n) about the natural numbers n. This is the principle of mathematical induction.
Let f be a map , where N is the set of the natural numbers and A a predefined set. A sequence in A is the set of the elements of A which correspond in f to the natural numbers.
The elements of a sequence may be written using the same symbol a
together with the correspondig integer number. This number, the index, is smaller on the
right: a_{1}, a_{2}, a_{3},....a_{i},...
a_{i} is the i-th element of the sequence.
The whole sequence may be denoted in the following way:
.
For example, the sequence of the odd numbers (d_{i})_{i ∈ N} = {1,3,5,7,....} may be denoted by d_{i}=2i-1 where d_{1}=1, d_{2}=3, d_{3}=5,...
A sequence of logical propositions is a sequence of statements with the same predicate referred to the elements of a sequence of natural numbers.
For example:
Intuitively we know that all the p_{i} are true, and that not all the q_{i} are true. But intuition is insufficient in mathematics. We need a formal procedure to validate a whole infinite set of statements. The mathematical induction principle is admitted as a formal procedure of validation.
Given a sequence of logical propositions
,
we can say that all the p_{i} are true. |
that is: the sum of a natural number n ≥ 1 and its square n^{2} is an even number.
The statement may be easily demonstrated by deduction:
In both cases, the result is even.
Applying the mathematical induction principle, we may proceed in the following way:
that is, if we admit the trueness of the identity for a number n, the number n+1 is such that the sum between it and its successive number is a sum between two even numbers, so this sum is even.
that is: the sum of the cube of a natural number n ≥ 1 and the quintuple of the same number is a multiple of 6.
We can also in this case demonstrate the statement by deduction:
Applying the mathematical induction principle, we may proceed in the following way:
is the sum of two multiples of 6, so it is multiple of 6.
that is: the sum of the first n odd natural numbers equals the square of n.
The statement is evidently true if n is 1.
If we admit that it is true for the sum of the first n odd numbers, can we demonstrate that it is true also if we extend the sum to the first n+1 odd numbers, that is ?
Demonstration:
that is: the sum of the squares of the first n natural numbers equals the sixth part of the product between n, its successive number and the successive number of its double.
This is immediate if n=1.
If we admit the trueness of the statement for the first n numbers, can we demonstrate that it is true also if we extend the sum to the first n+1 numbers, that is ?
Demonstration:
that is: the sum of the cubes of the first n natural numbers equals the fourth part of the square of the product between n and its successive number.
This is immediate if n=1.
If we admit the trueness of the statement for the first n numbers, can we demonstrate that it is true also if we extend the sum to the first n+1 numbers, that is ?
Demonstration:
This equality has the interesting variant
that is
In fact, in the equality
the right side can be written as
and it's easy to demonstrate that the base of the square equals the sum of the first n natural numbers.
If n=1, the equality becomes .
If a number n verifies the equality, we must have
Demonstration:
Mengoli's series.
The equality is immediate if n=1.
If we admit the equality for n we obtain
so also n+1 verifies the identity, therefore it is generally true.
Geometric series.
The equality is immediate if n=1.
If we admit the equality for n we obtain
so it holds also for n+1 and therefore it is generally true.
that is: the derivative of the n-th power of the base x with respect to the base itself is given by the product between the exponent n and the n-1-th power of the base.
If n=1 the equality results true.
From the validity for n one can deduce the validity for n+1, that is
Demonstration:
The product rule of derivation of a product gives:
This identity can be proved directly by applying the binomial theorem: infact
It may be interesting, however, to prove this identity by induction.
We can immediately see that it is true if n=1.
For n+1 we have
Binomial coefficients are such that
so we can write
that is
where the double exclamation mark after a natural number indicates the double factorial of the number itself, that is, if the number is even, the product of all even numbers that precede it and, if the number is odd, the product of all odd numbers that precede it. Additionally -1!! = 0!! = 1
If n=0, both sides of the identity have value 1.
We must demonstrate that
If, in order to simplify the exposition, we assume
we must demonstrate that, for every n>0,
For this purpose, we observe that
and also, assuming ,
In this integral the antiderivative of the integrand function can be evaluated by parts
Therefore the first fundamental theorem of calculus gives
The integral in the right side is f(n-1), so, ultimately,
When n=0, the left side is
The right side is
So the identity (12) is true for n=0. Assuming (12) true for a given n we need to prove that
The antiderivative of the integrand at the left side can be evaluated by parts
The definite integral is therefore
Since the first addend in the right side is 0 and the integral in the second addend coincides with the left side in (12) we have
If, given a circumference, we consider 2 points on it, and we draw the chord between them, the circle is divided into 2 regions.
If we consider 3 points and trace all the possible chords between them, the circle is divided into 4 regions.
If we consider 4 points and trace all the possible chords between them, the circle is divided into 8 regions.
If we consider 5 points and trace all the possible chords between them, assuming that no more than two lines intersect at any point inside the circle, the circle is divided into 16 regions.
Now we might think that, if we add another point, always assuming that no more than two lines intersect at any point inside the circle, the circle will be divided into 32 regions. But it is not true: the regions will be 31.
As is suggested by D. Acheson in the booklet "1089 and all that" (Oxford University Press, 2002), the number of these regions is
The correct sequence can be obtained by observing that, given r_{1}=1,
Every time we add a new point on the circumference, we get an increase in the number of regions given by the sum of the previous number of triangles with vertices on the circumference, expressed by the binomial coefficient, plus the number of previous points.
For example, when we add the point E,
we obtain:
In conclusion, when we add the fifth point we have an increase of 8 regions.
n | r_{n} | r_{n}-r_{n-1} | |
---|---|---|---|
1 | 1 | ||
2 | 2 | 1 | 1 |
3 | 4 | 2 | 2 |
4 | 8 | 4 | 4 |
5 | 16 | 8 | 8 |
6 | 31 | 15 | 15 |
7 | 57 | 26 | 26 |
8 | 99 | 42 | 42 |
9 | 163 | 64 | 64 |
10 | 256 | 93 | 93 |
So the equality (1) can be demonstrated by induction. In fact it is true for n = 1 and, taking it true for a given n, we obtain
So the equality (1) holds for every n.
last revision: May 2018