Proof and Reasoning
Skill Checklist
Track your progress across all skills in your objective. Mark your confidence level and identify areas to focus on.
Track your progress:
Don't know
Working on it
Confident
📖 = included in formula booklet • 🚫 = not in formula booklet
Track your progress:
Don't know
Working on it
Confident
📖 = included in formula booklet • 🚫 = not in formula booklet
Proof by deduction
Deductive Proof
A proof is a strict logical argument that demonstrates with mathematical certainty that a statement is true.
For SL students, these proofs will be in the form
Prove that
where ≡ means equivalent, i.e. equal for ALL variables in the expression, not just some specific intersections.
We use LHS (left-hand side) and RHS (right-hand side) as an abbreviation for one side of the equivalence.
Even and Odd Numbers
The parity of an integer describes whether or not it is divisible by 2. We say that
In general, even numbers take the form n=2k, and odd numbers take the form n=2k+1 for some k∈Z.
Proof by induction
Divisibility
We say that an integer a is divisible by b if a=kb for some integer k. In other words ba=k is an integer.
We write "a is divisible by b"
To write "a is not divisible by b" we write
Induction with divisibility
We can prove that an expression is always divisible by some integer D using induction. The easiest way to do this is to subtract the n=k case from the n=k+1 case, and show that the difference is divisible by D.
Induction with inequalities
Induction can be used to prove that an inequality holds. These require very careful "chains" of inequalities.
For example: 2n>n2 for n≥5.
Induction with summation
Induction can be used to proved statements involving summations with ∑ . The key is splitting the sum, which has the form
into
and use the inductive hypothesis for r=1∑kf(r).
Induction with derivatives
Induction can be used to prove statements involving the nth derivative of a function. Almost always, the product rule will be the key technique.
Contradiction and Counterexamples
Rational Numbers
A rational number is one that can be written in the form
Note that any fraction can be reduced to the point where the numerator and denominator share no common factors:
Proof by contradiction
To prove a statement by contradiction, we essentially show that if the statement were not true, math would "break".
In practice, we assume the opposite of the statement, and and derive a contradiction - a mathematical inconsistency.
Prime Numbers
A prime number is a natural number greater than 1 that has exactly two distinct positive divisors: 1 and itself. For example, the set of prime numbers begins as
Notice that 1 is not included in this list because it has only one positive divisor (namely, itself), and thus does not meet the definition.
Counterexamples
The easiest way to show a statement is not true is to find a specific example for which it is not true.