Proof Techniques

Goldbach's conjecture has been verified for every even integer up to 4 * 10^18, yet mathematicians still call it a conjecture because no amount of testing covers every case. Algorithm correctness has the same shape: a function can pass a hundred unit tests and still fail on the empty list or the input size your tests never reached. **Basic Proof Techniques** equips you with the small set of argument styles that turn intuition into certainty about correctness, complexity bounds, and data structure invariants. Direct proof chains definitions and prior facts to a claim. Proof by contradiction assumes the opposite and derives a logical impossibility, as in the irrationality of `sqrt(2)` and the `Omega(n log n)` lower bound for comparison sorts. Mathematical induction, in weak and strong forms, proves statements over the natural numbers via a base case and an inductive step, the backbone of recurrence solutions and loop invariants. Proof by contraposition swaps `P implies Q` for the equivalent `not Q implies not P`, and proof by cases breaks a claim into exhaustive subcases. This lesson builds on **Discrete Mathematics Basics**, where you met sets, propositional logic, implications, and the first taste of formal proof. Here those informal sketches become the disciplined patterns that algorithm analysis, theoretical CS, and clean engineering arguments all rely on. With proofs in hand, you have completed the foundations track and are ready to step into **Arrays & Strings** and the rest of the data structures curriculum, armed to analyze every operation rigorously.

Almost every conditional you have ever written is a tiny piece of propositional logic, and almost every collection you have ever stored is, mathematically, a set. **Discrete Mathematics Basics** makes that connection explicit, giving you the formal vocabulary that data structures, graph algorithms, database queries, and correctness arguments all sit on top of. This lesson walks you through three pillars of discrete math used throughout DSA. First, **sets** and the operations on them: union, intersection, difference, complement, subset, and membership, the same ideas baked into hash sets and array problems. Second, **propositional logic**: the operators `AND`, `OR`, `NOT`, and implication, plus truth tables for evaluating compound expressions; this is the math behind every Boolean condition in your code. Third, **binary relations** and their properties (reflexive, symmetric, transitive), which generalize the way edges connect nodes in graphs and rows connect in databases. Along the way you will get a first taste of formal proof: how to argue that two sets are equal or that a logical equivalence always holds. This lesson assumes only basic programming familiarity, so no specific DSA prerequisite is required. If you have written `if (x && !y)` or used a hash set, you already have informal intuition for everything we will formalize here. From here you will move into **Combinatorics Basics**, where you will use these set and counting foundations to count permutations, combinations, and arrangements (the math behind backtracking and many complexity proofs).

Comparison-based sorting cannot do better than `O(n log n)`. That is not a statement about merge sort or quick sort or any specific algorithm; it is a statement about every possible algorithm in this model, including ones nobody has invented yet. The proof is a counting argument over decision trees, and learning to read it changes how you reason about algorithmic limits forever. Lower bounds, NP-completeness, P versus NP, and loop invariants all live in the same theoretical neighborhood. **Complexity & Proof Intuition (Optional)** is an enrichment tour of that neighborhood. You will use loop invariants to prove iterative algorithms correct, revisit amortized analysis with the potential method, work through NP-completeness via polynomial-time reductions and the Cook-Levin theorem, examine the P vs. NP question and its implications, derive the `Omega(n log n)` comparison-sorting lower bound via decision trees, and meet the broader complexity zoo (co-NP, PSPACE, EXP). This lesson rests on three earlier ideas. **Asymptotic Analysis Fundamentals** gave you the language of growth rates that complexity classes refine. **Dynamic Programming (Intro)** and **Greedy (Intro)** showed you exact polynomial-time algorithms; this lesson asks which problems will never have one. This concludes the algorithms track. From here, the natural next step is sustained problem solving on hard interview problems and competitive programming contests that exercise the full toolkit you have built.