SME
Grade 12 Math · Problem type
A divisibility proof
Use this for “Prove that n³ − n is divisible by 3 for every whole number n ≥ 1.”
Table
Whole number n (n)
f(n) divided by 3 (q)
This is an example. Type your own values to start a new problem.
n
3
−
n
=
f(n)
f(n)
=
3
×
q
f(n + 1)
The next value, f(n + 1)
worked out (not typed)
D
The jump f(n + 1) − f(n)
worked out (not typed)
Formulas
f
(
n
)
=
n
3
−
n
60
=
4
3
−
4
q
=
f
(
n
)
3
20
=
60
3
f
(
n
+
1)
=
(
n
+ 1)
3
−
(
n
+
1)
120
=
(4 + 1)
3
−
(4
+
1)
D
=
f
(
n
+
1)
−
f
(
n
)
60 = 120 − 60
Assumptions
•
Base case: at n = 1, 1³ − 1 = 0, and 0 = 3 × 0 is divisible by 3.
•
Step: f(k + 1) = f(k) + 3k(k + 1), so if 3 divides f(k) it divides f(k + 1).
•
The numbers check the step at one n; the algebra with k proves every case.
Step-by-step
WE KNOW
n = 4
FIND
n³ − n (f(n)), f(n) divided by 3 (q), the next value, f(n + 1) (f(n + 1)), the jump f(n + 1) − f(n) (D)
Step 1 · Find n³ − n (f(n))
Use f(n) = n³ − n
Put
n
into
the
expression.
f
(
n
)
=
4
3
−
4
f
(
n
)
=
64
−
4
f
(
n
)
=
60
Step 2 · Find f(n) divided by 3 (q)
Use q = f(n) ÷ 3
A
whole
number:
3
divides
f
(
n
)
at
this
n
.
q
=
60
3
q
=
20
Step 3 · Find the next value, f(n + 1): f(n + 1)
Use f(n + 1) = (n + 1)³ − (n + 1)
The expression at the next whole number.
f
(
n
+
1)
=
(4 + 1)
3
−
(4
+
1)
f
(
n
+
1)
=
5
3
−
5
f
(
n
+
1)
=
125
−
5
f
(
n
+
1)
=
120
Step 4 · Find the jump f(n + 1) − f(n): D
Use D = f(n + 1) − f(n)
The
step:
how
much
the
expression
grows
from
n
to
n
+
1.
D
=
120
−
60
With
k
for
n
:
(k + 1)
3
−
(k
+
1)
−
(
k
3
−
k)
=
3k²
+
3k
=
3k(k
+
1)
3
n
(
n
+
1)
=
3
×
4
×
5
=
60
D
=
60
→
f
(
n
+
1)
=
f
(
n
)
+
3
n
(
n
+
1):
a
multiple
of
3
plus
a
multiple
of
3
is
a
multiple
of
3
Check
Put the numbers back in. Both sides should match.
60
=
4
3
−
4
✓
20
=
60
3
✓
120
=
(4 + 1)
3
−
(4
+
1)
✓
60 = 120 − 60 ✓
Topic check
See what you know: 5 questions on this topic
New questions each time. Pass to mark it complete.
Refresh
Related lessons
Mathematical induction
Main lesson
The sum of odd numbers
Use this for “Prove 1 + 3 + 5 + … + (2n − 1) = n² by induction.”
A geometric sum
Use this for “Prove 1 + 2 + 4 + … + 2ⁿ⁻¹ = 2ⁿ − 1 by induction” (r = 2), or any ratio r.
The sum of squares
Use this for “Prove 1² + 2² + … + n² = n(n + 1)(2n + 1)/6 by induction.”
The steps of a proof by induction
Use this for “Prove by induction that 1 + 3 + 5 + … + (2n − 1) = n² for every n ≥ 1.”