What is a proof?

When is a Proof not a Proof?

1=2 (a proof using algebra)

•   Let a=b.
•   Then ,
•   ,
• ,
•   ,
•   and .
•   This can be written as ,
•   and cancelling the from both sides gives 1=2.

1=2 (a proof using complex numbers)

The proof:

•   -1/1 = 1/-1
•   Taking the square root of both sides:
•   Simplifying:
•   In other words, i/1 = 1/i.
•   Therefore, i / 2 = 1 / (2i),
•   i/2 + 3/(2i) = 1/(2i) + 3/(2i),
•   i (i/2 + 3/(2i) ) = i ( 1/(2i) + 3/(2i) ),
• ,
•   (-1)/2 + 3/2 = 1/2 + 3/2,
•   and this shows that 1=2.

Ladders fall infinitely fast when pulled! 

Common sense tells us this can't possibly be true, but can you find the flaw in the following supposed "proof" of this claim?

The proof:

• Let x denote the horizontal distance from the bottom of the ladder to the wall, at time t.
• Let y denote the height of the top of the ladder from the ground, at time t.
• Since the ladder, the ground, and the wall form a right triangle, .
• Therefore, .
• Differentiating, and letting x' and y' (respectively) denote the derivatives of x and y with respect to t, we get that

  

• Since the bottom of the ladder is being pulled with constant speed v, we have x' = v, and therefore

  

• As x approaches L, the numerator in this expression for y' approaches -Lv which is nonzero, while the denominator approaches zero.
• Therefore, y' approaches as x approaches L. In other words, the top of the ladder is falling infinitely fast by the time the bottom has been pulled a distance L away from the wall.

All People in Calgary are the Same Age

Statement S(n): In any group of n people, everyone in that group has the same age.

The proof of Statement S(n):

• In any group that consists of just one person, everybody in the group has the same age, because after all there is only one person!
• Therefore, statement S(1) is true.
• The next stage in the induction argument is to prove that, whenever S(n) is true for one number (say n=k), it is also true for the next number (that is, n = k+1).
• We can do this by (1) assuming that, in every group of k people, everyone has the same age; then (2) deducing from it that, in every group of k+1 people, everyone has the same age.
• Let G be an arbitrary group of k+1 people; we just need to show that every member of G has the same age.
• To do this, we just need to show that, if P and Q are any members of G, then they have the same age.
• Consider everybody in G except P. These people form a group of k people, so they must all have the same age (since we are assuming that, in any group of k people, everyone has the same age).
• Consider everybody in G except Q. Again, they form a group of k people, so they must all have the same age.
• Let R be someone else in G other than P or Q. Since Q and R belong to a group in which the ages are the same (all the people except P) they are the same age.
  
• Similarly, since P and R belong to such a group they are the same age.
• Since Q and R are the same age, and P and R are the same age, it follows that P and Q are the same age.
• We have now seen that, if we consider any two people P and Q in G, they have the same age. It follows that everyone in G has the same age.
• The proof is now complete: we have shown that the statement is true for n=1, and we have shown that whenever it is true for n=k it is also true for n=k+1, so by induction it is true for all n.

Well I am probably not the same age as you!  So what went wrong?

A teacher announces that before the end of class he is going to give a surprise quiz.  A clever student in his class reasoned as follows (using the principle of strong induction see below):

• Number the days of the class backward from the last day of class which will be day 0.
• Say that U(n) holds when n is a day on which the teacher cannot set a surprise quiz.
• On the last day the test will not be a surprise, so U(0) holds.
  
• If it is impossible to set a surprise test on all the days after a given day then a test that day will not be a surprise (because the test has not happened so far so the students will know it must happen that day).  Thus if for all i < n we have U(i) then U(n) holds.
• The principle of strong induction now says that U(n) must hold for all n!

All numbers can be described in fourteen words or less

You know this can't be true. After all, there are only finitely many words in the English language, so there are only finitely many sentences that can be built using fourteen words or less.  So it can't possibly be true that every natural number can be unambiguously described by such a sentence as there are infinitely many natural numbers, and only finitely many such sentences!

And yet, here's a "proof" of that claim:

The proof:

