> Source URL: /demos/discrete-demo/induction-sum.proof
---
title: Sum of the First n Natural Numbers
technique: mathematical induction
---

<style>body { font-family: sans-serif; }</style>

# Theorem

For every natural number $n \geq 1$,

$$
\sum_{i=1}^{n} i = \frac{n(n+1)}{2}.
$$

This worked proof is a reference for the structure we expect on proof-based problem submissions: a clearly labeled **base case**, **inductive hypothesis**, and **inductive step**, with each algebraic move either self-evident or annotated.

---

## Proof (by induction on $n$)

Let $P(n)$ denote the statement

$$
P(n): \quad \sum_{i=1}^{n} i = \frac{n(n+1)}{2}.
$$

We prove $P(n)$ holds for all $n \in \mathbb{N}$ with $n \geq 1$.

### Base case: $n = 1$

$$
\sum_{i=1}^{1} i = 1
\qquad \text{and} \qquad
\frac{1 \cdot (1 + 1)}{2} = \frac{2}{2} = 1.
$$

Both sides equal $1$, so $P(1)$ holds.

### Inductive hypothesis

Fix an arbitrary $k \in \mathbb{N}$ with $k \geq 1$ and assume $P(k)$ holds -- that is,

$$
\sum_{i=1}^{k} i = \frac{k(k+1)}{2}. \tag{IH}
$$

### Inductive step: show $P(k) \Rightarrow P(k+1)$

We must show

$$
\sum_{i=1}^{k+1} i = \frac{(k+1)\bigl((k+1)+1\bigr)}{2} = \frac{(k+1)(k+2)}{2}.
$$

Starting from the left-hand side and peeling off the last term:

$$
\begin{aligned}
\sum_{i=1}^{k+1} i
  &= \left( \sum_{i=1}^{k} i \right) + (k+1)
    && \text{(split last term)} \\
  &= \frac{k(k+1)}{2} + (k+1)
    && \text{(by IH)} \\
  &= \frac{k(k+1) + 2(k+1)}{2}
    && \text{(common denominator)} \\
  &= \frac{(k+1)(k+2)}{2}
    && \text{(factor $(k+1)$)}.
\end{aligned}
$$

This is exactly the right-hand side of $P(k+1)$, so $P(k+1)$ holds.

### Conclusion

We have shown $P(1)$ directly and $P(k) \Rightarrow P(k+1)$ for every $k \geq 1$. By the principle of mathematical induction, $P(n)$ holds for every $n \in \mathbb{N}$ with $n \geq 1$.

$$\blacksquare$$

---

## Commentary

A complete proof by induction has four named pieces:

1. **Statement of $P(n)$.** Name the predicate you are proving so later references are unambiguous.
2. **Base case.** Verify the smallest index explicitly -- do not hand-wave.
3. **Inductive hypothesis.** State the assumption $P(k)$ in full. Label it (e.g. `(IH)`) so the inductive step can cite it.
4. **Inductive step.** Derive $P(k+1)$ from $P(k)$ with each step justified. Every equality should be either arithmetic or a cited identity / hypothesis.

A submission missing any of these pieces -- especially an unstated inductive hypothesis, or a base case that was assumed rather than verified -- is not a complete proof, even if the algebra in the middle is correct.


---

## Backlinks

The following sources link to this document:

- [Induction Proof](/demos/discrete-demo/index.demo.llm.md)