SME
Discrete Mathematics · Problem type
First-order recurrences
Use this for “Tower of Hanoi: a₁ = 1 and aₙ = 2aₙ₋₁ + 1. How many moves for 10 disks?”
Chart
Terms: 1, 3, 7, 15, …, 1,023 (each term 2 × the one before + 1).
aₙ = 2 × 511 + 1 = 1,023
This is an example. Type your own values to start a new problem.
aₙ
=
r
aₙ₋₁
+
d
a₁
=
a₁
a
=
aₙ
aₙ comes from the closed form in the Formulas: the fixed point p = d ÷ (1 − r), then aₙ = A × rⁿ⁻¹ + p with A = a₁ − p.
p
Fixed point
worked out (not typed)
A
Constant A
worked out (not typed)
Formulas
p
=
d
1 −
r
−1
=
1
1 − 2
A
=
a₁
−
p
2 = 1 − (−1)
aₙ
=
A
×
r
n
− 1
+
p
1,023
=
2
×
2
10 − 1
+
(−1)
Assumptions
•
Each term is r times the one before plus d, starting from the first term a₁.
•
The fixed point p = rp + d is the value the rule leaves unchanged, so p = d ÷ (1 − r) needs r ≠ 1.
•
Each step multiplies the distance from p by r, so aₙ = Arⁿ⁻¹ + p with A = a₁ − p.
•
Tower of Hanoi: move n − 1 disks aside, the largest disk across, then n − 1 disks back on top.
Step-by-step
WE KNOW
r = 2, d = 1, a₁ = 1, n = 10
FIND
fixed point (p), constant A (A), term n (aₙ)
Step 1 · Find fixed point (p)
Use p = d ÷ (1 − r)
Solve
p
=
rp
+
d
:
take
rp
from
both
sides,
then
divide
by
1
−
r
.
p
=
1
1 − 2
p
=
1
−1
p
=
−1
Step 2 · Find constant A (A)
Use A = a₁ − p
Put
n
=
1
in
aₙ
=
Arⁿ⁻¹
+
p
:
r
0
=
1,
so
a₁
=
A
+
p
.
A
=
1
−
(−1)
A
=
2
Step 3 · Find term n (aₙ)
Use aₙ = A × rⁿ⁻¹ + p
From
a₁
to
aₙ
the
distance
from
p
is
multiplied
by
r
,
n
−
1
times.
aₙ
=
2
×
2
10 − 1
+
(−1)
aₙ
=
2
×
2
9
+
(−1)
aₙ = 2 × 512 + (−1)
aₙ = 1,024 + (−1)
aₙ = 1,023
Check
Put the numbers back in. Both sides should match.
−1
=
1
1 − 2
✓
2 = 1 − (−1) ✓
1,023
=
2
×
2
10 − 1
+
(−1)
✓
Topic check
See what you know: 5 questions on this topic
New questions each time. Pass to mark it complete.