1. Suppose there is some natural number which cannot be unambiguously described in fourteen words or less.
2. Then there must be a smallest such number. Let's call it n.
3. But now n is "the smallest natural number that cannot be unambiguously described in fourteen words or less".
4. This is a complete and unambiguous description of n in fourteen words, contradicting the fact that n was supposed not to have such a description!
5. Since the assumption (step 1) of the existence of a natural number that cannot be unambiguously described in fourteen words or less led to a contradiction, it must be an incorrect assumption.
6. Therefore, all natural numbers can be unambiguously described in fourteen words or less!

I am not going to tell you the answer to this.  However, what I do wish to mention is that even a short proof can demonstrate something quite surprising.   So surprising that it can have significant effects ...

Perhaps one of the most famous (and yet simple) proofs is of the irrationality of the square root of 2. The proof is attributed to Hippasus of the Pythagorean school.  The story goes that Hippasus discovered irrational numbers when trying to represent the square root of 2 as a fraction (the proof is below).  Unfortunately for him it wasn't until much later, when Eudoxus developed a theory of irrational ratios, that Greek mathematicians accepted irrational numbers.  Pythagoras, in particular, believed in the absoluteness of numbers and did not accept the existence of irrational numbers.  However, neither could he find the fallacy in Hippasus's proof.  As he could not accept the conclusion (and admit that his philosophical ideas were wrong) he sentenced Hippasus to death by drowning! 

Please do not let this cautionary tale discourage you from getting your proofs right!  The power of life and death over students is nowadays no longer given to professors ...

Here is the proof:

Suppose sqrt(2) = n/m, where n and m are natural numbers with no common divisors.  Then 2m^2 = n^2 so that 2 divides 
n. But then it immediately follows that 2 also divides m so they have a common divisor contrary to the assumption!  So the initial assumption must be wrong.

Can you think of other proofs that have been just as controversial?

Principles of induction

To state it more informally: suppose you have been collecting numbers and the number 0 is in your collection, but also you notice that for each number k that you have in your collection, you also have the number k+1. Then you have a very large collection as it consists of all the natural numbers!

Intuitively, the idea is that if you start with the number 0, and keep on adding 1 to it, you will eventually get to every number.

The principle of induction is extremely important because it allows one to prove many results that are much more difficult, or impossible, to prove in other ways. The most common application is when one has a statement one wants to prove about each natural number.  It may be quite difficult to prove the statement directly, but easy to derive the truth of the statement about n+1 from the truth of the statement about n. In that case, one appeals to the principle of induction by showing

1. The statement is true when n=0.
2. Whenever the statement is true for one number n, then it's also true for the next number n+1.

As an example, consider proving that 1+2+3+· · ·+n = n(n+1)/2. To try to prove that equality for a general, unspecified n just by algebraic manipulations is difficult (though it may be easy to see it must be true).  However, it is easy to prove by induction: it's true when n=1 (as 1 = 1(1+1)/2), and whenever it's true for one number n, that means 1+2+3+· · ·+n = n(n+1)/2, so 1+2+3+· · ·+n+(n+1) = n(n+1)/2 + (n+1) = (n+1)(n+2)/2, so it's also true for n+1. These two facts, combined with the principle of induction, mean that it's true for all n.

Complete induction:

A consequence of mathematical induction is course-of-values induction (also known as complete induction or strong induction) which  says, given a set of natural numbers, if you know n is in the set whenever each i < n is in the set then every number is in the set.  

Here is a proof of this principle: notice that as there are no numbers less than 0 so that 0 must be in the set.  Define a subset of the set, namely those number for which all predecessors are in the set.  O is certainly in this subset.  Let k be any number in this set, as all of its predecessors are in the original set, then it is in the original set and so k+1 is in the subset.  But this means the subset contains all numbers whence the original set did!

An example of the use of strong induction is to derive the Fibonacci formula:
        fib(n) =( G^n - (-1/G)^n)/ sqrt(5)
where G is the Golden Ratio:
        G = (1+ sqrt(5))/2
and the Fibonacci sequence is given by
       fib(0) = 0, fib(1)=1, fib(n+2) = fib(n)+fib(n+1).

