1d. Proof Techniques

Question 1

Proof by Construction

Answer 1

1. If x, then y

2. assume X is true, show DIRECTLY that Y is true (show something can create this Y)

Question 2

Proof by Contradiction

Answer 2

If x, then y

1. assume statement is FALSE
2. create contradiction to statement know to be true
3. find contradiction->initial false assumption = invalid, therefore Y must be true

Question 3

How to tell if its a Proof by Induction

Answer 3

when variable (x or n) is changing (approaching infinity or a finite number)

Question 4

Proof by Induction

Answer 4

show P(n) = true when n=n naught
Hypothesis: assume P(n) = true for some n = k
Prove true for n = k+1
Conclude proof