Maths/Big O notation

Proof by induction

After thiswhat you will be able to doProve the formula for 1 + 2 + ... + n with a base case and inductive step, and say why checking examples alone cannot prove it.

Questionwhat this lesson answersThe pairing picture showed that one plus two up to n equals n times n plus one over two, but only for the sizes small enough to draw. A picture of four rows is not a proof for every n. How do you close the gap between "true for the cases I checked" and "true for every n" without checking infinitely many?

Not coveredwhat this lesson leaves outWe prove one closed form by induction and say what the method needs to stand on. We do not develop the logical foundation that guarantees the method works, nor prove any harder statement.

The pairing picture in Summing a loop makes the triangular total easy to see. Put a row of one dot, then two, then three, beside a reversed copy and every pair makes the same width. For four rows, the picture really does show the answer for four rows. It does not show an unseen fifth row, or a millionth row, or every row that can ever be named. A grid can make a pattern convincing without making it universal.

Trying more sizes cannot close that gap. Checking one, two, three, and four settles four separate claims. Checking through one thousand settles one thousand separate claims. There are still more whole numbers after the last one checked. The problem has a precise shape: a claim about every whole number cannot be settled by trying whole numbers one at a time.

Instead, build a chain with two parts. First, inspect the claim at the smallest size directly. Second, establish a link: whenever the claim holds at one size, it also holds at the next size. With both parts, the first size is true. The link makes the second true, then the third, then the fourth, and so on, with no unproved gap. This two-part method is called proof by induction. The first direct check is called the base case. The link that carries a true claim from one size to the next is called the inductive step.

A line of dominoes is useful intuition. Knock down the first one, and arrange each falling domino to knock down the next. The whole line falls. But the image is not the proof. A real proof has to check the first claim and show the exact algebra that turns one true claim into the next. The dominoes only help explain why those two jobs are the right jobs.

Here is the claim the pairing picture deferred:

The letter $n$ labels any whole number starting at one. To prove the first part, substitute the smallest allowed value. The left side contains only one addend, and the right side becomes the same number:

That is the base case. It matters that this is an actual calculation, not a picture of a likely pattern. The chain now has somewhere to begin.

For the link, take an arbitrary current whole number and call it $k$. We temporarily accept that the formula is already true at that one size. A statement temporarily accepted so that its consequence can be checked is called the assumption. The assumption is not the conclusion. It is the conditional starting point for the next-size argument:

Now add the next term, $k + 1$, to both sides. The left side has become the sum through the next whole number. On the right, factor out the shared $k + 1$ and simplify:

The last line is exactly the original right side with $k + 1$ in place of $k$. It says the formula holds at the next size whenever it held at the current one. The algebra has not assumed that the formula was true everywhere. It used the single assumed equality at $k$, then showed what must follow from it.

The two parts now meet. The base case establishes the claim at one. The inductive step carries it from any whole number to the next. Because every whole number from one onward is reached by repeatedly adding one, the claim reaches them all:

The method needs that ground under it. Starting at one and repeatedly adding one must reach every whole number in the intended range, without skipping one and without leaving an earlier number outside the start. That fact is what makes the domino image a chain rather than a collection of unrelated tiles. Its formal foundation is beyond this lesson’s stated stopping point.

This is why induction belongs in the Big O arc. A growth bound is not a report about a few large inputs. It claims that every input past a threshold obeys a ceiling. The What O(f) actually is door names that threshold and the fixed multiplier that must work after it. Induction is one way to establish an every-input claim once a suitable starting point and next-size link are known.

The pairing picture and this proof do different work without competing. The picture shows why the product divided by two is the right shape: paired rows make equal widths. The proof shows that the shape remains right at every whole-number size, including sizes no drawing can contain.