In general, proofwriting is skimmed at best in high schools. Yet it's something you're going to encounter sooner or later -- if not in high school, then in college. This will be a basic lesson on proofwriting and three methods of argument: deduction, proof by contradiction, and induction.
Deduction has a broader scope than induction and proof by contradiction. Most proofs have a deductive anatomy but the more surgical parts can be inductive or done by contradiction. Here are succinct explanations of the three techniques, with examples given:
DeductionDeduction is a straightforward method of argument. It takes the form
"if A then B", or A=>B. Some arguments can work both ways,
A<=>B, and thus are
logically equivalent.
Example ProblemDerive the sum of squares by deduction.
We will use difference analysis and deduction to derive the sum of squares formula. Let S(n) be the sum of squares function.
We know that S(n) is a polynomial of some unknown order because if we keep differentiating it we will sooner or later get a constant (for those who don't know calculus, basically the slope of function of the slope of the function of the slope... will be constant).
Let's first do some difference analysis.
n | S(n)
1 | 1
> 4
2 | 5 > 5
> 9 > 2
3 | 14 > 7 > 0
> 16 > 2
4 | 30 > 9
> 25
5 | 55
We see that the fourth derivative results in 0. Thus S(n) is a 3rd order polynomial.
Excercises:(1) The
contrapositive is derived by negating and permuting the terms of another proposition. If the proposition is true then the contrapositive is true.
What is the contrapositive of the proposition: “if you live in Massachusetts then you live in the USA?”
(2) The converse of a proposition is when the effect implies the cause. The converse of A=>B is B=>A.
What is the converse of the proposition: “if you are an alien then you are not human”? Is the converse true? Is the proposition logically equivalent, A<=>B.
(3) Derive the sum of cubes by deduction.
Proof by ContradictionBasically to argue something by contradiction you assume it is false and then show that it leads to some absurd conclusion. It is often the easiest route to proving something cannot happen, because if something is true then it has to be true in all cases.
Example Problem:Infinite Number of Primes ProblemExample Problem:
Excercises:(1) Prove that sqrt(3) is irrational.
(2) Prove that sqrt(6) is irrational.
InductionI think that many high schools teach induction wrong. It is much easier to think of it as proving the if-then and then finding some anchor chase to create the domino effect. The key phrase in that is
proving the if-then. You assume the
if and then prove the
then based on that assumption. The
if is often “assume the argument is true for some n” and the
then is often “is the argument true for n + 1”. When you show that it is true for some anchor case, n = c, then you can say it is true for n + 1, n + 2, n + 3…, and they topple like dominoes. Be aware that when n = c is an integer, this will only prove it true for the integers that are greater than or equal to c.
Example Problem:
Excercises:(1) Derive the sum of cubes by induction.
Now that you know these three methods of argument, you may ask “where do I start?”
There are many lines of thought you can wander through in a proof. Like chess, there are many moves you can do, and so you must have a direction -- you must be able to narrow down a set of moves that are plausible. This doesn't mean you should sacrifice creativity; plausibility is not so much judged by numbers as it is judged by the thought process -- is it logically sound?
One strategy is to think of which method of argument is best suited to the proof and then tackle it with that. Oftentimes, you should get your hands dirty. In your first investigation you should not shoot for a formal proof – prod for patterns, make tables of values, try it for a specific case before generalizing it, etc.
Another strategy is to work with the
penultimate step. This is imagining the step which satisfies "if P then the proof is done". For instance, let's assume that all users on x86labs have visited the math board =P. To prove that someone has visited the x86 math board, the penultimate step could be "if someone is a member of x86labs.org then he or she has been to the x86 math board." Then you have to show that that person is a member of x86labs.org. You can even do this recursively and go “backwards” through a proof.
Problems:(1) First show, and then prove, that a set with n elements has 2^{n}
subsets, including the empty set and the set itself.
(2) Prove Bernoulli’s Inequality, which states that if x > -1, x !=0, and n is a positive integer greater than 1, then: (1 + x)^n >= 1 + nx
(3) What is wrong with the proof that linked
here.
(4) Prove the formula for the sum of a geometric series.
(5) Prove the Fibonacci sequence formula.
(6) Prove that log 2 is irrational.
(7) Prove that the product of any three consecutive numbers is divisible by 6.
(
Prove that sqrt(2) + sqrt(3) is irrational.
(9) Determine a way to order the complex numbers. (For any two complex numbers you should be able to determine whether they are equal or not and if not then which is smaller.)
