Proof


A proof is a rigorous argument meant to convince readers that a theorem is true. They usually take the form of a step-by-step guide on how to reach a conclusion through the use of given assumptions. These assumptions can be axioms or other already-proven theorems.

There are many types of proofs: direct proofs, proofs by contradiction, proofs by exhaustion, proofs by induction, and the list goes on. Soon enough, you'll be well-acquainted with all of them!

⚠ Before writing a proof, you should experiment a lot! The most difficult part of writing a proof is creating the reasoning behind it. Never begin writing a proof until you've planned a complete path from start to finish, nothing's more awful than realizing you've gone the wrong way when you're already deep into the proof. The final version of your proof should be as clean as possible.
Contents

Format


The format of a proof should be simple and clear. First, write "Theorem:" and state the theorem you intend to prove. Then, write "Proof:" and begin taking steps to reach the conclusion. After showing the theorem is true, end your proof with the end-of-proof symbol "\(■\)".

Theorem: The sum of two odd integers is even.
Proof: Let \(n\) and \(m\) be odd integers, where \(n=2k+1\) for some integer \(k\) and \(m=2j+1\) for some integer \(j.\)
Their sum must be:$$n+m$$ Substituting in the definitions of \(n\) and \(m\):$$(2k+1)+(2j+1)$$$$2k+2j+2$$$$2(k+j+1)$$ Since \(k\) and \(j\) are integers, \((k+j+1)\) must also be an integer, which we can rewrite as \(x\):$$2x$$ Now, \(n+m\) has been represented in the form \(2x\), where \(x\) is an integer. This is the definition of an even integer.
Thus, the sum of any two odd integers is even. \(■\)
Logic & Proofs
IntegerRational numberInequalityReal numberTheoremProofStatementProof by exhaustionUniversal generalizationCounterexampleExistence proofExistential instantiationAxiomLogicTruthPropositionCompound propositionLogical operationLogical equivalenceTautologyContradictionLogic lawPredicateDomainQuantifierArgumentRule of inferenceLogical proofDirect proofProof by contrapositiveIrrational numberProof by contradictionProof by casesSummationDisjunctive normal form
Set Theory
SetElementEmpty setUniversal setSubsetPower setCartesian productStringBinary stringEmpty stringSet operationSet identitySet proof
Functions
FunctionFloor functionCeiling functionInverse function
Algorithms
AlgorithmPseudocodeCommandAsymptotic notationTime complexityAtomic operationBrute-force algorithm
Relations
RelationReflexive relationSymmetric relationTransitive relationRelation compositionEquivalence relationEquivalence class
Number Theory
Integer divisionLinear combinationDivision algorithmModular arithmeticPrime factorizationGreatest common divisorLeast common multiplePrimality testFactoring algorithmEuclid's theoremPrime number theoremEuclidean algorithm
Induction
Proof by inductionFibonacci sequenceProof by strong inductionWell-ordering principleSequenceFactorialRecursive definition
Combinatorics
Rule of productRule of sumBijection rulePermutationCombinationComplement ruleExperimentOutcomeSample spaceEventProbabilityProbability distributionUniform distributionMultisetSixfold wayInclusion-exclusion principlePigeonhole principle
Graph Theory
GraphWalkSubgraphRegular graphComplete graphEmpty graphCycle graphHypercube graphBipartite graphComponentEulerian circuitEulerian trailHamiltonian cycleHamiltonian pathTreeHuffman treeSubstringForestPath graphStarSpanning treeWeighted graphMinimum spanning treeGreedy algorithmPrim's algorithm
Recursion
RecursionRecursive algorithmCorrectness proofDivide-and-conquer algorithmSorting algorithmMerge sort