Proofs & Logic — How We Know

Proof by induction

continues from lesson 3 — values defined earlier in the course stay live here

ELI5: induction is the domino effect — show the first domino falls, and that each domino topples the next, and you've proved all of them fall. A favourite: the sum of the first n cubes equals (1 + 2 + ⋯ + n)² — a genuinely surprising identity.

cubes_{4} := Sum("i^3", "i", 1, 4)

100

1³ + 2³ + 3³ + 4³ = 100

squared_{sum} = \left(\frac{4 \cdot 5}{2}\right)^{2}

100

(1 + 2 + 3 + 4)² = 10² = 100

✓ pass

cubes_{4} == squared_{sum}

sum of cubes = (sum of integers)² — proved for all n by induction

Real-world hook: induction is how we prove an algorithm is correct for every input size, not just the ones we tested — the foundation of trustworthy software.

Try it yourself: what is the sum of the first 5 cubes (1³ + 2³ + ⋯ + 5³)? (The identity says it equals (1+2+3+4+5)².)

cubesum_{you} = \left(\frac{5 \cdot 6}{2}\right)^{2}

225

✏️ Your turn: sum the first 5 cubes. Use the identity (1+2+3+4+5)², and the check compares against adding the cubes directly.

✓ pass

cubesum_{you} == Sum("i^3", "i", 1, 5)

green when your total matches the brute-force sum of cubes

You've reached the frontier of the core sequence. The reasoning here is what every earlier course quietly relied on.