# What a Proof Is > A proof isn't intimidating ceremony - it's an argument so airtight it leaves no room for doubt: a chain of valid steps from things you already accept to the thing you're claiming. Here's how proofs actually work, including the famous techniques. --- # What a Proof Is The word "proof" makes a lot of people freeze - it sounds like a wall of Greek symbols only mathematicians are allowed behind. It isn't. A proof is something you already do informally every time you convince someone of a conclusion they can't wriggle out of: you start from things they already accept, take steps they can't object to, and arrive somewhere they now have to agree with. That's the whole idea. A proof is an argument with the gaps removed. This guide demystifies it. You'll see what a proof actually is (and how it differs from "evidence"), meet the handful of standard techniques that cover almost everything - direct proof, contradiction, contrapositive, cases, the single counterexample - and then unlock the one that feels like magic until it doesn't: **induction**, which lets a few lines prove something true for infinitely many cases at once. If you've written a recursive function, you already think the way induction works. ## How to read this - **Curious what proof even means?** [Phase 1](01-what-a-proof-actually-is.md) is the reframe. - **Want the toolkit?** Read in order - Phase 2 is the techniques, Phase 3 is induction. ## The phases 1. **[What a Proof Actually Is](01-what-a-proof-actually-is.md)** - a gap-free chain from accepted truths to a conclusion, and why that's stronger than evidence. 2. **[The Main Proof Techniques](02-the-main-proof-techniques.md)** - direct, contradiction, contrapositive, cases, and disproof by counterexample. 3. **[Proof by Induction](03-proof-by-induction.md)** - the domino principle, and why it's the same shape as recursion. > This builds on validity from [What Logic Actually Is](/guides/what-logic-actually-is) and the > contrapositive from [Propositional Logic](/guides/propositional-logic). Last in the Logic foundations: > spotting fallacies. --- # What a Proof Actually Is The word "proof" can feel like a wall - something with a velvet rope in front of it, open only to people with chalk dust on their sleeves. Here's the reality: a proof is an ordinary argument, the kind you make when you explain why the restaurant must be closed, or why the missing ten dollars has to be in your other coat. The only difference is that a proof has the gaps taken out. Every place a normal argument says "and so, clearly," a proof stops and fills the space with a reason no one can refuse. That's the whole trick - not genius, patience about gaps. ## What a proof is A proof is a chain. It starts from things you already accept and walks, one careful step at a time, to the claim you want to establish. The things you start from come in three kinds: - **Axioms** - starting assumptions everyone in the room has agreed to accept without further argument. - **Definitions** - the agreed meanings of your words. If "even number" means "a whole number you can write as two times some whole number," that meaning is yours to use, free, whenever you need it. - **Previously-proven results** - anything already established the same way. Once proven, a result is yours to lean on forever; you never re-prove it. From that bedrock, you take **valid** steps. A step is valid when the truth of what came before *forces* the truth of what comes next - the conclusion can't be false if the premises are true. (That word "valid" carries a lot of weight, and it has a precise meaning; see [what logic actually is](/guides/what-logic-actually-is).) You keep taking valid steps until you reach your claim. When you do, the claim isn't *likely* true. It is true, with the same certainty as the bricks you started from - because each step only ever passed that certainty along. So the test for a proof is brutally simple, and you can apply it yourself: > Walk it step by step. At every step, ask: *could someone reasonably deny this, > given everything before it?* If the answer is ever "yes," you have a gap, and > you don't yet have a proof. If the answer is always "no," you do. A proof is exactly an argument where the true answer is always "no." ## Axioms: where the chain is anchored 📝 **Axiom** - a statement accepted as a starting point, without proof, by agreement. Not because it's been proven (it hasn't), and not because it's beyond question, but because *we have to start somewhere.* You can't prove everything from nothing; every chain needs a first link that hangs from open air. This can feel like cheating. It isn't. Think of axioms as the rules of a game you and your reader agree to play. "Two points determine a line" is an axiom of one kind of geometry - nobody proves it, you agree to it, then see what follows. Change the axioms and you get a different game with different - but equally valid - conclusions. Definitions are the other half of your bedrock. An axiom says *what is true to start with*; a definition says *what your words mean*. Both are accepted, not proven. Everything else in the chain has to earn its place. 💡 If an argument ever feels circular or bottomless - "but why is *that* true?" forever - you've usually hit the place where someone forgot to name their axioms. Name them, and the bottom appears. ## Proof vs evidence This distinction changes how you see almost everything, so slow down here. **Evidence** makes a claim *more believable*. You test, you observe, you collect examples, and your confidence goes up. This is how science, courts, and daily life work, and it is enormously powerful. But evidence reasons from particular cases toward a general pattern - that direction is called **inductive** - and it can never reach certainty. There is always one more case you haven't checked. **A proof** makes a claim *certain*. It reasons from general accepted truths down to the specific conclusion - that direction is called **deductive** - and when every step is valid, the conclusion is locked. Not 99.9% likely. Locked. Here is the asymmetry that makes the whole thing sharp. Consider a claim of the form *"every X has property P"* (logicians call this a universal claim; you can read more in [predicate logic and quantifiers](/guides/predicate-logic-and-quantifiers)): ```text Claim: "Every even number greater than 2 is the sum of two primes." Evidence FOR it: 4 = 2 + 2 6 = 3 + 3 8 = 3 + 5 ... checked for billions of numbers, all work. Does this PROVE it? No. It supports it. The very next number could be the one that fails. No pile of confirming examples - however huge - proves a universal claim. A single COUNTEREXAMPLE, on the other hand: one even number that is NOT a sum of two primes would destroy the claim instantly and forever. ``` (That example is real - it's an unsolved problem. Billions of confirming cases, still not a proof.) Read that box twice. Examples can only *support* a "for all" claim; they can never finish it. But one counterexample *settles* it - in the negative. That's why mathematicians hunt counterexamples so eagerly: a single one does what infinite examples cannot. ## For builders You already live with this distinction every day, under a different name. A **passing test** is evidence. A test runs your code on *particular* inputs and checks the output for those inputs - that's induction: "it worked on the cases I tried." A green test suite raises your confidence, and it should, but it checks a finite handful of the (often infinite) inputs your code might see. A **proof** about your code - the kind you do informally when you reason "this loop can't go out of bounds because `i` is always less than `len`" - guarantees *all* inputs at once, by argument rather than by trial. ```text Test: add(2, 3) == 5 ✓ (one case, checked) add(0, 0) == 0 ✓ (one case, checked) add(-1, 1) == 0 ✓ (one case, checked) => evidence that add works. Not a guarantee. Proof: an argument that add(a, b) == a + b for EVERY a and b => a guarantee, covering inputs you never typed. ``` This is the exact reason "the tests pass" is not the same as "the code is correct." Tests sample reality; proofs cover it. Most of the time sampling is all you can afford, and that's fine - but knowing *which* kind of certainty you have keeps you clear-eyed about what could still break. ⚠️ **The gotcha that catches everyone.** "It works on the cases I tried" is not "it works always." A handful of green checks, a few hand-traced examples, a demo that didn't crash - these are evidence, not proof. The moment you say "so it always works" on the strength of examples alone, you've quietly swapped support for certainty, and the bug you ship will be in the case you never tried. 🪖 When examples make you feel sure, name it out loud: *"I have strong evidence, not a proof."* That one sentence has saved more shipped code than any linter. ## Recap - A **proof** is a gap-free chain of **valid** steps from accepted truths to a claim. Every step must be one no reasonable reader could deny. - The accepted truths are **axioms** (agreed starting assumptions), **definitions** (agreed meanings), and **previously-proven results**. - A correct proof gives **certainty** (deductive reasoning). **Evidence** - examples, tests, observations - gives **support** (inductive reasoning), never certainty. - No pile of examples proves a "for all" claim; a single **counterexample** disproves one. - For builders: passing tests are evidence (particular cases); a proof guarantees all inputs. That's why "tests pass" ≠ "code is correct." ## Open-ended exercise A teammate claims: "Our cache never returns stale data - we've tested it on a hundred requests and every one was fresh." Is this a proof? Why or why not? Distinguish between what kind of certainty the tests provide and what kind would be needed to *prove* the claim "the cache never returns stale data" for all possible inputs and all possible future states. A quick check before you move on: ```quiz [ { "q": "Which best describes what a proof is?", "choices": [ "A gap-free chain of valid steps from accepted truths to the claim", "A large collection of examples that all confirm the claim", "An expert vouching that the claim is true", "A claim that has never been shown to be false" ], "answer": 0, "explain": "A proof links accepted truths to the conclusion through steps no one can deny. Examples and authority can support a claim, but they aren't proofs." }, { "q": "You've tested a function on a thousand inputs and they all pass. What have you got?", "choices": [ "A proof that the function is correct for all inputs", "Strong evidence, but not certainty that it works for every input", "Nothing useful, since tests never tell you anything", "A counterexample to the function's correctness" ], "answer": 1, "explain": "Tests check particular cases (induction): they raise confidence but can't cover every possible input. Only an argument covering all inputs would make it certain." }, { "q": "What is an axiom?", "choices": [ "A statement proven from simpler statements", "A claim supported by many examples", "A starting assumption accepted without proof, by agreement", "A claim that turned out to be false" ], "answer": 2, "explain": "An axiom is a starting point accepted without proof. You can't prove everything from nothing, so every chain of reasoning needs agreed first links." } ] ``` --- # The Main Proof Techniques When people say "a proof," they often picture one giant skill you either have or don't. The reality is smaller than that. Most proofs you'll meet are built from a handful of recurring *shapes*. Once you recognize the shape a claim wants, half the work is done - you stop staring at a blank page and start filling in a known template. This phase walks through five of those shapes. None is a trick - each is a sane response to a specific kind of statement, and we'll say *why* each one fits where it does. ```mermaid flowchart LR A[Claim] --> B{Shape?} B -->|if P then Q| C[Direct proof] B -->|if P then Q| D[Contrapositive] B -->|any claim| E[Contradiction] B -->|for all x| F[Cases / Counterexample] C --> G[Conclusion] D --> G E --> G F --> G ``` ## Direct proof: assume the hypothesis, walk to the conclusion The most common shape, and the one you reach for first. A claim of the form "if `P`, then `Q`" asks: *whenever `P` holds, does `Q` follow?* So you assume `P` is true and walk, step by straight step, until you reach `Q`. No detours, no cleverness - the proof *is* the walk. Take a concrete one: the sum of two even numbers is even. "Even" means "divisible by 2," which means you can write the number as 2 times some whole number. That definition is the whole engine of the proof. ```text Claim: if a and b are even, then a + b is even. Assume a and b are even. (this is P, the hypothesis) Then a = 2m for some integer m. (definition of even) And b = 2n for some integer n. (definition of even) So a + b = 2m + 2n = 2(m + n). (factor out the 2) Since m + n is an integer, a + b is 2 times an integer. Therefore a + b is even. (this is Q, the conclusion) ∎ ``` Notice nothing is missing between any two lines. That gap-free quality is what makes it a proof rather than a plausible story. When a claim hands you a clear hypothesis to start from, try direct proof first. ## Proof by contradiction: assume it's false, hit a wall Sometimes walking forward from the hypothesis is awkward, or the claim has no obvious hypothesis to grip. Then try the opposite move: assume the statement is *false*, and show that assumption forces something impossible. If "false" leads to an impossibility, "false" can't hold, so the statement must be true. The mental model is a trap you set on purpose: you let the enemy assumption in, follow where it leads, and watch it walk into a wall it can't get past - like `1 = 0`, or "this number is both even and odd." The classic example is that √2 is irrational - it can't be written as a fraction of two whole numbers. Here's the *idea*, not the full proof: ```text Suppose, for contradiction, that √2 IS a fraction. Write it in lowest terms: √2 = a/b, with a and b sharing no common factor (already reduced). Squaring and rearranging forces a to be even, and then forces b to be even too. But if a and b are both even, they share the factor 2 - which contradicts "lowest terms, no common factor." The assumption collapsed. So √2 is NOT a fraction: it's irrational. ∎ ``` The shape is what matters: assume the negation, derive an impossibility, conclude the original. You'll see this pattern constantly once you know to look for it. ## Proof by contrapositive: flip the implication This one trades a hard direction for an easier one. To prove "if `P`, then `Q`" (written `P → Q`), you may instead prove "if not `Q`, then not `P`" (written `¬Q → ¬P`). The two are *logically equivalent* - true in exactly the same situations, so proving either one proves both. (If "equivalent" feels slippery, the truth-table reasoning behind it lives in [/guides/propositional-logic](/guides/propositional-logic), and the bigger picture of what logic is doing here is in [/guides/what-logic-actually-is](/guides/what-logic-actually-is).) Why flip? Because sometimes `¬Q` is a much friendlier place to start than `P`. A negation can hand you concrete structure to work with. ```text Claim: if n² is even, then n is even. (P → Q) Starting from "n² is even" is awkward. So prove the contrapositive instead: if n is NOT even, then n² is NOT even. (¬Q → ¬P) Assume n is odd. Then n = 2k + 1. n² = (2k + 1)² = 4k² + 4k + 1 = 2(2k² + 2k) + 1, which is odd. So n odd forces n² odd. By contrapositive, n² even forces n even. ∎ ``` Same claim, but the contrapositive gave us an `n = 2k + 1` to expand instead of a square root to wrestle. When the negation of your conclusion is easier to grab than the hypothesis, reach for this. ## Proof by cases: split, then conquer each piece Some claims resist a single line of argument because the objects involved behave differently in different situations. The fix: carve the possibilities into a few *exhaustive* buckets - buckets that together cover every case - and prove the claim inside each. If it holds in every bucket, and the buckets leave nothing out, it holds everywhere. The load-bearing word is *exhaustive*. Miss a case and the proof has a hole. ```text Claim: for every integer n, n² + n is even. Every integer is either even or odd. Two cases: Case 1 - n is even: n = 2k. n² + n = n(n + 1) = 2k(2k + 1), which is 2 times an integer → even. Case 2 - n is odd: n = 2k + 1. n + 1 = 2k + 2 = 2(k + 1), so n + 1 is even. n(n + 1) is (something) times an even number → even. The two cases cover every integer, and both give "even." Therefore n² + n is always even. ∎ ``` The art is choosing cases that are both *exhaustive* (nothing slips through) and *useful* (each gives you something concrete to work with). "Even or odd" did both here. ## Disproof by counterexample: one failure is enough The techniques above all *prove* statements. This one *disproves* them - and it reveals a deep asymmetry worth burning into memory. Consider a claim of the form "for all `x`, `P(x)`" - a universal statement, every single `x` obeys. To disprove it, you don't need a grand argument. You need *one* `x` where `P` fails. That single example, a counterexample, kills the universal claim outright. (Universal "for all" statements and what their negation looks like are the subject of [/guides/predicate-logic-and-quantifiers](/guides/predicate-logic-and-quantifiers).) ```text Claim (false): every prime number is odd. Counterexample: 2 is prime, and 2 is even. One example breaks "every." Claim disproved. ∎ ``` Now the asymmetry, stated bluntly so it sticks: - **One counterexample disproves a "for all" claim** - fully, permanently. - **No pile of examples ever proves a "for all" claim.** You could check a million values, find no counterexample, and still be wrong about the million-and-first. Examples can *suggest* a universal is true and build your intuition. But suggestion isn't proof. To actually *prove* a universal, go back to the techniques above - direct, contradiction, contrapositive, cases - which argue about *all* `x` at once instead of checking them one by one. > The same asymmetry runs the other way for "there exists" claims: to prove "some `x` > has property `P`," one good example is enough; to disprove it, you must rule out > every `x`. Quantifiers flip which direction is cheap. If that's new, it's covered in > [/guides/predicate-logic-and-quantifiers](/guides/predicate-logic-and-quantifiers). ## For builders If you write code, you already use two of these shapes - under different names. **Contradiction is how you isolate a bug.** When you say "assume this layer is correct - then the data reaching the next layer should look like *this* - but it actually looks like *that*, which is impossible if the layer were correct, so the bug is in this layer," you're running a proof by contradiction. That's *reductio* with a debugger attached. **A counterexample is a failing test case.** The claim "this function always works" is a universal: for all inputs, it behaves. A green test suite of a thousand passing cases does *not* prove it, same as a thousand examples don't prove a math universal. But one red test, one input that returns the wrong answer, disproves "it always works" instantly - a single reproducible failing test is a counterexample, and counterexamples are decisive. ## Recap - **Direct proof** - assume the hypothesis, derive the conclusion step by gap-free step. Your default for "if `P` then `Q`." - **Proof by contradiction** - assume the statement is false, derive an impossibility, conclude it's true. - **Proof by contrapositive** - prove `¬Q → ¬P` instead of `P → Q`; equivalent, and often easier to start from. - **Proof by cases** - split into exhaustive buckets, prove each. Watch that the cases miss nothing. - **Disproof by counterexample** - one failing `x` kills a "for all" claim; no number of examples ever proves one. ## Open-ended exercise Pick a claim you believe is true - something small and concrete, like "the sum of two odd numbers is even" or "a function that checks `x > 0` and `x < 10` can be rewritten as `x >= 1 && x <= 9`." Now choose *one* of the five proof shapes from this phase and sketch how you'd structure a proof for it. You don't need to write every step - just identify: what's the hypothesis, what's the conclusion, and which shape fits best? The exercise is to feel the difference between "I think this is true" and "I can show why it must be true." Pick a quiz to check the parts that trip people up most: ```quiz [ { "q": "In a proof by contradiction, what do you assume at the start?", "choices": [ "That the statement you want to prove is false", "That the statement you want to prove is true", "That the hypothesis is false but the conclusion is true", "Nothing - you derive the statement with no assumptions" ], "answer": 0, "explain": "You assume the statement is false, then show that assumption forces an impossibility. Since 'false' leads to a wall, the statement must be true." }, { "q": "Why is proving the contrapositive (¬Q → ¬P) a valid way to prove P → Q?", "choices": [ "Because the contrapositive is usually shorter to write", "Because P → Q and ¬Q → ¬P are logically equivalent - true in exactly the same situations", "Because proving any related statement is good enough", "Because the converse Q → P is always true too" ], "answer": 1, "explain": "The two statements are logically equivalent: proving either one proves both. Being shorter is a nice bonus, not the reason it's valid." }, { "q": "You want to disprove 'every prime number is odd.' What's enough?", "choices": [ "Checking that the first hundred primes are odd", "A general argument about all primes at once", "One counterexample, such as 2 (prime and even)", "Showing most primes are odd" ], "answer": 2, "explain": "A single counterexample disproves a 'for all' claim outright. 2 is prime and even, so 'every prime is odd' is false. Examples that fit the claim never prove it." } ] ``` --- # Proof by Induction One kind of claim should make you nervous: a claim about *all* natural numbers. "This formula works for every n." Every n? There are infinitely many - you can't check them one by one, you'd never finish. So how could anyone prove something true for an infinite list of cases? Induction is the answer, and it does the whole infinite job with a small, finite amount of work. Once you see the trick, it stops feeling like a trick and starts feeling like the most natural thing in the world. ## The domino metaphor Picture a long line of dominoes, stretching off as far as you can see. You want to know: will *all* of them fall? You don't need to push each one - you need exactly two things to be true. First, the **first domino falls**. Someone tips it over; the chain has to start somewhere. Second, the dominoes are **spaced so that each one knocks over the next** - anywhere in the line, if a domino falls, the one after it falls too. If both hold, then *all* the dominoes fall, and you know it without watching. The first falls, so the second falls. The second falls, so the third falls. The rule carries you down the entire line, forever. That's induction: two facts, one about the start and one about the *step*, and between them they cover infinitely many cases. ## The formal shape Suppose you have a statement `P(n)` - some claim that depends on a natural number n. You want to prove `P(n)` is true for *every* natural number n. Induction says: do exactly two things. **Base case.** Prove `P(1)`. (Sometimes you start at `P(0)` instead - whichever is the first number you care about.) This is tipping the first domino. **Inductive step.** Prove that *if* `P(k)` is true, *then* `P(k+1)` is true. You assume `P(k)` holds for some unspecified k - this assumption is the **inductive hypothesis** - and from it you derive `P(k+1)`. This is the spacing between dominoes: each case knocks over the next. Put those two together and you've proved `P(n)` for all n. The base case starts the chain; the inductive step propagates it forever. Notice what the inductive step really is: an implication, `P(k) → P(k+1)`. That's the same conditional you met in [propositional logic](/guides/propositional-logic). Induction is built from logical tools you already have - it only aims them at infinity. ## A worked example The classic first proof. The sum of the numbers from 1 up to n has a tidy closed form: `1 + 2 + 3 + ... + n = n(n+1)/2` Call that claim `P(n)` and prove it for all n by induction. ```text Claim P(n): 1 + 2 + ... + n = n(n+1)/2 --- Base case: n = 1 --- Left side: 1 Right side: 1(1+1)/2 = 1*2/2 = 1 Both sides equal 1, so P(1) is true. --- Inductive step: assume P(k), prove P(k+1) --- Inductive hypothesis (assume true): 1 + 2 + ... + k = k(k+1)/2 We want to show P(k+1): 1 + 2 + ... + k + (k+1) = (k+1)(k+2)/2 Start from the left side of P(k+1): (1 + 2 + ... + k) + (k+1) Replace the part in parentheses using the hypothesis: = k(k+1)/2 + (k+1) Put both terms over a common denominator: = k(k+1)/2 + 2(k+1)/2 = [k(k+1) + 2(k+1)] / 2 Factor out (k+1): = (k+1)(k+2) / 2 That is exactly the right side of P(k+1). So P(k) implies P(k+1). --- Conclusion --- Base case holds, and each case implies the next. Therefore P(n) holds for every natural number n. ``` Read the inductive step again slowly - it's where the whole idea lives. We never proved the formula for `k+1` from scratch. We *borrowed* the result for `k` - that's the inductive hypothesis - and only added one more term. The hard part was already done for us, by us, one step earlier. ## Why it's valid Here's the part that feels uncomfortable at first: in the inductive step, you assume the very kind of thing you're trying to prove. Isn't that circular? It isn't, and the domino picture shows why. You're not assuming `P(k)` is true for all k. You're proving a *connection*: "wherever the chain has reached, it reaches one further." That connection is a single, reusable rule. The base case then proves the chain has actually started. Combine "it started" with "it always continues" and you get "it reaches everywhere" - no circularity, only a rule applied over and over. This is the deep payoff. The inductive step is proved *once*, in general, for an arbitrary k. But because k stands for any number, that one proof does the work of infinitely many. You establish infinitely many cases with finite effort, because you found the *pattern* that links each case to the next instead of grinding through them individually. Finite work, infinite reach. ## For builders If you write code, you already think this way - under a different name. Induction is the exact shape of **recursion**. A recursive function has a **base case** (the input small enough to answer directly) and a **recursive case** (reduce the problem to a slightly smaller one and trust the function to handle that). Sound familiar? Base case plus a step that reaches the next case down. ```text function sumTo(n): if n == 1: <- base case return 1 else: return n + sumTo(n - 1) <- step: reduce to a smaller case ``` When you reason about whether a recursive function is *correct*, you're doing an induction proof, named or not. You check the base case returns the right answer. Then you assume the recursive call on the smaller input is correct (the inductive hypothesis), and check the function builds the right answer on top of it. If both hold, the function is correct for all inputs - because the dominoes fall. So induction isn't an exotic math ritual. It's the same trust you place in a recursive call, made explicit. ## ⚠️ You need both parts The most common way to wreck an induction proof is to skip the base case. It's tempting, because the inductive step often feels like the clever, satisfying part. But without a base case, nothing anchors the chain. You can prove "each domino knocks over the next" perfectly - and if no domino ever gets tipped over, *not a single one falls*. The implications are all true and completely useless, because they're never triggered. You can even "prove" outright false statements this way if you drop the base case. The base case isn't a formality to rush past. It's the thing that turns an endless chain of *ifs* into actual truth. The other failure is a broken step: an inductive step that quietly assumes something extra, or works for some k and not others. The step has to hold for *every* k, with nothing borrowed except the hypothesis itself. ## Where this leaves you You've now seen the three pillars of this guide: [what a proof actually is](01-what-a-proof-actually-is.md) - an argument that forces a conclusion; [the main techniques](02-the-main-proof-techniques.md) - direct proof, contradiction, contrapositive; and now induction, the tool for taming infinity, two steps that topple an endless line of cases. That's a real foundation - you can read a proof and follow why each line is forced, and you have a vocabulary for the moves people make to get there. One more skill rounds it out, pointing the other direction. So far you've studied how arguments go *right*. The natural companion is learning how they go *wrong* - the recurring patterns of bad reasoning that look convincing until you name them. If proof is how you build trust in a conclusion, fallacy-spotting is how you withhold it when it hasn't been earned. That's the last Logic foundation, and where the whole toolkit starts paying off in everyday life. ## Open-ended exercise Prove by induction that the sum of the first `n` natural numbers is `n(n+1)/2`. Write out the base case (n = 1) and the inductive step (assume true for n, prove for n+1). The structure is identical to a recursive function that builds on a smaller input - see the connection? A quick check before you go: ```quiz [ { "q": "What are the two parts every induction proof needs?", "choices": [ "A base case and an inductive step", "A hypothesis and a conclusion", "A contradiction and a contrapositive", "An example and a counterexample" ], "answer": 0, "explain": "You prove the first case (base case), then prove that any case implies the next (inductive step). Together they cover all natural numbers." }, { "q": "In the domino picture, what does the base case correspond to?", "choices": [ "Spacing the dominoes so each knocks over the next", "Tipping over the very first domino", "Counting how many dominoes there are", "Checking that the last domino falls" ], "answer": 1, "explain": "The base case starts the chain - it tips the first domino. Without it, the 'each knocks over the next' rule is true but never triggered, so nothing falls." }, { "q": "Why do programmers already understand induction?", "choices": [ "Because every loop runs a fixed number of times", "Because induction is only used in mathematics, not code", "Because recursion has the same shape: a base case plus a step that reduces to the next case", "Because compilers prove programs correct automatically" ], "answer": 2, "explain": "Reasoning that a recursive function is correct IS an induction proof: the base case answers directly, and you assume the smaller recursive call is correct (the inductive hypothesis) to show the whole call is." } ] ```