Induction: Sum of First $n$ Integers
Young Gauss famously summed $1 + 2 + \cdots + 100$ in seconds. But how do we prove that $1 + 2 + \cdots + n = \dfrac{n(n+1)}{2}$ works for every single positive integer? Mathematical induction gives a watertight argument — base case, assumption, step, conclusion — that leaves no room for doubt. In this lesson you will master the full proof structure for sum formulas.
Without using the formula, calculate $1 + 2 + 3 + 4 + 5 + 6 + 7 + 8 + 9 + 10$. Describe the shortcut or pattern you noticed while adding them up.
The formula $\displaystyle\sum_{r=1}^{n} r = \dfrac{n(n+1)}{2}$ gives the sum of the first $n$ positive integers. Checking it for $n = 10$ is easy — but how do you guarantee it works for $n = 1{,}000{,}000$? Or every $n$ simultaneously?
The key challenge of induction is building a chain of reasoning: if the formula works for some integer $k$, we use that assumption to prove it must also work for $k+1$. Combined with a verified base case, this chain reaches every positive integer.
Base ($n=1$) → Step: $k \Rightarrow k+1$ → True for all $n$
Key facts
- $1 + 2 + \cdots + n = \dfrac{n(n+1)}{2}$ for all positive integers $n$
- $2 + 4 + \cdots + 2n = n(n+1)$ for all positive integers $n$
- The four mandatory steps of an induction proof
Concepts
- Why both a base case and an inductive step are logically required
- How the inductive step adds the next term to the hypothesis
- The role of common-factor algebraic manipulation in inductive steps
Skills
- Write a complete proof by induction for a sum formula with all four parts
- Correctly factorise $(k+1)$ from a combined expression
- Identify and avoid common induction errors in worked solutions
The sum of the first $n$ positive integers is given by:
This result was allegedly discovered by Gauss as a schoolboy. Pairing $1$ with $n$, $2$ with $n-1$, and so on gives $\frac{n}{2}$ pairs each summing to $n+1$ — but this is only a heuristic. Induction turns it into a rigorous proof for every positive integer.
Proof by mathematical induction:
Step 1 — Base case ($n = 1$): LHS $= 1$; RHS $= \dfrac{1 \cdot 2}{2} = 1$. LHS = RHS. True for $n = 1$.
Step 2 — Inductive hypothesis: Assume true for $n = k$: $$1 + 2 + \cdots + k = \frac{k(k+1)}{2}$$
Step 3 — Inductive step ($n = k+1$): We must show $1 + 2 + \cdots + (k+1) = \dfrac{(k+1)(k+2)}{2}$.
LHS $= \underbrace{1 + 2 + \cdots + k}_{\text{use hypothesis}} + (k+1) = \dfrac{k(k+1)}{2} + (k+1) = \dfrac{k(k+1) + 2(k+1)}{2} = \dfrac{(k+1)(k+2)}{2}$ = RHS. ✓
Conclusion: By the principle of mathematical induction, the result is true for all positive integers $n \geq 1$. $\blacksquare$
The sum of the first $n$ positive integers is given by: $1+2+3+\cdots+n = \frac{n(n+1)}{2}$
Pause — copy the formula $1+2+\cdots+n=\frac{n(n+1)}{2}$ and the key inductive step $\frac{k(k+1)}{2}+(k+1)=\frac{(k+1)(k+2)}{2}$ into your book.
Quick check: What is the correct target expression when proving the formula for $n = k+1$?
We just saw that $1+2+\cdots+n=\frac{n(n+1)}{2}$, proved by the inductive step $\frac{k(k+1)}{2}+(k+1)=\frac{(k+1)(k+2)}{2}$. That raises a question: does the same four-step template extend to the sum of even integers $2+4+\cdots+2n$, and what is the key factorisation? This card answers it → adding $2(k+1)$ and factorising gives $k(k+1)+2(k+1)=(k+1)(k+2)=$ RHS.
A related result is the sum of the first $n$ even positive integers:
Notice that this is exactly twice the formula for the sum of the first $n$ integers — which makes sense because each term is doubled. The inductive step uses the same strategy: add the next term $2(k+1)$ to the hypothesis and factorise.
Step 3 — Inductive step:
LHS $= k(k+1) + 2(k+1) = (k+1)(k+2)$ = RHS for $n = k+1$. ✓
A related result is the sum of the first $n$ even positive integers:
Pause — copy the formula $2+4+\cdots+2n=n(n+1)$ and the one-line inductive step $k(k+1)+2(k+1)=(k+1)(k+2)$ into your book.
Did you get this? True or false: when proving $2+4+\cdots+2n = n(n+1)$ by induction, the inductive step adds $2(k+1)$ to both sides of the hypothesis.
Worked examples · 3 in a row, reveal as you go
Prove by mathematical induction that $1 + 2 + 3 + \cdots + n = \dfrac{n(n+1)}{2}$ for all positive integers $n$.
Prove by induction that $2 + 4 + 6 + \cdots + 2n = n(n+1)$ for all positive integers $n$.
Find the sum of the first 50 positive integers, then verify that this matches the formula $\dfrac{n(n+1)}{2}$.
Fill the gap: In the inductive step, $\dfrac{k(k+1)}{2} + (k+1) = \dfrac{(k+1)(k +\,}$$\text{)}{2}$.
Misconceptions to fix · the 3 traps that cost marks
Did you get this? True or false: it is valid to begin the inductive step by assuming the formula holds for $n = k+1$ and working backward.
Activities · practice with the ideas
Calculate $\displaystyle\sum_{r=1}^{20} r$ using the formula $\dfrac{n(n+1)}{2}$.
Write out the base case for proving $2+4+\cdots+2n = n(n+1)$ by induction ($n = 1$). Show LHS and RHS separately.
In the inductive step for $1+2+\cdots+n = \dfrac{n(n+1)}{2}$, simplify $\dfrac{k(k+1)}{2} + (k+1)$ fully.
Find the sum $2 + 4 + 6 + \cdots + 40$ (i.e. the sum of even integers up to 40).
What is wrong with the following "proof" step: "Assume $S_{k+1} = \dfrac{(k+1)(k+2)}{2}$; then working backward, $S_k = \dfrac{k(k+1)}{2}$."
Odd one out: Three of these statements about induction proofs are correct. Which one is NOT?
Earlier you calculated $1+2+\cdots+10$ and noted a shortcut. The formula gives $\dfrac{10 \times 11}{2} = \mathbf{55}$.
The pairing trick (add $1+10, 2+9, \ldots$ to get 5 pairs of 11) is essentially Gauss's geometric insight. Induction turns that insight into a logically airtight proof that works for every $n$ — not just $n = 10$. Did your shortcut match the pairing idea?
Pick your answer, then rate your confidence — that tells the system what to drill next. Each retry pulls a fresh mix from the bank.
Q1. Find the sum of the first 30 positive integers. (1 mark)
Q2. Prove by mathematical induction that $2 + 4 + 6 + \cdots + 2n = n(n+1)$ for all positive integers $n$. (3 marks)
Q3. A student writes the inductive step as: "Since we want to show $S_{k+1} = \dfrac{(k+1)(k+2)}{2}$, we rearrange to get $S_k = \dfrac{k(k+1)}{2}$, which is our hypothesis." Identify the error and explain why the argument is invalid. (2 marks)
Comprehensive answers (click to reveal)
Activity answers:
1. $S_{20} = \dfrac{20 \times 21}{2} = 210$.
2. LHS $= 2$; RHS $= 1(1+1) = 2$. LHS = RHS. True for $n = 1$.
3. $\dfrac{k(k+1)}{2} + (k+1) = \dfrac{k(k+1)+2(k+1)}{2} = \dfrac{(k+1)(k+2)}{2}$.
4. $n = 20$ even integers up to 40: $S = 20 \times 21 = 420$.
5. The error is circular reasoning: the argument assumes the conclusion (the $k+1$ formula) and derives the hypothesis from it. A valid inductive step must start from known results (the hypothesis for $n=k$) and reach the $k+1$ case.
Q1 (1 mark): $S_{30} = \dfrac{30 \times 31}{2} = \mathbf{465}$ [1].
Q2 (3 marks): Base case ($n=1$): LHS $= 2$; RHS $= 1 \times 2 = 2$. True [1]. Hypothesis: assume $2+4+\cdots+2k = k(k+1)$. Inductive step: $k(k+1)+2(k+1) = (k+1)(k+2)$ = RHS for $n = k+1$ [1]. By induction, true for all $n \geq 1$ [1].
Q3 (2 marks): The error is circular/backward reasoning — the student assumes the conclusion [1]. The valid method is to start from the LHS using only the hypothesis and algebraically reach the required RHS, not to assume the result and work backward [1].
Five timed questions on sum induction. Beat the boss to bank a tier — gold (90% + speed), silver (75%), or bronze (50%). Replays welcome.
⚔ Enter the arenaClimb platforms by answering sum induction questions. Lighter alternative to the boss.
Mark lesson as complete
Tick when you've finished the practice and review.