Standard Proof techniques

Disproof by Counterexample

Shows that a conjecture is not true by pointing out an example where the conjecture does not hold.

• No nickels
• 1 quarter + 5 pennies
• 3 dimes
• Greedy method is not appropriate with limited change

Proof by Contradiction

Proof that the opposite cannot be true.

Square root of 2 is irrational

• \(\sqrt 2 = a/b\)
• \(a/b\) is simplified
• a or b or both must be odd (otherwise could be simplified)
• \(2 = a^2/b^2\)
• \(a^2 = 2 * b^2\)
• \(a^2\) must be even (2 times any number is even)
• \(a\) is even as well (odd times odd is odd)
• \(a = 2 * k\) where k is a / 2
• \(2 = (2 * k)^2/b^2 \rightarrow b^2 = 2k^2\)
• \(b\) is also odd by this method
• \(a\) and \(b\) cannot be odd
• \(\sqrt 2\) cannot be rational