Cheatography

# Discrete Math - Proofs Cheat Sheet (DRAFT) by mkenny

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.

### DEFINI­TIONS

 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. Parity Whether the number is odd or even Divides 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. Prime An integer n is prime if and only if n > 1, and the only positive integers that divide n are 1 and n. Composite 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. Rational A number r is rational if there exist integers x and y such that y ≠ 0 and r = x/y. ZERO 0 is rational. For example if x = 0 and y = 1, then y ≠ 0 and x/y = 0/1 = 0.

### METHOD DEFINI­TIONS

 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.

### 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" Since 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.