# Proof by Induction

Establishing a statement for all natural numbers by proving a base case and showing each case implies the next.

**Leads to:** Catalan Numbers, Integer Partitions, Loop Invariants, Modular Arithmetic

**Rests on nothing.** A place to start.

*Mathematical Foundations · Discrete Mathematics*


## Why learn this

Proof by induction is the tool that lets you reason about all natural numbers at once — 0, 1, 2, 3, and so on, without ever reaching the end. It unlocks the deepest ideas in computer science: you will use it to prove that algorithms actually work (correctness proofs for sorting, searching, and graph traversal), to understand recursion (where a function calls itself, and induction is the proof that it stops), and to reason about data structures like trees and heaps. When you later study loop invariants — the property that stays true every time a loop runs — induction is the underlying logic. Without induction, you can test a program on ten inputs and hope; with induction, you know it works for every input. This page teaches you the method, and the neighbouring topics in your library — Catalan Numbers, Integer Partitions, Modular Arithmetic — all rely on it.


## The intuition

Imagine you want to prove that a statement is true for every natural number: 0, 1, 2, 3, ... and so on forever. You can't check them all one by one, because there are infinitely many. Induction gives you a two-step trick. First, you check the smallest case (the base case). Second, you show that if the statement is true for some number, then it must be true for the next number. Once you have those two things, you can start at the base case and walk up: true for 0 forces true for 1, which forces true for 2, which forces true for 3, and so on — like a chain of falling dominoes. If you've set up the chain correctly, every domino falls, even though you never touched them all. The magic is that you don't need to write out the infinite chain; the 'if-then' step covers every link at once. The real work is in that second step — the inductive step — where you assume the statement is true for one number (the assumption is called the 'inductive hypothesis') and then prove it for the next number. It's like proving a recipe works for any portion size by showing that if it works for one portion, it works for two, and so on.


## An analogy

Think of a staircase that goes up forever. You want to prove that you can reach any step. You can't climb them all right now. Instead, you do two things: first, you step onto the first stair (the base case, say step 0). Second, you prove that if you are standing on any stair, you can always take one more step to reach the next stair (the inductive step). Once you've done that, you can be certain that you can reach stair 100, stair 1000, stair 10,000 — because you can start at 0, step to 1, step to 2, and so on. The 'if I'm on one stair, I can reach the next' is a general rule that covers all stairs at once. But here's where the analogy stops: in real life, you might get tired or the stairs might crumble, so the rule 'if I'm on a stair, I can step to the next' might break for some stair. In induction, that rule has to be proven for every single stair without exception — you can't just say 'it works for the ones I've tried'. Also, the staircase analogy suggests a physical process of climbing, but induction is a logical proof, not a physical act. You don't actually move; you just show that the chain of reasoning is sound. Another place the analogy breaks: in induction, the base case might not be 0; sometimes it's 1 or 2, and you have to be careful to start at the right place.


## Definition

Proof by induction is a method of proving a statement is true for every natural number by establishing a base case (the statement holds for the smallest number, often 0 or 1) and then showing that if the statement is true for any number n, it must also be true for n+1.


## How it connects

This sits at the heart of Discrete Mathematics, which your library records as the mathematics of countable structures — logic, sets, relations, functions, combinatorics, and proof technique. Induction is the proof technique. It connects directly to recursion, which you will meet in algorithms: induction is the proof version, recursion is the computation version. The book in your library, 'Foundations of Algorithmic Thinking', says 'Induction and recursion are the same idea in two domains — one proves, the other computes.' That is the key bridge. Neighbouring topics: Catalan Numbers are defined by a recurrence that is proved by induction; Integer Partitions use induction to establish counting formulas; Modular Arithmetic uses induction to prove properties of powers and congruences. Also, loop invariants, which you'll study later, are proven using induction over the number of loop iterations. So this concept is the glue.


## The mathematics

