Maths WorkshopMaths problems with full solutions
Exercise 1034Logic, sets and proofs › Proof techniques › InductionL1Added 3 Nov 2026

Divisibility by induction

#induction#divisibility#powers

Statement

Prove by induction that 3n−13^n-1 is divisible by 22 for all n≥1n\ge1.

Hint

Write 3n+1−1=3(3n−1)+23^{n+1}-1=3(3^n-1)+2.

Show solutionHide solution

Solution

Base case. n=1n=1: 3−1=23-1=2 is even. ✓

Inductive step. Assume 3n−13^n-1 is even. Then
3n+1−1=3⋅3n−1=3(3n−1)+2.3^{n+1}-1=3\cdot3^n-1=3(3^n-1)+2.
Both terms are even (the first by induction, 22 trivially), so the sum is even.

Conclusion. 3n−13^n-1 is divisible by 22 for all n≥1n\ge1.