Probability and Statistics
Proof Basics
Direct Proofs
There are two elements involved in direct proofs.
1) The Premises must be true.
2) The steps of the proof must be valid.
Example
Prove: 
Premise: 
True!
This is a one step proof!
Correct!
So the premise was true and the step was algebraically correct— it's a valid
proof!
Here is another direct Proof:
Prove: 
Premise: 
True! (There is nothing untrue about this premise, as long as we
realize that we are assuming that the series converges to a finite
number, S. The caveat is that we must understand that
|x|<1 for this to occur.)
Steps:
All steps are valid!
Since the premise is true and the steps are all valid, then the proof is
sound!
What happens if we start from a false premise?
Prove: 16 = 25
Premise: 1 = 2 False!
Steps:
All steps are valid!
So even though all of the steps were valid, we can prove something
ridiculous since we started with a false premise!
What happens if we have a false step?
Prove: 1 = 2
Premise: a = b;
Not untrue....
Steps:
One of the algebraic steps is incorrect (can you find which step is
wrong?)!!!! We have just proved 1 = 2, but only because we did not follow the
legal algebra rules.
The moral of the story is that if you prove something that you know is
false, then either your premise was untrue or one of your steps was false. The
third option is that what you thought was false is actually true. See (later)
Gregor Cantor's proof that there are the same number of integers and rationals.
Proof by Contradiction
This proof is approximately 2500 years old.
Prove: 
is
irrational.
First, we must know what an irrational number is. An irrational number is a
number that cannot be expressed by either a repeating decimal or a terminating
decimal (such as 14.28928928928928 or 14.3). That is to say, an irrational
number cannot be of the form p/q where p and q are both integers.
To start the proof, let us assume that 
IS
rational. Hence, let us say that
Furthermore, let us say that p/q is in its most reduced form. That is, if
could be 6/4, we are going to use p/q=3/2.
Okay, the following algebraic steps are valid:
Now, if 
is
even (it is 2 times some integer), then p must also be even (try it out for
yourself!). This means that we can rename p as 2 times another integer, r.
So now we know that q is also even. However, we assumed that p/q was in its
most reduced form and if p and q are both even, then p/q can be reduced! Because
we have arrived at a contradiction, and all of our algebraic steps were valid,
that our assumption must be wrong. Recall that our assumption was that
,
where p/q was in its most reduced form. If the assumption is false, that
means that
cannot be of the form p/q in a most reduced form. Since every number p/q can be
put in a most reduced form, then
must not be able to be put in the form of p/q at all! This means that
must be irrational.
(Deductive) Proof by two cases:
One more proof before we move on to induction, since we are on the topic of
irrational numbers. An irrational number is one that, in its decimal
representation, is a non-repeating, non-terminating decimal. Do you suppose that
there exists an irrational number such that if you raise it to an irrational
power, you get a rational number?
We know that
is irrational (see the above proof by contradiction). Let's raise
to the power to
see if we get a rational.
Case 1
is rational
We're done!
Case 2
is irrational.
Well, in this case, let's take our new irrational number and raise it to
another irrational, namely .
We have arrived at a rational number! So, in Case 1 we found a rational
number, and in Case 2 we found a rational number. Since only two cases are
possible ( is
either rational or irrational), then we have shown that it is possible to raise
an irrational number to another irrational number and get a rational out!
Proof By Induction
Deductive reasoning would go along the lines of the following: 1) I see a
dog running toward me. 2) The dog's mouth is open. 3) This dog bites everyone.
Conclusion: This dog is going to bite me.
Inductive reasoning might go something like: 1) the dog bit me three days
ago. 2) the dog bit me two days ago. 3) the dog bit me yesterday. Conclusion:
The dog will bite me today.
Now, in "real life" situations, inductive proof is not always the most
useful thing in the world. Obviously, you might run away from the dog today, or
might not even go to its house. In mathematics, however, inductive proofs are
amazingly useful and powerful.
The key to inductive proofs is to show that a statement will be true for the
(N+1)th case every time the Nth case is true. Then, if we have any starting
point (a Base Case), we can start there and we know that the statement must be
true for every subsequent case.
For every induction proof, there are four steps:
Step 1: Prove Base Case (BC)
Step 2: State Induction Hypothesis (IHOP) for Nth case and assume it is
true.
Step 3: State Goal Equation (GE) for (N+1)st case.
Step 4: Using the IHOP, derive GE Induction Proof Example
Prove: 
BC (N=1):
1 = 1(2)/2
1 = 1 YES!
IHOP:
GE:
Starting from IHOP:
So, we have shown that given the Nth case is true, that the (N+1)th case is
also true. Now we refer back to our Base Case, and know that for the first case,
it is true. Hence, it is true for the first and thus the second case. It is true
for the second and thus third case, and so on. This means it is true for all
cases, and we have proved that
!
As an aside, here are two other simple proofs that
:
1)
Add:
-----------------------------------------------
(N times)
So indeed we have shown that
2) Graphical, no words proof:
Here is another example of an induction proof:
Prove: 
BC:
IHOP:
GE:
Starting from IHOP:
So we have arrived at our next step (in this case, the (N+2)th case) from
our IHOP and have shown the Base Case to be true. Hence, we have proven that .
Finally, here is a graphical induction proof:
Prove: Given any 
checkerboard
with an arbitrary space covered, the remaining spaces can be covered by pieces
that look like:
.
Here is an example: a 
board:
The black square is first covered, and then...
Now prove it for any
checkerboard by induction!
BC: 
This is actually trivial, so let's try the next step up: 
As you can see, we have covered up one square, and the rest can be covered
by a single elbow piece.
IHOP: Assume that you can cover any
board by covering one square arbitrarily, we can cover the rest with pieces that
look like:
.
Goal: To cover a 
board by
covering one square arbitrarily and covering the rest with elbow pieces.
To begin, let's construct a
board, recognizing that a board
is simply four boards forming a
larger square. Let's cover one single square in the
board, like so:
Now, the upper-right-hand square is a
, so we know (by IHOP) we can cover the remaining top square with elbow pieces.
Next, let's take one more elbow piece and place it in the center:
Now, each of the three remaining large squares is a
with one small square "arbitrarily" covered. Hence, each of the three large
squares can each be covered with elbow pieces! Therefore, we have covered the
entire
board, after covering one (black, in the diagram above) square, with elbow
pieces. Thus, we have proved that for any checkerboard
with one square arbitrarily covered, the remaining squares can be covered with
elbow pieces.