P(n): Σr = n(n + 1)/2, base n = 1
LHS = 1, RHS = 1
1.
Proof by induction shows a statement holds for every positive integer by proving two things: the base case is true, and whenever is true then is also true.
This page is easier if you are comfortable with:
Think of dominoes. The base case knocks over the first one, and the inductive step guarantees that each falling domino knocks over the next. Together they show that every domino falls. You must always prove both parts: a true base case with a broken step proves nothing, and vice versa.
In the inductive step you assume (the inductive hypothesis) and use it to prove . For sums, add the next term, as in the sum of r(r+1) and the sum of 1 over r(r+1). For matrices, multiply by one more copy, as in the powers of a shear matrix. A sum with factorials is handled in the sum of r times r factorial.
Divisibility results are proved by writing the expression in terms of the expression, as in divisibility by induction. Compare this with proof by contradiction, which suits negative statements. Finite sums are also covered in standard sigma results.
Induction proves a statement for every positive integer by proving it for the first one and then showing that each case leads to the next.
Each bar is the previous bar plus the next integer, which is exactly the inductive step.
These examples are worked by hand, step by step, so you can compare your own working.
Prove .
Prove for all positive integers .
Prove that is divisible by 7.
A few situations come up again and again. Knowing them saves time and helps you spot answers that cannot be right.
LHS = 1, RHS = 1
1.
10 + 5
15.
5·6/2
15.
k(k+1)/2 + (k+1) = (k+1)(k+2)/2
k = 4: 15.
Induction: show P(1) (base case); then assume P(k) and prove P(k + 1). Conclude P(n) for all n ≥ 1.
n = 1: n(n + 1)/2.
Assume P(4): 10. Add the next term 5.
P(5) right side.
k(k+1)/2 + (k+1) at k = 4.
only the step ✗
both parts ✓
Needed.
circular ✗
assume P(k) ✓
Hypothesis.
stop ✗
state “true for all n ≥ 1” ✓
Final line.
P(k) ✗
P(k + 1) ✓
Prove the next case.
Try each one on paper, then open the answer. Use the solver above to see the full working.
1
6
21
21
55
10
Unlimited fresh questions with instant marking. Choose a level, work it out on paper, then type your answer.
Solve: …
Base case, inductive step, conclusion.
P(k) is true for some k.
P(k + 1).
Yes.
induction: Σr(r+1).
proof by contradiction.
More in Further pure maths and the formula sheets.