Proof: how you know, not how likely

Sets, boolean algebra and Big-O all rest on one move you have been making silently: checking a few cases and deciding the pattern holds. For a two-element set that is fine, because you can look at everything. For a claim about every integer it is not, and the whole difference between a professional and a beginner hides in that gap. A proof is not a stronger test. It is a different kind of object: a finite argument that covers infinitely many cases at once.

First, read the claim carefully, because most bad proofs attack a different sentence than the one on the board. A claim that says for every integer n has no exceptions by definition, and a claim that says there exists an n asks you to produce one witness. Those two need opposite strategies. The claim below looks excellent. Run it and it holds for forty consecutive values, which is far better than most patterns you have trusted.

claim: for every integer n >= 1,  n^2 + n + 41  is prime

n = 1    43         prime
n = 2    47         prime
n = 3    53         prime
n = 4    61         prime
n = 5    71         prime
n = 10   151        prime
n = 20   461        prime
n = 39   1601       prime
n = 40   1681 = 41 * 41   composite

confirmed: 39 cases before that one

At n = 40 the value collapses into a product. That single case is a complete, final disproof, and it costs one line. This asymmetry is the most useful thing in the whole lesson: to prove a universal claim you must argue about all cases at once, but to destroy it you need exactly one. Notice also what the forty successes were worth — nothing. They were not weak evidence for the claim, they were no evidence at all, because the claim was already false the whole time. When you search for a counterexample, search the boundaries: n = 0, n = 1, negative numbers, the empty list, the largest value your type can hold. Most false universal claims about code die at an edge case, not in the middle.

A direct proof is the ordinary kind: start from the definitions and arrive at the claim without assuming anything you have not established. When the argument needs different reasoning in different situations, split into cases and make sure the cases cover everything. The claim below has a two-line proof, but it is only a proof because the last line states that every integer falls into one of the two cases. Without that sentence you have shown two examples, not a theorem.

claim: for every integer n,  n^2 + n  is even

n^2 + n  =  n * (n + 1)

case A:  n = 2k       ->  n * (n + 1) = 2 * k * (n + 1)
case B:  n + 1 = 2k   ->  n * (n + 1) = 2 * k * n

int(n) = A union B

Proof by contradiction is for claims that are hard to attack head-on, usually statements that something does not exist. You assume the opposite, then follow the consequences until two facts cannot both be true. The classic example is below. Every step is ordinary algebra plus one arithmetic fact: if a squared is even then a is even. The contradiction is not that something surprising happened, it is that the result attacks the assumption you started with, namely that a and b had no common factor.

claim: no integers a, b with  sqrt(2) = a / b

assume integers a, b exist, gcd(a, b) = 1

  a / b   = sqrt(2)
  a^2     = 2 * b^2
  a^2 even              ->  a = 2k
  4 * k^2 = 2 * b^2
  b^2     = 2 * k^2     ->  b = 2m
  gcd(a, b) >= 2  ->  contradicts gcd(a, b) = 1

assumption false

That last point is where most failed contradiction proofs die, and it is worth naming the dead end so you can recognise it. If your assumption was loose, the contradiction you reach may only show that your assumption was inconvenient, not false. Assuming a fraction with a common factor would have reached no contradiction at all. The fix is never to push harder on the algebra; it is to go back and assume the strongest, most specific version of the opposite. A contradiction proof is only as good as the assumption it kills.

So what is a test worth? A great deal, but it is not a proof and it does not become one when you add more tests. Evidence raises your confidence; a proof ends the question. Real engineering needs both, and confusing them is how systems get shipped with a claim nobody actually checked. The honest position is narrow and useful: my proof shows the algorithm returns a sorted array, and my tests show that it terminates within the memory we have. Neither sentence claims the other.