First we note that fib(0) and fib(1) satisfy the formula.  Now suppose fib(k) for every k < n+2 satisfies the formula (we have  dealt with 0 and 1) then
        fib(n+2) = fib(n) + fib(n+1) = (G^n - (-1/G)^n +G^(n+1) - (-1/G)^(n+1))/sqrt(5)
                      = (G^(n+1)(1+1/G) -(-1/G)^(n+1)(1-G)/sqrt(5)
                      = (G^(n+2) - (-1/G)^(n+2)
where the last step uses the two equations:
        1+1/G = G   and  1 - G = - 1/G
which are really the same equation and simplified give the quadratic
        G^2 -G -1 = 0  
for which G as defined is a root!  This is how Fibonacci found it!

Least number principal:

The least number principle says that any non-empty set of numbers has a least element.   This can be used  to do a proof by minimal counterexample:  given a set which does not contain all numbers there must be a least number not in the set.  Suppose you can show that there is no minimal counterexample (typically by using the  fact that it is a counterexample to construct another smaller counterexample) then it must be that the set of counterexamples is empty.

This is actually the contrapositive of complete induction!   If you can prove that for any  n not in the set there is a smaller m not in the set then, whenever everything smaller
than the given element n is in the set, n must be in the set.   So one can apply complete induction to conclude the set is all natural numbers.

Picks theorem:

Given a simple polygon constructed on a 2-dimensional grid of points with integer coordinates such that all the polygon's vertices are grid points, Pick's theorem provides a simple formula for calculating the area A of this polygon in terms of the number i of interior points located in the polygon and the number b of boundary points placed on the polygon's perimeter:

A = i + ½b − 1.

Note that the theorem is only valid for simple polygons, i.e. ones that consist of a single connected piece and do not contain "holes". 

The result was first described by Georg Alexander Pick in 1899. It can be generalized to three dimensions and higher with Ehrhart polynomials. The formula also generalizes to surfaces of polyhedra.

Proof:
Every polygon must involve at least three grid points.  We shall suppose that there is a polygon which is a counterexample which involves a minimum number of grid points.   Either the polygon involves only three grid points (in which case it is straight forward to check Pick's formula actually holds) or it is possible to split the polygon into two smaller polygons by drawing a cord across the polygon.  The sum of the areas of the two smaller polygons is then the area of the original.   If the path across the polygon involves d  points then the two polygons must satisfy (so d-2 interior points):
        i = i1 + i2 + d - 2            b = b1- d + b2 - d + 2 = b1 + b2 - 2d + 2
whence
       A = A1 + A2 = i1 + ½b1 − 1 + i2 + ½b2 − 1
          = i1 + i2 +  ½(b1 + b2) - 2
          = (i1 + i2 + d - 2) + ½( b1 + b2 - 2d +2) - 1
          = i + ½b - 1
so this cannot be a counterexample unless one of the smaller polygons is already a counterexample.   So there are no minimal counterexamples!

A neat application of Pick's theorem is to show:

It is impossible to draw an equilateral triangle with its vertices on grid points.

As the area of an equilateral triangle of base B has area sqrt(3) B^2/2 which, as B^2 is an integer, is an irrational number!

Well-founded Induction:

Let S be a non-empty set, and R be a binary relation on S. Then R is said to be a well-founded relation if and only if every nonempty subset  X of S has an R-minimal element.

For an example of the use of well-founded induction, when the order is not the successor or the usual ordering on numbers, consider the fundamental theorem of arithmetic: every natural number has a prime factorization.

First note that the division relation on natural numbers is well-founded and division-minimal elements are exactly the prime numbers. We detail the proof  by splitting it into considering the minimal elements and the non-minimal elements:

1. If n is prime, then n is its own factorization into primes, so the assertion is true for the division-minimal elements.
2. If n is not prime, then n has a non-trivial factorization: n = rs, where r, s are not one. By induction, r and s have prime factorizations, and therefore n has one too.
   

then the terms of these datatypes have a well-founded relation given by t2 < t1 whenever t1 is a (strict subterm) of t2 and there are to subterms of the datatype between t1 and t2

                    t1 = s[t2/x] means t2 < t1
whenever the term \x -> s(x) has  type X ->Ti(a,X). 

the relation gives  t < Cons(a,t)  which then allows us to do structural inductive proofs using the principle of structural induction for lists:

1. if a property holds for Nil  (the minimal element)
2. and whenever the property holds for t then the property holds for Cons a t) (well-founded relation t < Cons a t)
   

1. if a property holds for Tip
2. and whenever the property holds for t1 and t2 it holds for Node a t1 t2

1. leaves Tip = 1 = 1+0 = 1 + nodes Tip
2. leaves (Node a t1 t2) = leaves t1 + leaves t2 = 1+ nodes t1 + 1 + nodes t2 = 1  + nodes (Node a t1 t2).