# Proofs

A theorem is a statement that can be proven to be true, and a proof is the formal process of showing that it is true via a series of steps consisting of axioms (assumed truth), proven theorems, and logic.

Writing proofs is formally done like:

Theorem:
Every positive integer is less than
or equal to its square.

Proof:
Let x be an integer, where  x > 0

Since x > 0, we can multiply both
sides of the inequality by x to get: x*x >= 1x

Simplify the expression we get: x^2 >= x ∎

# Language

Proofs use language to give the purpose of each line:

let/suppose: new variable thus/therefore: it follows from the last point since: restate a fact or assumption we will prove/show: purpose by definition by assumption in other words gives/yields

# Universal Proofs

# Proof by Exhaustion

If you literally walk through every element of a domain and prove a statement is true for each element, you have proven the universally qualified statement as true via exhaustion.

# Universal Generalization

Name an arbitrary object of a theorem's domain and prove the theorem for that object.

The example at the top of this document is a universal generalization.

Remember that you only need a single counterexample to prove universally quantified statements as false. A counterexample needs to satisfy all the hypothesis but contradict the conclusion.

# Existential Proofs

To disprove an existential statement you have to prove that for every element the statement is false.

# Constructive proof of existence

Give a specific example of an element that has the required properties.

# Nonconstructive proof of existence

Commonly done by showing that assuming no element exists leads to a contradiction.

# Direct Proofs

p -> c

p is assumed to be true and the conclusion is proven to be true as a direct result of the proposition.

example:

Theorem: The difference between two even integers is even.

Let x and y be even integers. We will prove that x-y is even.

Since x is even, there is an integer k such that x = 2k.
Since y is even, there is an integer j such that y = 2j.

x-y = 2k - 2j

2k - 2j = 2(k-j)

Since k and j are integers, k-j is also an integer.

Since x-y is equal to 2m, where m = k-j which is an integer, x-y is even.
∎

# Contrapositive

To prove p -> q show that ¬q -> ¬p

Do this when ¬q is a more useful assumption than p.

If you have to negate and/or statements you can remember de morgan's laws:

If x < 0 and xy > 0, then y < 0.

contrapositive:

assume y >= 0, show x >= 0 or xy <= 0

# Contradiction

A proof by contradiction is an indirect proof where you assume the theorem is false (¬t) and prove that a contradiction arises as a result of that assumption (r ∧ ¬r).

# Proof by cases

For a universal statement, you can break the domain into different groups and prove the theorem is true for a member of each group.

For every integer x, x2 - x is an even integer.

Case 1: x is even
Case 2: x is odd

Also you can sometimes break into one case without loss of generality:

Theorem: For any two integers x and y, if x is even or y is even, then xy is even.

Proof:
Without loss of generality, assume that x is even. Then x = 2k for some integer k. Plugging in the expression 2k for x in xy gives xy = 2ky = 2(ky). Since k and y are integers, ky is also an integer. Since xy is equal to two times an integer, xy is even.  ■

# Induction

Induction is a proof technique especially helpful for proving statements about elements in a sequence. It can also be used when proving facts about lists of other mathematical objects like sets - even if those lists are infinitely long.

Principle of mathematical induction:

Let S(n) be a statement parameterized by a positive integer n. Then S(n) is true for all positive integers n, if:

1. S(1) is true (the base case).
2. For all k ∈ Z+, S(k) implies S(k+1) (the inductive step).

Proofs using induction follow this general outline:

Theorem:
Thing you will prove, including the inductive hypothesis

Proof:
Induction on n (n is the variable you are tracking)

Base:
n = 1

...show what happens

Inductive step:

...assume the inductive hypothesis (base case generalized to some k)

...show n implies n+1 using the inductive hypothesis

Here is an example of an inductive proof:

Theorem: For every positive integer n, 3 evenly divides 2^(2n) - 1.

Proof: By induction on n

Base Case: n = 1

2^(2*1) - 1 = 4 - 1 = 3. Since 3 evenly divides 3, the theorem holds for the
case n = 1.

Inductive step:

Suppose that for positive integer k, 3 evenly divides 2^2k - 1. Then we will
show that 3 evenly divides 2^2(k+1) - 1.

By the inductive hypothesis 3 evenly divides 2^2k - 1, which means that = 3m for
some integer m. By adding 1 to both sides of the equation, we get 2^2k = 3m + 1.

We must show 2^2(k+1) - 1 can be expressed as three times an integer:

2^2(k+1) - 1 = 2^(2k+2) - 1
= 4 * 2^(2k) - 1
= 4(3m + 1) - 1 (subbing in our reworked inductive hypothesis)
= 3 * 4m + 4 - 1
= 3(4m + 1)

Scince m is an integer, 3(4m + 1) is 3 multiplied by an integer. Therefore
2^(2k) - 1 is divisible by 3. ∎

# Strong Induction

In normal (weak) induction, the inductive hypothesis is just S(k), but in strong induction we assume the fact to be proven holds for every value up to k as well. This is needed for proving things like the Fibonacci sequence because you need to refer to deeper values than just k-1.

You may need multiple base cases to establish the truth value on the sequence before you generalize to the inductive hypothesis.

For all k ≥ 6, if P(3), P(4),.....,P(k) are all true, then P(k+1) is true.
Base case: show P(3), P(4), P(5), and P(6).