Week 4: Proof Techniques

Question 1

N

Answer 1

set of rational numbers

Question 2

Z

Answer 2

set of integers

Question 3

Z+

Answer 3

set of real numbers

Question 4

R

Answer 4

set of natural numbers

Question 5

R+

Answer 5

set of positive numbers

Question 6

Q

Answer 6

set of positive real numbers

Question 7

even integers

Answer 7

• n is even if there exists an integer k such that n=2k
• every integer is either even or odd, but not both

Question 8

odd integers

Answer 8

• n is odd if there exists an integer k such that n=2k+1
• every integer is either even or odd, but not both

Question 9

proof by contraposition

Answer 9

• when a direct proof is hard, make use of the equivalence p -> q = ¬q -> ¬p
• assume ¬q and show ¬p is true
• if we give a direct proof of ¬q -> ¬p, then we have a proof of p -> q

Question 10

proof by contradiction

Answer 10

• we want to prove that statement p is true
• to prove p, we assume ¬p and derive a contradiction

Question 11

proof by cases

Answer 11

• prove a statement by demonstrating it to be true in multiple situations

Question 12

common errors: proof by example

Answer 12

• when a claim holds true for a certain set of values, making it appear true

Question 13

common errors: declaring a proof to be trivial

Answer 13

• assuming the conclusion of the statement is already known to be true regardless of the hypothesis
• if the proof appears to easy to fill in the details, don’t use trivial

Question 14

common errors in proofs: an indirect proof that starts with the assumption you want to derive

Answer 14

• want to prove p -> q and assume ¬p is true (when showing ¬q -> ¬p)

Question 15

common errors in proofs: using the same variable for two different variables

Answer 15

• can change the meaning of a variable and produce an incorrect conclusion

Question 16

basis step

Answer 16

• the initial value used in a proof by mathematical induction
• ex. for P(n), verifying that P(1) is true

Question 17

inductive step

Answer 17

• proving that if a statement is true for the nth iteration, then it is also true for the (n+1)th iteration
• used in proof by mathematical induction

Question 18

two important points about using mathematical induction

Answer 18

• don’t assume P(k) is true for all positive integers!
• proofs by mathematics induction do not always start at n = 1(the basis step can begin at integer b, b > 1)

Question 19

direct proof

Answer 19

• start by making an assumption
• go through the process with said assumption
• ex. if n is an odd integer, then n^2 is odd, assume n is odd

Question 20

proof by mathematical induction

Answer 20

• used to prove a statement is true for every natural number
• done by proving it for the initial value (base step) and for the nth/(n+1)th iteration (inductive step)
• works for functions AND summations

Question 21

conjecture

Answer 21

• a statement that seems to be true but has not been proven

Question 22

inductive hypothesis

Answer 22

• he assumption that a statement is true for a particular integer “k” when using a proof by mathematical induction
• then used to prove it’s also true for k + 1