EntCSExplore. Visualise. Understand.

Everything on the site.

Big-O notationAlgorithms · Count the steps in real loops, then compare n, n log n, n² and 2ⁿ on a live chart.RecursionAlgorithms · Watch frames push and pop on the call stack for factorial and Fibonacci.BFS vs DFSAlgorithms · A queue against a stack: draw a graph and see which order each search visits it in.Sorting algorithmsAlgorithms · Seven sorts on the same input, with comparison, swap and write counts side by side.Binary searchAlgorithms · Halve the range, probe the middle, repeat: with lo, mid and hi drawn on the array.Sets, relations and functionsDiscrete maths · Shade any set expression on a Venn diagram and test a relation for its properties.Proof by inductionDiscrete maths · Four worked proofs revealed one step at a time, and a broken one to diagnose.CombinatoricsDiscrete maths · An exact nPr and nCr calculator, and a Pascal’s triangle that shows its own addition rule.Boolean algebraDiscrete maths · The laws, De Morgan, and normal forms, with a truth-table generator built in.Finite-state machinesTheory · Build a DFA in a table, see it drawn, and run strings through it one symbol at a time.Domain theoryTheory · Why recursion needs least fixed points, and how CPOs, Scott continuity and powerdomains supply them.Truth table generatorTools · Expression in, truth table out: with DNF, CNF, a minimal form and LaTeX.Graph traversal visualiserTools · Draw a graph, then animate BFS, DFS and Dijkstra with the frontier shown.Recursion tree visualiserTools · Paste a recursive function or a recurrence and see its call tree and call count.Gradient descentML maths · Drag the starting point, set the learning rate, and watch it converge or blow up.Vectors and embeddingsML maths · Bend the plane with a 2×2 matrix and measure how close toy word vectors are.Softmax and cross-entropyML maths · Edit the logits and watch the probabilities, the loss and the gradient update live.AttentionML maths · Q, K and V for three tokens, a live score heatmap, and the weighted sum of values.Formatting a CS paper in LaTeXLaTeX · Page limits, \documentclass, front matter, theorem environments and the bibliography.Camera-ready checklistLaTeX · Fonts embedded, PDF/A, copyright form, source bundle, and why final versions get rejected.LaTeX templatesLaTeX · Where the official classes live, plus a minimal article template you can copy.AlgorithmsSection · Step-through visualisations of sorting, searching, recursion, graph traversal and Big-O growth, each with pseudocode that highlights the line being run.Discrete mathsSection · Sets, relations and functions, proof by induction, counting, and Boolean algebra, explained with worked examples and small interactive checkers.TheorySection · Finite-state machines, automata and the mathematical semantics of programming languages, explained from first principles.ML mathsSection · Gradient descent, vectors and embeddings, softmax and cross-entropy, and attention, each with a formula, a worked numeric example and a live version.ToolsSection · A truth-table generator with CNF, DNF and LaTeX output, a graph-traversal visualiser for BFS, DFS and Dijkstra, and a recursion-tree visualiser.LaTeXSection · How to format a CS conference or workshop paper in LaTeX, a camera-ready checklist, and a minimal template you can adapt.
Discrete maths

Proof by induction, with worked proofs

Mathematical induction proves a statement for every natural number at once: show it holds for the first one, and show that whenever it holds for one number it holds for the next. Work through four proofs one step at a time, then find the flaw in a famous wrong one.

Interactive: Step-reveal proofs and a numerical claim checkerUpdated

The principle

Let P(n)P(n) be a statement about a natural number nn, such as “1+2+⋯+n=n(n+1)/21 + 2 + \dots + n = n(n+1)/2”. To prove P(n)P(n) for all n≥n0n \ge n_0 by induction, you prove two things:

  1. Base case: P(n0)P(n_0) is true.
  2. Inductive step: for every k≥n0k \ge n_0, if P(k)P(k) is true, then P(k+1)P(k+1) is true. The assumption P(k)P(k) is called the inductive hypothesis.

Together these give P(n0)P(n_0), then P(n0+1)P(n_0 + 1), then P(n0+2)P(n_0 + 2), and so on, with no gaps. The usual picture is an infinite row of dominoes: the base case knocks over the first one, and the inductive step guarantees each falling domino knocks over the next.

The inductive step is an implication You do not prove P(k)P(k) in the inductive step; you assume it and derive P(k+1)P(k+1). That is not circular, because the base case supplies the first true instance and the implication carries it forward.

Checking cases is not a proof

Before proving something it is worth testing it. The checker computes both sides of a few claims for the first nn values. The last claim is a warning: n2+n+41n^2 + n + 41 is prime for n=1,…,39n = 1, \dots, 39, then fails at n=40n = 40, where it equals 41241^2. However many cases you check, only a proof covers them all.

Check a claim for the first few n

nLeft sideRight sideHolds?

Four worked proofs

Each proof reveals one step at a time. Before revealing the next step, try to predict it.

Proof 1: the sum of the first n integers

Claim. For every n≥1n \ge 1, 1+2+⋯+n=n(n+1)21 + 2 + \dots + n = \dfrac{n(n+1)}{2}.

  1. Base case, n=1n = 1. The left side is 1; the right side is 1⋅2/2=11 \cdot 2 / 2 = 1. They agree.

  2. Inductive hypothesis. Fix some k≥1k \ge 1 and assume 1+2+⋯+k=k(k+1)21 + 2 + \dots + k = \dfrac{k(k+1)}{2}.

  3. Goal. Show 1+2+⋯+k+(k+1)=(k+1)(k+2)21 + 2 + \dots + k + (k+1) = \dfrac{(k+1)(k+2)}{2}.

  4. Use the hypothesis. The first kk terms are exactly the hypothesis, so the left side is k(k+1)2+(k+1)\dfrac{k(k+1)}{2} + (k+1).

  5. Simplify. k(k+1)2+2(k+1)2=(k+1)(k+2)2\dfrac{k(k+1)}{2} + \dfrac{2(k+1)}{2} = \dfrac{(k+1)(k+2)}{2}, which is the goal.

  6. Conclude. The base case holds and each case implies the next, so the formula holds for every n≥1n \ge 1. ∎

