Mathematical induction, without the leap of faith

Students often distrust induction. It looks like you assume the thing you are trying to prove. You do not. You assume it for one value and earn it for the next. Here is the idea, then a full worked proof.

The idea, in one sentence

If a statement is true for $n = 1$, and being true for some $n = k$ forces it to be true for $n = k+1$, then it topples like dominoes through every positive integer.

The base case tips the first domino. The inductive step guarantees each domino knocks over the next. Together they cover all of them.

The claim

Prove that for all integers $n \ge 1$:

$$1 + 2 + 3 + \cdots + n = \frac{n(n+1)}{2}$$

Step 1: base case

Check $n = 1$. The left side is $1$. The right side is $\dfrac{1 \cdot 2}{2} = 1$. They agree, so the statement holds for $n = 1$.

Step 2: inductive step

Assume it holds for some $n = k$. That is our one free assumption:

$$1 + 2 + \cdots + k = \frac{k(k+1)}{2}$$

Now show it must then hold for $n = k+1$. Add the next term, $k+1$, to both sides:

$$1 + 2 + \cdots + k + (k+1) = \frac{k(k+1)}{2} + (k+1)$$

The reasoning is now pure algebra. Factor out $(k+1)$ on the right:

$$= (k+1)\left(\frac{k}{2} + 1\right) = (k+1)\cdot\frac{k+2}{2} = \frac{(k+1)(k+2)}{2}$$

That is exactly the formula with $k+1$ in place of $n$. So truth at $k$ forces truth at $k+1$.

Step 3: conclude

The statement is true for $n = 1$, and truth at any $k$ forces truth at $k+1$. By induction it holds for all integers $n \ge 1$.

The trace: notice we never assumed the final result. We assumed one case and did honest algebra to reach the next. Write the proof so a reader can see that distinction, and you will not lose marks for "circular reasoning".