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 confidencethat 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.