Proofs

Proofs are often used to prove an algorithm will work for some or all cases.

Proof by Induction

First, prove the first case. Then assume that the $k$th case is true. Prove the $(k+1)$th case

Proof by Contradiction

Create a conjecture that is the opposite of what you are trying to prove. Prove that such a conjecture cannot be true as it creates contradictions. As such the original proposal must be true.