Mathematical Investigations
This document was uploaded by user and they confirmed that they have the permission to share it. If you are author or own the copyright of this book, please report to us by using this DMCA report form. Report DMCA
Overview
Download & View Mathematical Investigations as PDF for free.
More details
- Words: 1,922
- Pages: 46
Mathematical Investigations Methods of Proof Bautista
April 17, 2008
Bautista ()
Mathematical Investigations
April 17, 2008
1 / 45
1
Introduction
2
Methods of Proof Direct Proof Proof by Contradiction Mathematical Induction The Pigeonhole Principle
Bautista ()
Mathematical Investigations
April 17, 2008
2 / 45
Introduction
The Mathematical Proof
This is the device that makes theoretical mathematics special: the tightly knit chain of reasoning following logical rules, that leads inexorably to a particular conclusion. It is proof that is our device for establishing the absolute and irrevocable truth of statements in our subject. This is the reason that we can depend on mathematics that was done by Euclid 2300 years ago as readily as we believe in the mathematics that is done today. No other discipline can make such an assertion. - Krantz, 2007
Bautista ()
Mathematical Investigations
April 17, 2008
3 / 45
Methods of Proof
An Example
Into how many regions will n lines, no two of which are parallel and no three of which are concurrent divide the plane?
Bautista ()
Mathematical Investigations
April 17, 2008
4 / 45
Methods of Proof
Direct Proof
Direct Proof Example
Prove that for every positive integer n, we can find n consecutive composite integers.
Bautista ()
Mathematical Investigations
April 17, 2008
5 / 45
Methods of Proof
Direct Proof
Direct Proof Example
If a, b and c are distinct rational numbers, prove that 1 1 1 + + 2 2 (a − b) (b − c) (c − a)2 is always the square of a rational number.
Bautista ()
Mathematical Investigations
April 17, 2008
6 / 45
Methods of Proof
Direct Proof
Direct Proof Example
Prove that there is one and only one natural number n such that 28 + 211 + 2n is a perfect square.
Bautista ()
Mathematical Investigations
April 17, 2008
7 / 45
Methods of Proof
Direct Proof
Direct Proof Some Combinatorial Examples
n n = r n−r
Bautista ()
Mathematical Investigations
April 17, 2008
8 / 45
Methods of Proof
Direct Proof
Direct Proof Some Combinatorial Examples
n n−1 n−1 = + r r −1 r
Bautista ()
Mathematical Investigations
April 17, 2008
9 / 45
Methods of Proof
Direct Proof
Direct Proof Some Combinatorial Examples
m n m n m n m+n + + ··· + = 0 r 1 r −1 r 0 r
Bautista ()
Mathematical Investigations
April 17, 2008
10 / 45
Methods of Proof
Proof by Contradiction
Proof by Contradiction Example
Prove that the number of primes is infinite.
Bautista ()
Mathematical Investigations
April 17, 2008
11 / 45
Methods of Proof
Proof by Contradiction
Proof by Contradiction Example
Prove that
√
2 is irrational.
Bautista ()
Mathematical Investigations
April 17, 2008
12 / 45
Methods of Proof
Proof by Contradiction
Proof by Contradiction Example
Prove that there are no integers x > 1, y > 1 and z > 1 with x! + y ! = z!.
Bautista ()
Mathematical Investigations
April 17, 2008
13 / 45
Methods of Proof
Proof by Contradiction
Proof by Contradiction Example
Given that a, b, c are odd integers, prove that the equation ax 2 + bx + c = 0 cannot have a rational root.
Bautista ()
Mathematical Investigations
April 17, 2008
14 / 45
Methods of Proof
Mathematical Induction
The Principle of Mathematical Induction Theorem (The Principle of Mathematical Induction) If a subset M of Z+ (= the set of positive integers) satisfies the conditions 1 1∈M 2 n ∈ M implies that n + 1 ∈ M then M = Z+ . Proof.
Bautista ()
Mathematical Investigations
April 17, 2008
15 / 45
Methods of Proof
Mathematical Induction
The Principle of Mathematical Induction Theorem (The Principle of Mathematical Induction) If a subset M of Z+ (= the set of positive integers) satisfies the conditions 1 1∈M 2 n ∈ M implies that n + 1 ∈ M then M = Z+ . Proof. Suppose there is a positive integer not belonging to M. Then, there is a smallest such integer m. But m 6= 1 since [1] states that 1 ∈ M. Thus, m < 1. Now, consider m − 1. If m − 1 ∈ M, then m ∈ M which leads to a contradiction. If m − 1 ∈ / M, then we contradict minimality of m. Thus, there can be no such m. Bautista ()
Mathematical Investigations
April 17, 2008
15 / 45
Methods of Proof
Mathematical Induction
The Principle of Mathematical Induction Example
1 + 2 + ··· + n =
Bautista ()
n(n + 1) 2
Mathematical Investigations
April 17, 2008
16 / 45
Methods of Proof
Mathematical Induction
The Principle of Mathematical Induction Example
Show that 5n + 6 · 7n + 1 is divisible by 8.
Bautista ()
Mathematical Investigations
April 17, 2008
17 / 45
Methods of Proof
Mathematical Induction
The Principle of Mathematical Induction Example
Prove the binomial theorem: n
(a + b) =
X i
Bautista ()
n n−i i =0 a b. i n
Mathematical Investigations
April 17, 2008
18 / 45
Methods of Proof
Mathematical Induction
The Principle of Mathematical Induction Example
Prove that for any positive integer n, a 2n × 2n square grid with 1 square removed can be covered with L-shaped tiles that look like this:
Bautista ()
Mathematical Investigations
April 17, 2008
19 / 45
Methods of Proof
Mathematical Induction
The Principle of Mathematical Induction Example
Scratchwork: For a 2 × 2 square:
Bautista ()
Mathematical Investigations
April 17, 2008
20 / 45
Methods of Proof
Mathematical Induction
The Principle of Mathematical Induction Example
Scratchwork: For a 4 × 4 square:
Bautista ()
Mathematical Investigations
April 17, 2008
21 / 45
Methods of Proof
Mathematical Induction
The Principle of Mathematical Induction Example
Scratchwork: A 2n+1 × 2n+1 square may be divided into four 2n × 2n squares as follows:
2
2
n
2
n
2
2
n
2 2
Bautista ()
n
n
2
n
n
n
Mathematical Investigations
April 17, 2008
22 / 45
Methods of Proof
Mathematical Induction
The Principle of Mathematical Induction Example
Scratchwork: A 2n+1 × 2n+1 square may be divided into four 2n × 2n squares as follows:
2
2
n
2
n
2
2
n
2 2
Bautista ()
n
n
2
n
n
n
Mathematical Investigations
April 17, 2008
23 / 45
Methods of Proof
Mathematical Induction
The Principle of Mathematical Induction Example
Scratchwork: A 2n+1 × 2n+1 square may be divided into four 2n × 2n squares as follows:
2
2
n
2
n
2
2
n
2 2
Bautista ()
n
n
2
n
n
n
Mathematical Investigations
April 17, 2008
24 / 45
Methods of Proof
Mathematical Induction
The Principle of Mathematical Induction Example
Suppose n is a positive integer. An equilateral triangle is cut into 4n congruent triangles and one corner is removed. Show that the remaining area can be covered by red trapezoidal tiles like those shown in the figure:
Bautista ()
Mathematical Investigations
April 17, 2008
25 / 45
Methods of Proof
The Pigeonhole Principle
The Pigeonhole Principle
If kn + 1 objects (k ≥ 1) are distributed among n boxes, one of the boxes will contain at least k + 1 objects.
Bautista ()
Mathematical Investigations
April 17, 2008
26 / 45
Methods of Proof
The Pigeonhole Principle
The Pigeonhole Principle Example
Consider a 3 × 7 rectangle divided into 21 squares as shown below. If all the squares are to be colored either red or blue, show that no matter how these squares are colored, one will always form a rectangle whose corners are all of the same color.
Bautista ()
Mathematical Investigations
April 17, 2008
27 / 45
Methods of Proof
The Pigeonhole Principle
The Pigeonhole Principle Example
Bautista ()
Mathematical Investigations
April 17, 2008
28 / 45
Methods of Proof
The Pigeonhole Principle
The Pigeonhole Principle Example
Bautista ()
Mathematical Investigations
April 17, 2008
29 / 45
Methods of Proof
The Pigeonhole Principle
The Pigeonhole Principle Example
If we are to look at the board by columns, then we only have eight possible columns as shown below. When will a rectangle of vertices with the same color be formed?
Bautista ()
Mathematical Investigations
April 17, 2008
30 / 45
Methods of Proof
The Pigeonhole Principle
The Pigeonhole Principle Example
The midpoint of (a, b) and (c, d) is a+c b+d , . 2 2
Bautista ()
Mathematical Investigations
April 17, 2008
31 / 45
Methods of Proof
The Pigeonhole Principle
The Pigeonhole Principle Example
If any five of the infinite points shown above are chosen. Show that there will always be two of the five points whose midpoint is a lattice point.
Bautista ()
Mathematical Investigations
April 17, 2008
32 / 45
Methods of Proof
The Pigeonhole Principle
The Pigeonhole Principle Example
Suppose A is a set of 19 numbers chosen from the numbers 1, 4, 7, 10, 13, . . . , 97, 100. Show that no matter how A is selected, there will always be two whose sum is 104.
Bautista ()
Mathematical Investigations
April 17, 2008
33 / 45
Methods of Proof
The Pigeonhole Principle
The Pigeonhole Principle Example
If 5 points are put inside a square of side 1 unit, show that no matter how these points are located, there will always be two whose distance between them √ is less than or equal to 2/2.
1 unit
1 unit
Bautista ()
Mathematical Investigations
April 17, 2008
34 / 45
Methods of Proof
The Pigeonhole Principle
The Pigeonhole Principle Example
Given 6 points, no three of which are collinear, show that if all the 6 points are joined with each other by blue or red segments then no matter how the segments are colored, a triangle with sides of the same color will always be formed.
Bautista ()
Mathematical Investigations
April 17, 2008
35 / 45
Methods of Proof
The Pigeonhole Principle
The Pigeonhole Principle Example
Bautista ()
Mathematical Investigations
April 17, 2008
36 / 45
Methods of Proof
The Pigeonhole Principle
The Pigeonhole Principle Example
B
A
C
F
E Bautista ()
Mathematical Investigations
D April 17, 2008
37 / 45
Methods of Proof
The Pigeonhole Principle
The Pigeonhole Principle Example
B
A
C
F
E Bautista ()
Mathematical Investigations
D April 17, 2008
38 / 45
Methods of Proof
The Pigeonhole Principle
The Pigeonhole Principle Example
B
A
C
F
E Bautista ()
Mathematical Investigations
D April 17, 2008
39 / 45
Methods of Proof
The Pigeonhole Principle
The Pigeonhole Principle Example
B
A
C
F
E Bautista ()
Mathematical Investigations
D April 17, 2008
40 / 45
Methods of Proof
The Pigeonhole Principle
The Pigeonhole Principle Example
B
A
C
F
E Bautista ()
Mathematical Investigations
D April 17, 2008
41 / 45
Methods of Proof
The Pigeonhole Principle
The Pigeonhole Principle Example
B
A
C
F
E Bautista ()
Mathematical Investigations
D April 17, 2008
42 / 45
Methods of Proof
The Pigeonhole Principle
The Pigeonhole Principle Example
B
A
C
F
E Bautista ()
Mathematical Investigations
D April 17, 2008
43 / 45
Methods of Proof
The Pigeonhole Principle
The Pigeonhole Principle Example
B
A
C
F
E Bautista ()
Mathematical Investigations
D April 17, 2008
44 / 45
Methods of Proof
The Pigeonhole Principle
The Pigeonhole Principle Example
B
A
C
F
E Bautista ()
Mathematical Investigations
D April 17, 2008
45 / 45
April 17, 2008
Bautista ()
Mathematical Investigations
April 17, 2008
1 / 45
1
Introduction
2
Methods of Proof Direct Proof Proof by Contradiction Mathematical Induction The Pigeonhole Principle
Bautista ()
Mathematical Investigations
April 17, 2008
2 / 45
Introduction
The Mathematical Proof
This is the device that makes theoretical mathematics special: the tightly knit chain of reasoning following logical rules, that leads inexorably to a particular conclusion. It is proof that is our device for establishing the absolute and irrevocable truth of statements in our subject. This is the reason that we can depend on mathematics that was done by Euclid 2300 years ago as readily as we believe in the mathematics that is done today. No other discipline can make such an assertion. - Krantz, 2007
Bautista ()
Mathematical Investigations
April 17, 2008
3 / 45
Methods of Proof
An Example
Into how many regions will n lines, no two of which are parallel and no three of which are concurrent divide the plane?
Bautista ()
Mathematical Investigations
April 17, 2008
4 / 45
Methods of Proof
Direct Proof
Direct Proof Example
Prove that for every positive integer n, we can find n consecutive composite integers.
Bautista ()
Mathematical Investigations
April 17, 2008
5 / 45
Methods of Proof
Direct Proof
Direct Proof Example
If a, b and c are distinct rational numbers, prove that 1 1 1 + + 2 2 (a − b) (b − c) (c − a)2 is always the square of a rational number.
Bautista ()
Mathematical Investigations
April 17, 2008
6 / 45
Methods of Proof
Direct Proof
Direct Proof Example
Prove that there is one and only one natural number n such that 28 + 211 + 2n is a perfect square.
Bautista ()
Mathematical Investigations
April 17, 2008
7 / 45
Methods of Proof
Direct Proof
Direct Proof Some Combinatorial Examples
n n = r n−r
Bautista ()
Mathematical Investigations
April 17, 2008
8 / 45
Methods of Proof
Direct Proof
Direct Proof Some Combinatorial Examples
n n−1 n−1 = + r r −1 r
Bautista ()
Mathematical Investigations
April 17, 2008
9 / 45
Methods of Proof
Direct Proof
Direct Proof Some Combinatorial Examples
m n m n m n m+n + + ··· + = 0 r 1 r −1 r 0 r
Bautista ()
Mathematical Investigations
April 17, 2008
10 / 45
Methods of Proof
Proof by Contradiction
Proof by Contradiction Example
Prove that the number of primes is infinite.
Bautista ()
Mathematical Investigations
April 17, 2008
11 / 45
Methods of Proof
Proof by Contradiction
Proof by Contradiction Example
Prove that
√
2 is irrational.
Bautista ()
Mathematical Investigations
April 17, 2008
12 / 45
Methods of Proof
Proof by Contradiction
Proof by Contradiction Example
Prove that there are no integers x > 1, y > 1 and z > 1 with x! + y ! = z!.
Bautista ()
Mathematical Investigations
April 17, 2008
13 / 45
Methods of Proof
Proof by Contradiction
Proof by Contradiction Example
Given that a, b, c are odd integers, prove that the equation ax 2 + bx + c = 0 cannot have a rational root.
Bautista ()
Mathematical Investigations
April 17, 2008
14 / 45
Methods of Proof
Mathematical Induction
The Principle of Mathematical Induction Theorem (The Principle of Mathematical Induction) If a subset M of Z+ (= the set of positive integers) satisfies the conditions 1 1∈M 2 n ∈ M implies that n + 1 ∈ M then M = Z+ . Proof.
Bautista ()
Mathematical Investigations
April 17, 2008
15 / 45
Methods of Proof
Mathematical Induction
The Principle of Mathematical Induction Theorem (The Principle of Mathematical Induction) If a subset M of Z+ (= the set of positive integers) satisfies the conditions 1 1∈M 2 n ∈ M implies that n + 1 ∈ M then M = Z+ . Proof. Suppose there is a positive integer not belonging to M. Then, there is a smallest such integer m. But m 6= 1 since [1] states that 1 ∈ M. Thus, m < 1. Now, consider m − 1. If m − 1 ∈ M, then m ∈ M which leads to a contradiction. If m − 1 ∈ / M, then we contradict minimality of m. Thus, there can be no such m. Bautista ()
Mathematical Investigations
April 17, 2008
15 / 45
Methods of Proof
Mathematical Induction
The Principle of Mathematical Induction Example
1 + 2 + ··· + n =
Bautista ()
n(n + 1) 2
Mathematical Investigations
April 17, 2008
16 / 45
Methods of Proof
Mathematical Induction
The Principle of Mathematical Induction Example
Show that 5n + 6 · 7n + 1 is divisible by 8.
Bautista ()
Mathematical Investigations
April 17, 2008
17 / 45
Methods of Proof
Mathematical Induction
The Principle of Mathematical Induction Example
Prove the binomial theorem: n
(a + b) =
X i
Bautista ()
n n−i i =0 a b. i n
Mathematical Investigations
April 17, 2008
18 / 45
Methods of Proof
Mathematical Induction
The Principle of Mathematical Induction Example
Prove that for any positive integer n, a 2n × 2n square grid with 1 square removed can be covered with L-shaped tiles that look like this:
Bautista ()
Mathematical Investigations
April 17, 2008
19 / 45
Methods of Proof
Mathematical Induction
The Principle of Mathematical Induction Example
Scratchwork: For a 2 × 2 square:
Bautista ()
Mathematical Investigations
April 17, 2008
20 / 45
Methods of Proof
Mathematical Induction
The Principle of Mathematical Induction Example
Scratchwork: For a 4 × 4 square:
Bautista ()
Mathematical Investigations
April 17, 2008
21 / 45
Methods of Proof
Mathematical Induction
The Principle of Mathematical Induction Example
Scratchwork: A 2n+1 × 2n+1 square may be divided into four 2n × 2n squares as follows:
2
2
n
2
n
2
2
n
2 2
Bautista ()
n
n
2
n
n
n
Mathematical Investigations
April 17, 2008
22 / 45
Methods of Proof
Mathematical Induction
The Principle of Mathematical Induction Example
Scratchwork: A 2n+1 × 2n+1 square may be divided into four 2n × 2n squares as follows:
2
2
n
2
n
2
2
n
2 2
Bautista ()
n
n
2
n
n
n
Mathematical Investigations
April 17, 2008
23 / 45
Methods of Proof
Mathematical Induction
The Principle of Mathematical Induction Example
Scratchwork: A 2n+1 × 2n+1 square may be divided into four 2n × 2n squares as follows:
2
2
n
2
n
2
2
n
2 2
Bautista ()
n
n
2
n
n
n
Mathematical Investigations
April 17, 2008
24 / 45
Methods of Proof
Mathematical Induction
The Principle of Mathematical Induction Example
Suppose n is a positive integer. An equilateral triangle is cut into 4n congruent triangles and one corner is removed. Show that the remaining area can be covered by red trapezoidal tiles like those shown in the figure:
Bautista ()
Mathematical Investigations
April 17, 2008
25 / 45
Methods of Proof
The Pigeonhole Principle
The Pigeonhole Principle
If kn + 1 objects (k ≥ 1) are distributed among n boxes, one of the boxes will contain at least k + 1 objects.
Bautista ()
Mathematical Investigations
April 17, 2008
26 / 45
Methods of Proof
The Pigeonhole Principle
The Pigeonhole Principle Example
Consider a 3 × 7 rectangle divided into 21 squares as shown below. If all the squares are to be colored either red or blue, show that no matter how these squares are colored, one will always form a rectangle whose corners are all of the same color.
Bautista ()
Mathematical Investigations
April 17, 2008
27 / 45
Methods of Proof
The Pigeonhole Principle
The Pigeonhole Principle Example
Bautista ()
Mathematical Investigations
April 17, 2008
28 / 45
Methods of Proof
The Pigeonhole Principle
The Pigeonhole Principle Example
Bautista ()
Mathematical Investigations
April 17, 2008
29 / 45
Methods of Proof
The Pigeonhole Principle
The Pigeonhole Principle Example
If we are to look at the board by columns, then we only have eight possible columns as shown below. When will a rectangle of vertices with the same color be formed?
Bautista ()
Mathematical Investigations
April 17, 2008
30 / 45
Methods of Proof
The Pigeonhole Principle
The Pigeonhole Principle Example
The midpoint of (a, b) and (c, d) is a+c b+d , . 2 2
Bautista ()
Mathematical Investigations
April 17, 2008
31 / 45
Methods of Proof
The Pigeonhole Principle
The Pigeonhole Principle Example
If any five of the infinite points shown above are chosen. Show that there will always be two of the five points whose midpoint is a lattice point.
Bautista ()
Mathematical Investigations
April 17, 2008
32 / 45
Methods of Proof
The Pigeonhole Principle
The Pigeonhole Principle Example
Suppose A is a set of 19 numbers chosen from the numbers 1, 4, 7, 10, 13, . . . , 97, 100. Show that no matter how A is selected, there will always be two whose sum is 104.
Bautista ()
Mathematical Investigations
April 17, 2008
33 / 45
Methods of Proof
The Pigeonhole Principle
The Pigeonhole Principle Example
If 5 points are put inside a square of side 1 unit, show that no matter how these points are located, there will always be two whose distance between them √ is less than or equal to 2/2.
1 unit
1 unit
Bautista ()
Mathematical Investigations
April 17, 2008
34 / 45
Methods of Proof
The Pigeonhole Principle
The Pigeonhole Principle Example
Given 6 points, no three of which are collinear, show that if all the 6 points are joined with each other by blue or red segments then no matter how the segments are colored, a triangle with sides of the same color will always be formed.
Bautista ()
Mathematical Investigations
April 17, 2008
35 / 45
Methods of Proof
The Pigeonhole Principle
The Pigeonhole Principle Example
Bautista ()
Mathematical Investigations
April 17, 2008
36 / 45
Methods of Proof
The Pigeonhole Principle
The Pigeonhole Principle Example
B
A
C
F
E Bautista ()
Mathematical Investigations
D April 17, 2008
37 / 45
Methods of Proof
The Pigeonhole Principle
The Pigeonhole Principle Example
B
A
C
F
E Bautista ()
Mathematical Investigations
D April 17, 2008
38 / 45
Methods of Proof
The Pigeonhole Principle
The Pigeonhole Principle Example
B
A
C
F
E Bautista ()
Mathematical Investigations
D April 17, 2008
39 / 45
Methods of Proof
The Pigeonhole Principle
The Pigeonhole Principle Example
B
A
C
F
E Bautista ()
Mathematical Investigations
D April 17, 2008
40 / 45
Methods of Proof
The Pigeonhole Principle
The Pigeonhole Principle Example
B
A
C
F
E Bautista ()
Mathematical Investigations
D April 17, 2008
41 / 45
Methods of Proof
The Pigeonhole Principle
The Pigeonhole Principle Example
B
A
C
F
E Bautista ()
Mathematical Investigations
D April 17, 2008
42 / 45
Methods of Proof
The Pigeonhole Principle
The Pigeonhole Principle Example
B
A
C
F
E Bautista ()
Mathematical Investigations
D April 17, 2008
43 / 45
Methods of Proof
The Pigeonhole Principle
The Pigeonhole Principle Example
B
A
C
F
E Bautista ()
Mathematical Investigations
D April 17, 2008
44 / 45
Methods of Proof
The Pigeonhole Principle
The Pigeonhole Principle Example
B
A
C
F
E Bautista ()
Mathematical Investigations
D April 17, 2008
45 / 45
Related Documents
Mathematical Investigations
May 2020 11
Investigations
May 2020 21
Investigations
April 2020 42
Investigations Guidelines
May 2020 13
Msta Investigations
December 2019 19