Week 4: Proof Techniques Flashcards
1
Q
N
A
set of rational numbers
2
Q
Z
A
set of integers
3
Q
Z+
A
set of real numbers
4
Q
R
A
set of natural numbers
5
Q
R+
A
set of positive numbers
6
Q
Q
A
set of positive real numbers
7
Q
even integers
A
- n is even if there exists an integer k such that n=2k
- every integer is either even or odd, but not both
8
Q
odd integers
A
- n is odd if there exists an integer k such that n=2k+1
- every integer is either even or odd, but not both
9
Q
proof by contraposition
A
- 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
10
Q
proof by contradiction
A
- we want to prove that statement p is true
- to prove p, we assume ¬p and derive a contradiction
11
Q
proof by cases
A
- prove a statement by demonstrating it to be true in multiple situations
12
Q
common errors: proof by example
A
- when a claim holds true for a certain set of values, making it appear true
13
Q
common errors: declaring a proof to be trivial
A
- 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
14
Q
common errors in proofs: an indirect proof that starts with the assumption you want to derive
A
- want to prove p -> q and assume ¬p is true (when showing ¬q -> ¬p)
15
Q
common errors in proofs: using the same variable for two different variables
A
- can change the meaning of a variable and produce an incorrect conclusion
16
Q
basis step
A
- the initial value used in a proof by mathematical induction
- ex. for P(n), verifying that P(1) is true
17
Q
inductive step
A
- 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
18
Q
two important points about using mathematical induction
A
- 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)
19
Q
direct proof
A
- 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
20
Q
proof by mathematical induction
A
- 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
21
Q
conjecture
A
- a statement that seems to be true but has not been proven
22
Q
inductive hypothesis
A
- 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
