03. The Mathematical Foundations: Proofs

[!NOTE] This module explores the core principles of 03. The Mathematical Foundations: Proofs, deriving solutions from first principles and hardware constraints to build world-class, production-ready expertise.

1. Why Prove It?

In software engineering, we “verify” code with tests. But tests only prove the code works for certain inputs. In Computer Science, we use Proofs to guarantee an algorithm works for all valid inputs.

To move from a “Junior” to a “Senior” level, you must stop guessing if your code works and start proving it.

2. Induction: The Ladder of Logic

Mathematical Induction is the most powerful tool for proving Recursive algorithms.

How it Works

  1. Base Case: Prove the algorithm works for the smallest input (e.g., n=1).
  2. Inductive Step: Assume it works for n=k. Prove that it must therefore work for n=k+1.

Analogy: If you can step onto the first rung of a ladder (Base Case), and you can always move from one rung to the next (Inductive Step), you can reach any height!

3. Loop Invariants: Proving Loops

For Iterative algorithms (loops), we use a “Loop Invariant”. An invariant is a truth that remains unchanged after every iteration of a loop.

The 3 Stages of an Invariant

  1. Initialization: It is true before the first iteration.
  2. Maintenance: If it’s true before an iteration, it remains true after the iteration.
  3. Termination: When the loop stops, the invariant gives us the proof that the algorithm succeeded.

Example: Finding Max

Invariant: “At the start of each iteration i, max<sub>val</sub> contains the maximum of the elements arr[0...i-1].”

When i = arr.length, the invariant tells us max<sub>val</sub> is the maximum of the entire array. Goal achieved.

4. Proof by Contradiction

To prove something is true, you assume it is false and show that this assumption leads to an impossible situation (an absurdity).

Classic Example: Proving that a search algorithm is optimal.

  • Assume there is a faster way to find an item in a sorted list than O(\log n).
  • Through logic, we prove this would require looking at fewer than \log n items.
  • But with k items looked at, we can only distinguish 2k possibilities.
  • If 2k < n, we haven’t checked enough “possibilities” to guarantee the result.
  • Contradiction! Therefore, O(\log n) is the lower bound.

Next Steps

With the logic proven, we can now move to the language of efficiency: Time and Space Complexity.