Imagine infinitely many dominoes standing in a row, and you want to prove "all of them fall." You can't push each one by hand. Induction says: you only need to prove two things—the first one falls; and "whenever any one falls, it knocks over the next." Once both hold, the fate of all infinitely many is sealed.
The elegance of induction is compressing "verify infinitely many statements" into "verify one starting point + one propagation rule." You never actually walk infinitely many steps—you merely prove "this chain has no broken link." A chain that can't break is a chain that all falls.
$P(n)$ is a statement about the natural number $n$. The base case proves $P(0)$; the inductive step assumes $P(k)$ (the inductive hypothesis) and derives $P(k{+}1)$. With both, $P(n)$ holds for all $n$. Note the hypothesis isn't "secretly assuming what you want to prove"—you assume "some domino falls" and prove "it knocks over the next," which is propagation, not the conclusion itself.
Induction reveals something profound: infinity need not be fought with infinite effort. A finite two-step argument covers infinitely many statements. Deeper still, it isn't a mere "trick"—in the Peano axioms, the induction principle is part of the very definition of the natural numbers. "Why can naturals be inducted on" is not a theorem but a stipulation: we call something a natural number precisely when it satisfies induction. Induction and the naturals are two faces of one thing. Its variants—strong induction (assume $P(0),\dots,P(k)$) and structural induction (over trees, expressions)—generalize the same spirit.
Induction is the workhorse of proof in computer science. Proving a loop invariant—"some property still holds after each iteration"—is induction on the iteration count, and it's the heart of program-correctness proofs. The correctness of recursive algorithms (mergesort, fast exponentiation) rests on structural induction. Type-system soundness, order-preserving compiler optimizations, and the safety proofs of distributed protocols are all induction at bottom. Any software guarantee that "holds for every size" has induction standing behind it.
A Russian nesting doll: open one and inside is a smaller, identical doll, until the innermost is too small to open. Recursion has this shape—to solve a big problem, first solve a smaller instance of the same problem, shrinking layer by layer until you reach a smallest case whose answer is obvious (the base case).
If induction is "climbing up in proof" (from $k$ to $k{+}1$), recursion is "drilling down in computation" (reducing $n$ to $n{-}1$). They are two faces of one coin: induction guarantees recursion terminates and is correct; recursion is induction incarnate in the computational world.
A recurrence relation defines the current term from smaller terms, plus initial conditions (base cases) that anchor the chain to the ground. Above is the Fibonacci sequence—strip the initial conditions and it's just a dangling rule; supply $F(0),F(1)$ and the whole sequence is uniquely pinned down. A recursive function translates this definition directly into code: the function calls itself, stopping at the base case.
One recurrence can wear startlingly different faces. Fibonacci's recurrence is the plainest addition, yet its closed form is $F(n)=\frac{\varphi^n-\psi^n}{\sqrt5}$, where $\varphi=\frac{1+\sqrt5}{2}$ is exactly the golden ratio—a formula full of irrationals and powers that spits out an integer every time. Why does a rule about adding integers secretly harbor the golden ratio? Because the recurrence corresponds to a characteristic equation $x^2=x+1$, whose root is $\varphi$. A recurrence's "growth gene" is written in the roots of its characteristic equation—a hidden bridge between the discrete world and algebra, and continuous growth rates.
Divide-and-conquer algorithms (mergesort, quicksort, FFT) "split the problem in half, recurse on each, then merge," with running time described by the recurrence $T(n)=2T(n/2)+O(n)$, solved at a glance to $O(n\log n)$ by the Master Theorem. Dynamic programming is essentially "recursion with overlapping subproblems"—above, $F2$ is recomputed; memoization (storing what's been computed) cuts exponential repetition down to linear. Parsing, fractal generation, recurrent neural networks, and the entire functional programming paradigm are all built on recursion.
You wrote a program; one run takes 3 milliseconds—that number is nearly useless. Switch machines or compilers and it changes. The question that decides fate is: when the data doubles, how does the time change? Double? Quadruple? Stay put? Big-O notation drops all constants and lower-order terms, keeping only the "shape of growth," because when data is large enough, only the growth rate is destiny; constants are just noise.
A slow $O(n)$ algorithm on a slow machine will, in the long run, crush a clever $O(n^2)$ one on a fast machine—as long as $n$ is big enough. Big-O measures not "how fast right now" but "will it hit a wall when it scales."
Read: once $n$ exceeds some threshold $n_0$, $f$ is forever pinned below some constant multiple $c\,g(n)$ of $g$. The $c$ absorbs all hardware and constant-factor differences; $n_0$ says "we only care about sufficiently large scales." So $3n^2+100n+5 = O(n^2)$—the lower-order $100n$ and constant $5$ are drowned out for large $n$. Big-O is a pair of glasses that sees only the trend, never the detail.
Big-O lifts algorithms out of machine, language, and era, making them purely comparable mathematical objects. Its most striking feature: different O's are not "a bit faster or slower" but a chasm between "feasible and infeasible". $O(n)$ vs $O(n^2)$ differ by a factor of a million at $n=10^6$; $O(n)$ vs $O(2^n)$ exceeds the number of atoms in the universe. This "polynomial vs exponential" divide is the heart of theoretical computer science's deepest open problem, P vs NP—some problems we can verify an answer to, yet seem unable to quickly find one. A single notation carves out the boundary of "what computation can do."
Why do databases build indexes? To drop lookup from an $O(n)$ full-table scan to an $O(\log n)$ B-tree—the larger the data, the more fatal the gap. Hash tables support nearly every system with $O(1)$ average lookup. The most vivid current example is large models: the self-attention in a Transformer is $O(n^2)$ (each token attends to all tokens), which is precisely the long-context bottleneck—the entire motivation behind FlashAttention, linear attention, and state-space models is to bring that $n^2$ down. Big-O isn't an academic concept; it decides daily whether context can go from 8K to a million.
Continuous probability is "measuring area"; discrete probability is "counting." List every possible outcome (the sample space), and if each is equally likely, the probability of an event is simply the number of favorable outcomes ÷ the total number of outcomes. Roll an even number on a die? $3/6$. Draw a heart from a deck? $13/52$. Probability here collapses into pure combinatorial counting—if you can count, you can compute the probability.
For this reason, discrete probability and combinatorics are conjoined twins: the hard part of computing a probability is usually not the probability itself but "counting the favorable cases cleanly, with no double-counting and no omissions."
$\Omega$ is the sample space (the set of all outcomes), $A\subseteq\Omega$ is an event, and $|A|$ is the number of outcomes it contains. When outcomes are equally likely, probability is a ratio of two counts. The expectation $\mathbb{E}[X]$ is the "weighted average" of the random variable $X$—each value times its probability, summed—representing "how much you get on average in the long run." It is the single most useful number in discrete probability.
Discrete probability's most elegant weapon is linearity of expectation: $\mathbb{E}[X+Y]=\mathbb{E}[X]+\mathbb{E}[Y]$, whether or not $X$ and $Y$ are independent. This looks bland but is astonishingly powerful—many problems that seem to entangle all the correlations, once decomposed into a sum of simple random variables whose expectations are computed separately and added, yield their answer instantly. For instance, "in a shuffled deck, how many cards on average land in their original position": computing it directly means facing complex correlations; by linearity, the answer is cleanly $1$. Breaking uncertainty into blocks you can count one by one and add up—that is the core beauty of discrete probability.
Randomization is the secret weapon of modern algorithms: randomized quicksort uses a "random pivot" to make the worst case almost impossible; hashing achieves load balancing through random distribution; probabilistic data structures like the Bloom filter trade a small, controllable error rate for enormous space savings. Machine learning trains via random sampling (mini-batches, dropout), and the "temperature" in large-model generation is precisely sampling from the discrete probability distribution over the next token. Anywhere a decision must be made under uncertainty, discrete probability is holding it up.