The branch of mathematics this draws on is discrete mathematics, specifically the logic of proof. Discrete mathematics deals with countable structures — things you can list one after another, like the natural numbers. Induction is the standard way to prove statements about all of them.

Before we get to induction itself, you need to know what a 'statement' is in mathematics: a sentence that is either true or false, like 'the number 5 is odd'. Now, induction works on a family of statements, one for each natural number. For example, the statement for n=0 might be '0+0=0', for n=1 '1+1=2', and so on.

The method has two parts. First, the base case: check the first statement in the family is true. Second, the inductive step: show that if the statement for any number n is true, then the statement for n+1 must also be true. This is the 'domino effect'. The key word is 'if': you don't prove the statement for n outright; you prove that the truth of the n-th statement forces the truth of the (n+1)-th.

Once you have both, you can chain them together. Starting at the base case, the truth for 0 forces truth for 1, which forces truth for 2, and so on infinitely. No single step required you to check beyond one link, but the chain covers all numbers. The inductive step is where the real thinking happens — you have to find a logical connection between n and n+1. Often this is done by writing the (n+1)-th statement in a way that contains the n-th statement inside it.

To prove a statement P(n) for all natural numbers n:

1. Base case: Prove P(0) (or P(1), depending on the domain).
2. Inductive step: Assume P(n) for an arbitrary (but fixed) n. This is the inductive hypothesis. Then prove P(n+1).

Conclude that P(n) holds for every n.

Symbolically: P(0) AND (for all n, if P(n) is true then P(n+1) is true) IMPLIES for all n, P(n) is true.


## A worked example

We'll prove that for every natural number n (0, 1, 2, ...), the sum of the first n natural numbers equals n times (n plus 1) divided by 2. For example, for n=4, the sum 0+1+2+3+4 = 10, and the formula gives 4*5/2 = 10. We'll prove this by induction.

Step 1: Base case: n=0. Sum of first 0 numbers is 0. Formula gives 0*1/2 = 0.   # Check the smallest case directly.
Step 2: Inductive hypothesis: Assume the statement is true for some n, i.e., 0+1+...+n = n(n+1)/2.   # This is the 'if' part of the inductive step. We assume it for one n, not all at once.
Step 3: Inductive step: Consider the sum up to n+1: 0+1+...+n+(n+1). Using the hypothesis, this equals n(n+1)/2 + (n+1).   # We rewrite the (n+1)-th sum in terms of the n-th sum, which we already assumed true.
Step 4: Simplify: n(n+1)/2 + (n+1) = (n+1)(n/2 + 1) = (n+1)(n+2)/2.   # Common denominator: n/2 + 1 = (n+2)/2. So the result is (n+1)(n+2)/2, which is exactly the formula for n+1.
Step 5: Conclusion: The statement for n+1 is true. By induction, it's true for all n.   # Since we've shown the base case and the if-then step, the chain is complete.

Result: We proved that 0+1+...+n = n(n+1)/2 for every natural number n. The proof didn't use any single large example; it used the base case and the general if-then step.


## From scratch, in Python

```python
def hypothesis(n):
    return sum(range(n+1)) == n*(n+1)//2

def base_case():
    return hypothesis(0)

def inductive_step(statement_fn):
    # Check that if P(n) is true, then P(n+1) is true, for n = 0 to 5
    for n in range(5):
        if statement_fn(n) and not statement_fn(n+1):
            return False
    return True

print("Base case holds:", base_case())
print("Inductive step holds for first few n:", inductive_step(hypothesis))
```


## What the code does

