Proof is the method by which mathematics separates assertion from knowledge. A statement becomes a theorem only when it follows from accepted assumptions by valid reasoning. This chapter introduces the main proof techniques used across mathematics.
A proof technique is not a trick. It is a disciplined pattern of argument. Each technique is suited to a different kind of statement and a different kind of structure.
Direct proof begins with the assumptions and derives the conclusion step by step. It is the most transparent method and often the first one to try. When a statement has the form “if , then ,” a direct proof assumes and proves .
Proof by contradiction works by assuming the negation of the desired conclusion and deriving an impossibility. It is especially useful when the conclusion is hard to construct directly, but its failure has strong consequences.
Induction and recursion are used for objects built in stages. Natural numbers, lists, trees, syntax, algorithms, and recursively defined structures all support this style of reasoning. Induction proves that a property holds at every stage by proving that it starts correctly and is preserved by the construction rule.
Constructive proofs provide witnesses. To prove that an object exists, they build the object or give a method to obtain it. This style connects proof with computation and is central in algorithmic mathematics and formal verification.
Probabilistic and combinatorial proofs use counting, random choice, or finite structure to establish existence or identity. They often prove that something must exist without immediately displaying a concrete example, or they count the same object in two different ways.
These techniques often combine. A proof may begin directly, use induction inside a lemma, argue by contradiction at a key step, and finish with a construction. The important skill is choosing the method that matches the logical shape of the claim.
The sections that follow present these techniques in detail: direct proof, proof by contradiction, induction and recursion, constructive proof, and probabilistic or combinatorial proof.