Foundations of Mathematics
Summer Program , Columbia University
July 2001 -- Week #2 Notes
Roger B. Blumberg
0. Review of graph results from last time. Can you tell (without putting pen to paper) whether it is possible to trace the following figure with a single stroke of a pen, such that every edge is drawn once and only once?
Last week we saw a number examples of mathematical proof, most of them "indirect"; that is, in order to show a particular statement was true, we supposed that it was false, and then showed that this supposition led to a contradiction. This week we'll try to categorize several more methods of proof, and see what they all have in common.
1. The story of Gauss' third-grade sum is well-known, but he figured out much more than the sum of the first 100 consecutive integers. We use his method to derive a formula for the sum of the first n consecutive integers, and to demonstrate an elementary example of direct proof.
1 + 2 + 3 + ........ + n = SUM
n + (n-1) + (n-2) + ........ + 1 = SUM [addition is commutative]
-----------------------------------------
(n+1)+(n+1) + (n+1) + .......+ (n+1) = 2(SUM) [adding the two equations]
n(n+1) = 2(SUM) [there are n terms on the left side(s) of the equation(s)]
Therefore, SUM is equal to [n(n+1)]/2.
We can use this method to derive formulas for arithmetic series of various kinds (e.g. successive multiples of 5), and can derive a formula for the general series:
When will Gauss' direct method of deriving formulae for series fail?
2. We'll now use a direct proof to prove something we noticed in our discussion of graphs last week:
where n is the number of vertices in the graph, v(i) is the ith vertex, and E is the number of edges.
b. We know that each of the n points of the graph has either an even degree or an odd degree, and so n can be written as the sum of p and q, where p is the # of vertices with even degree, and q is the number vertices with odd degree (i.e. n = p+q). With this in mind, we can rewrite the equation as the following sum:
c. We observe that the right side of the equation is an even number, no matter what E happens to be. We also observe that the left term of the sum on the left side of the equation must itself be even. This is because each of the p points has an even number of edges attached, and the sum of any number of even numbers is always even. Thus we have:
d. But of course this means that if the equation holds the second term in the sum on the left must also be even. Yet each of the individual terms in this sum is odd, because we said that q was the number of vertices with odd degree. Therefore, only if there are an even number of these odd terms (i.e. only when q is even), will the sum be an even number. Therefore q must be even.
e. In an graph, the number of vertices with odd degree is even. (Proved)
Aside: Consider the application of this finding to social networks. In any social group, where friendship is defined to by a mutual and 1:1 relation, is it true that the number of people in the group who have an odd number of friends in the group is always even?
3. We have now seen several examples of mathematical proof, and it's time to investigate what they all have in common. That is, what is a mathematical proof, and what exactly does such a proof prove?
a. What sort of argument is a mathematical proof? Compare:
All mammals have hearts All mammals thus far observed have had hearts. All horses are mammals All horses thus far observed have been mammals. ------------------------ ------------------------------------------------ Every horse has a heart. Every horse has a heart.
b. What is the difference between a deductive argument/inference, and an inductive argument/inference? Note that the difference is not the conclusion, but rather the relation between the premises and the conclusion.
c. A deductive argument is characterized by the following: i) all information in the conclusion is already contained in the premises, ii) if the premises are true, the conclusion must be true. (We considered the hypothetical syllogism as example.)
d. What sorts of arguments have been the proofs we've looked at? the square-root of 2 proof? Köonigsburg? In mathematics, we only honor methods of proof that have the force of deductions; however, we do not always (and in fact, we rarely) construct deductive arguments as above.
4. We now look at a technique of mathematical proof called mathematical induction. Although it is called "induction", it actually has the force of the deductive forms of proof we've considered so far. Some use an analogy to the "Domino Principle" to describe how mathematical induction works, but the elegance of the method comes from the fact that it involves only two steps:
II. Prove that, if the statement is true for some general case (e.g. n), then it will also be true for the "next" case (e.g. n+1).
Taken together, these proofs allow you to conclude that a given statement is true for all cases (e.g. all n).
Example A: Any whole-cent postage n > 5 (cents) can be made using combinations of only 3 and 4 cent stamps.
As usual with a proof by mathematical induction, the first step is easy: n = 6 cents can be made using two 3-cent stamps. But how can we prove that: "If n cents can be made using only 3 cent and 4 cent stamps, then (n+1) cents can also be made using only 3 cent and 4 cent stamps? The answer is that we can come up with substitution rules that will allow us to make the "next" case (i.e. n+1 cents) whenever we have already made a given case (i.e. n cents).
Example B: Gauss' formula for the sum of consecutive integers.
Again, the first case is easy to prove: For n=1, the formula becomes 1 = [1(1+1)]/2 = 1, which is obviously true.
The second step in this example is a bit more formal than in the postage example, but the principle is the same. We want to show that:
To do this, we can show that the difference between the left sides of the equations is equal to the difference between the right sides of the equations. Therefore, if the first equation is true, then the second must be true as well. That proves the second, or "induction" step. When we combine both proofs (i.e. that the formula is true for n=1, and that whenever it is true for some case it will be true for the next case), we see that we have proven the formula true for all n.
Aside: Note that we have now proven Gauss' sum two different ways. Mathematicians often try to prove statements in new and "better" ways (where "better" often indicates an aesthetic judgement).
A. Identify a pattern for the following sum, and then prove whether
or not it is true by mathematical induction:
By computing the first several sums, we arrive at the conjecture that the sum of the first n terms can be given by the fraction (n/n+1). Now we need to prove the conjecture.
I. Let n=1 then 1/1(2) = 1/2
II. Show that
if 1/1(2) + 1/2(3) + .... + 1/n(n+1) = n/(n+1)
then 1/1(2) + 1/2(3) + .... + 1/n(n+1) + 1/(n+1)(n+2) = (n+1)/(n+2)
To prove the second step (the "induction step"), we show that the
difference between the left sides of the equations (1/(n+1)(n+2)) is
equal to the difference between the right sides of the equations:
[(n+1)/(n+2) - n/(n+1)].
B. Using mathematical induction, prove that:
I. Let n=1, then 1^2 - 1 = 0 which can be represented as 4(0).
II. Show that:
if some odd counting number squared, minus one, is divisible by 4,
then the next odd counting number squared, minus one, is divisible by 4.
Here we recognize the need to convert the statements in the induction step
into equations that will allow us to manipulate them. So,
II. Show that:
if n^2 -1 = 4x
then (n+2)^2 - 1 = 4y
We can expand the "then" statement to get n^2 + 4n + 4 - 1, and we see that
two of the terms are obviously divisible by 4. But the remaining number
(n^2 -1) is also divisible by 4, as we know from the "if" statement.
Therefore, we have completed the induction step, and thus proved that,
for all n, if n is an odd counting number, than (n^2 - 1) is divisible by 4.
1. We continue with mathematical induction. In each of the following examples, we see that the same two-step procedure is followed, although the way we establish the induction step may differ.
For k > 0, integers of the form 9^k - 1 are always divisible by 8. Here the induction step requires us to show that when we know that 9^k -1 is divisible by 8, then we also know that 9^k+1 - 1 is also divisible by 8. We can do this by showing that the difference between 9^k+1 - 1 and 9^k -1 is divisible by 8.
The sum of cubes of any three consecutive natural numbers (greater than 0) is divisible by 9. One of the goals of this example, I admit, is to make sure everyone knows how to expand (x+3)^3.
The sum of successive cubes. Here we first need to find a formula for the sum of cubes that we can prove using mathematical induction. To do this we compute several examples until a pattern becomes clear; we recognize that the sum of cubes seems to be just the Gaussian sum squared.
For all integers n > 2, n! > 2n. Here we learn a bit about working with factorials, and can reduce the "then" statement to n! > 2, which is trivially true, since the initial condition is that n > 2.
Every polygon of n vertices can be triangulated. If the polygon is a triangle (i.e. n=3) then the statement is clearly true. The induction step involves drawing a diagonal in a polygon with n vertices, thus partitioning the polygon into two polygons.
If n is an integer greater than or equal to 14, then n can be written as a sum of 3's and/or 8's. As in Example A, above, we look for substitution rules to prove the induction step.
1(3) + 2(4) + 3(5) + ................. + n(n+2) = (1/6)(n)(n+1)(2n+7). A simple example, but one which requires some careful algebra. While working out the induction step, we have to multiply polynomials and Kristina (in Section II) suggested the following method, based on how we multiply numbers with more than one digit. For example, if we want to multiply (n^2 + 3n + 2) by (2n + 9), we can write:
n^2 + 3n + 2
2n + 9
--------------
9n^2 + 27n + 18
2n^3 + 6n^2 + 4n
----------------------
2n^3 + 15n^2 + 31n + 18
Are proofs by mathematical induction examples of deductive arguments?
2. We now consider some "classical" examples of deductive proof, drawn from Euclidean geometry. We begin with several axioms, and deduce theorems one by one, sometimes directly and sometimes indirectly.
Primitives: "line", "point"
T2: Every line contains at least 1 point. This may seem a trivial thing to want to prove, but because it is not an axiom it must be proven in order for us to use it in future proofs. We can prove this indirectly, by showing that assuming that there exists a line that contains no points contradicts the axioms we have already accepted (specifically, it contradicts A5).
T2c: Every line contains at least two points. We prove this indirectly as well, again showing that a line that contains only one point would contradict A5.
T3: There exist at least four points. Armed with the axioms and theorems we've now proven, we can use a direct proof to construct four different points. One way to do this is: A2, A3, A4, A5, T2c.
3. Finally, we want to address the question of whether indirect proofs, like the one concerning the irrationality of the square-root of 2, are also examples of deductive arguments. We consider an indirect proof of the square root of 2, different than the one we saw last week, based on the theorem: Every integer greater than 1 can be expressed as a unique product of primes (except for the order of the factors). We show that the equation:
cannot be true, because the prime chains of the two sides cannot be the same. Specifically, the number 2 must appear an odd number of times on the right, and an even number of times on the left. We can generalize this method to show that the nth root of any prime is irrational.