Proof 2: the sum of the first n odd numbers

Claim. For every n≥1n \ge 1, 1+3+5+⋯+(2n−1)=n21 + 3 + 5 + \dots + (2n - 1) = n^2.

  1. Base case, n=1n = 1. 1=121 = 1^2.

  2. Inductive hypothesis. Assume 1+3+⋯+(2k−1)=k21 + 3 + \dots + (2k - 1) = k^2 for some k≥1k \ge 1.

  3. Inductive step. The next odd number is 2(k+1)−1=2k+12(k+1) - 1 = 2k + 1. Adding it to both sides gives 1+3+⋯+(2k−1)+(2k+1)=k2+2k+1=(k+1)21 + 3 + \dots + (2k-1) + (2k+1) = k^2 + 2k + 1 = (k+1)^2. ∎

  4. Picture. A k×kk \times k square of dots grows to (k+1)×(k+1)(k+1) \times (k+1) by adding an L-shaped border of k+k+1=2k+1k + k + 1 = 2k + 1 dots. The algebra above is that picture.

Proof 3: a later base case, 2ⁿ > n² for n ≥ 5

Claim. For every n≥5n \ge 5, 2n>n22^n > n^2. (The checker shows it fails for n=2,3,4n = 2, 3, 4, so the base case has to be 5.)

  1. Base case, n=5n = 5. 25=32>25=522^5 = 32 > 25 = 5^2.

  2. Inductive hypothesis. Assume 2k>k22^k > k^2 for some k≥5k \ge 5.

  3. Use it. 2k+1=2⋅2k>2k22^{k+1} = 2 \cdot 2^k > 2k^2.

  4. Compare with the goal. We need 2k2≥(k+1)2=k2+2k+12k^2 \ge (k+1)^2 = k^2 + 2k + 1, that is, k2≥2k+1k^2 \ge 2k + 1. Since k≥5k \ge 5, k2≥5k=2k+3k>2k+1k^2 \ge 5k = 2k + 3k > 2k + 1.

  5. Chain them. 2k+1>2k2≥(k+1)22^{k+1} > 2k^2 \ge (k+1)^2. ∎ The inductive step needed k≥3k \ge 3; the base case needed 5. Both conditions matter.

Proof 4: strong induction, every integer ≥ 2 is a product of primes

Claim. Every integer n≥2n \ge 2 can be written as a product of one or more primes.

  1. Why ordinary induction is awkward. Knowing that 11 is a product of primes says nothing useful about 12. But 12 = 3 × 4, and the factors are smaller numbers we would like to use.

  2. Strong induction. In the inductive step, assume the claim for every integer from 2 up to kk, and prove it for k+1k + 1. This is just as valid: the dominoes behind you have all fallen, not only the last one.

  3. Base case, n=2n = 2. 2 is prime, so it is a product of one prime.

  4. Case 1: k+1k + 1 is prime. Then it is a product of one prime, itself.

  5. Case 2: k+1k + 1 is composite. Then k+1=abk + 1 = ab with 2≤a,b≤k2 \le a, b \le k. By the hypothesis both aa and bb are products of primes; putting the two products together writes k+1k + 1 as one. ∎

Spot the mistake

A broken proof: all horses are the same colour

“Claim.” In every set of n≥1n \ge 1 horses, all the horses have the same colour.

  1. Base case, n=1n = 1. A set with one horse has only one colour in it. True.

  2. Inductive step. Assume any kk horses share a colour. Take k+1k + 1 horses and line them up. The first kk share a colour, and so do the last kk.

  3. The suspicious move. “The two groups overlap, so the colour is the same throughout.”

  4. The flaw. When k+1=2k + 1 = 2, the first group is horse 1 and the last group is horse 2. They don’t overlap at all, so nothing connects their colours. The step from 1 to 2 is false, and every later case depends on it.

  5. The lesson. An inductive step must work for every k≥n0k \ge n_0, including the smallest. Always test the argument on the first step explicitly.

Writing an induction proof

  1. State P(n)P(n) precisely, and the starting value n0n_0.
  2. Prove the base case by direct calculation.
  3. Write the inductive hypothesis out in full, with kk in place of nn.
  4. Write the goal, P(k+1)P(k+1), in full too. Seeing both side by side usually shows how to get from one to the other.
  5. Point to the exact place where you use the hypothesis. If you never use it, you didn’t need induction, or something is wrong.

Induction in computer science

Recursion and induction are the same idea: a recursive function is correct if its base case is correct and each recursive case is correct assuming the smaller calls are. Loop invariants, like the one that proves binary search correct, are induction on the number of iterations. And structural induction proves facts about lists, trees and syntax by doing the base case for the smallest structures (the empty list, a leaf) and the inductive step for each way of building bigger ones.

References

  1. D. J. Velleman, How to Prove It: A Structured Approach, 3rd ed., Cambridge University Press, 2019. Chapter 6. doi:10.1017/9781108539890
  2. E. Lehman, F. T. Leighton and A. R. Meyer, Mathematics for Computer Science, MIT, 2017. Chapter 5.
  3. “Mathematical induction”, Wikipedia.