Proof methods

Mathematic Induction 数学归纳法 (MI)

• Base step (e.g., n=1)
• Induction hypothesis (e.g. assume when n-1, …)
• Inductive step (e.g., using hypothesis for n-1, induce n)
• Conclusion: By M.I. we proved … is true

Proof by exhaustion 穷举法

• List all the cases
• Make a table like the truth table

Proof by contradiction 反证法

• Take $\neg p$ as a premise, show that there is a contradiction
  • Assume $\neg p\to q$
  • Contradiction occur
  • Therefore, $p$ must be true

Proof by contrapositive 否定证明法

• take $\neg p$ as a premise, proof $\neg q$
• $\neg p\to \neg q$ is equivalent to $p\to q$

Direct Proof 直接证明

• Take $p$ as a premise, then show that $p\to q$

Existence Proof (constructive)

• For proving $\exist x \in D, P(x)$
• By finding one value of $x$ where the predicate $P(x)$ is true

Existence Proof (non-contructive)