Show Menu

Discrete Math - Proofs Cheat Sheet (DRAFT) by

The four basic proof techniques, definitions, and how to choose between them.

This is a draft cheat sheet. It is a work in progress and is not finished yet.


Even Integer
An integer x is even if there is an integer k such that x = 2k.
Odd Integer
An integer x is odd if there is an integer k such that x = 2k+1.
Whether the number is odd or even
An integer x divides an integer y if and only if x ≠ 0 and y = kx, for some integer k. Denoted x|y. If x does not divide y, then that fact is denoted x ∤ y. If x divides y, then y is said to be a multiple of x, and x is a factor or divisor of y.
An integer n is prime if and only if n > 1, and the only positive integers that divide n are 1 and n.
An integer n is composite if and only if n > 1, and there is an integer m such that 1 < m < n and m divides n.
A number r is rational if there exist integers x and y such that y ≠ 0 and r = x/y.
0 is rational. For example if x = 0 and y = 1, then y ≠ 0 and x/y = 0/1 = 0.


constr­uctive proof of existence
A proof that shows that an existe­ntial statement is true.
proof by exhaustion

Allowed assump­tions in proofs

The rules of algebra.
For example if x, y, and z are real numbers and x = y, then x+z = y+z.
The set of integers is closed under addition, multip­lic­ation, and subtra­ction.
n other words, sums, products, and differ­ences of integers are also integers.
Every integer is either even or odd.
This fact is proven elsewhere in the material.
If x is an integer, there is no integer between x and x+1.
In partic­ular, there is no integer between 0 and 1.
The relative order of any two real numbers.
For example 1/2 < 1 or 4.2 ≥ 3.7.
The square of any real number is greater than or equal to 0.
This fact is proven in a later exercise.

Choosing a Method

Common keywords and phrases in proofs

Thus, therefore then, hence, it follows that
A statement that follows from the previous statem­ent(s)
ex. n and m are integers. Therefore, n+m is also an integer.

Let, suppose
Introduce a new variable
ex. "Let x be a positive intege­r" "­Suppose that x is a positive intege­r"

If a statement depends on a fact that appeared earlier in the proof or in the assump­tions of the theorem, it can be helpful to remind the reader of that fact before the statement.
ex. "­Since x > 0 and y > z, then xy > xz."

By definition
A fact that is known because of a definition
ex. "The integer m is even. By defini­tion, m = 2k for some integer k."

By assumption
A fact that is known because of an assumption
ex. "By assump­tion, x is positive. Therefore x > 0."

"­giv­es" and "­yie­lds­"
useful to say that one equation or inequality follows from another
provides clarity to justify algebraic steps
*ex. Multip­lying both sides of the inequality x > y by 2 gives 2x > 2y.
Substi­tuting m = 2k into m2 yields (2k)2*
Since z > 0, we can multiply both sides of the inequality x > y by z to get xz > yz.