First, we define a function `hypothesis(n)` that returns True or False for whether the statement holds for n. The `sum` function adds up all numbers in a list. `range(n+1)` gives us the list [0, 1, 2, ..., n]. So `sum(range(n+1))` adds those numbers. The right side `n*(n+1)//2` computes n times (n+1) divided by 2, using `//` for integer division. The `==` checks if both sides are equal, returning True or False. Next, `base_case` calls hypothesis(0) and returns whether the base case is true. Then `inductive_step` takes a function as input — this is a Python function that takes another function as an argument. It loops over n from 0 to 4. For each n, it checks: if the statement is true for n, but not true for n+1, then the inductive step is broken. If it finds a break, it returns False. Otherwise, after the loop, it returns True. Finally, we print both results. This is a simplified check; a true proof is a mathematical argument, but this code illustrates the pattern: base case and the if-then chain for a few steps.


## Common misconceptions

**I can prove by checking many examples** — If I check the formula for n=0, 1, 2, 3, 4, and it works, that's a proof.

Examples only cover finitely many cases. The statement claims to hold for all infinitely many natural numbers. One counterexample for a larger n would invalidate it. In fact: Induction is the way to cover all cases: prove the base case and the if-then step, and you have covered every n without checking each one.

**The inductive step assumes what I'm trying to prove** — In the inductive step, I assume P(n) is true, but that's what I'm trying to prove — that seems circular.

You are not assuming P(n) is true for all n. You are temporarily assuming it for one arbitrary n, and showing that if that assumption holds, P(n+1) holds. That's a conditional statement, not a circular proof. In fact: The inductive hypothesis is a 'what if' for a single case. The proof then shows that truth propagates from n to n+1.

**The base case is always n=0** — Every induction has to start at 0.

The base case depends on the statement. Some statements start at 1, some at 2, etc. If the statement is false for 0 but true for 1, you must start at 1. In fact: Choose the smallest natural number for which the statement makes sense and is true. For example, when proving 'n^2 ≥ n', the base case is n=1, not n=0 (since 0^2 ≥ 0 also holds, but 1 is the first nontrivial).


## In short

Proof by induction: prove the base case, then prove the if-then step (inductive hypothesis → next case). That proves the statement for all natural numbers. It's the proof twin of recursion, and it's the logic behind loop invariants and the correctness of algorithms.


## Where this is used

Proof by induction is not a tool you call from a library; it's a method of reasoning that underlies the correctness of algorithms and data structures. When a developer writes a loop, they often rely on an inductive invariant — a property that holds before and after each iteration. For example, in binary search, the invariant is 'if the target is in the array, it lies between the current low and high indices'. That invariant is proven by induction over the number of iterations. In a large language model, the transformer architecture processes input tokens in layers; the correctness of the forward pass propagation is often reasoned about inductively — for each layer, the output depends correctly on the previous layer's outputs, and by induction, the final output is correct. In small models running on devices, such as TinyML keyword spotters, the networks are often quantised to reduce size; proving that quantisation doesn't cause the output to drift too far relies on inductive bounds across layers. In retrieval-augmented generation, the system retrieves documents, concatenates them with the query, and the generation model produces an answer; the correctness of the retrieval ranking is often justified by ranking principles that are proven by induction on the candidate set. In agentic systems that plan and call tools, the agent executes a sequence of actions; proving that the plan achieves the goal requires inductive reasoning about the state before and after each action. In everyday applied machine learning, such as training a model with gradient descent, the convergence proof (that the loss decreases over epochs and reaches a minimum) is often argued by induction over epochs, showing that if the loss is at a certain value at epoch t, it will be lower at epoch t+1. A developer might not write an induction proof every day, but when they debug a tricky issue in a loop or a recursive function, they mentally run the induction: 'Does the base case hold? If I'm here, does the next step hold?' So induction is the hidden reasoning behind nearly every non-trivial piece of software. If done badly, as when an algorithm is not proven correct, subtle bugs appear only on large inputs — exactly the cases that induction would have covered. For example, a sorting algorithm that works on small arrays but fails on large ones because the inductive step wasn't established. Thus, induction is the developer's invisible safety net.


---

Read this on the web: https://basavapurushottam.com/learn-ai/proof-by-induction
