SME
Discrete Mathematics
Recurrences
Use this for “Solve aₙ = 5aₙ₋₁ − 6aₙ₋₂ with a₀ = 1, a₁ = 4.”
Chart
Terms from a₀: 1, 4, 14, 46, 146, 454 (each term c₁ × the one before + c₂ × the one before that).
a₅ = 5 × 146 + (−6) × 46 = 454.
Closed form (rings): a₅ = −1 × 2⁵ + 2 × 3⁵ = −32 + 486 = 454, on every term.
This is an example. Type your own values to start a new problem.
aₙ
=
c₁
aₙ₋₁
+
(
c₂
)
aₙ₋₂
a₀
=
a₀
,
a₁
=
a₁
a
=
aₙ
aₙ comes from the closed form in the Formulas: the roots r₁ and r₂ of r² = c₁r + c₂, then A and B fitted to a₀ and a₁.
r₁
Smaller root
worked out (not typed)
r₂
Larger root
worked out (not typed)
A
Constant A
worked out (not typed)
B
Constant B
worked out (not typed)
Formulas
r₁
=
c₁
−
√
c₁
2
+ 4 ×
c₂
2
2
=
(5
−
√(
5
2
+
4
×
(−6)))
÷
2
r₂
=
c₁
+
√
c₁
2
+ 4 ×
c₂
2
3
=
(5
+
√(
5
2
+
4
×
(−6)))
÷
2
A
=
r₂
×
a₀
−
a₁
r₂
−
r₁
−1
=
3 × 1 − 4
3 − 2
B
=
a₁
−
r₁
×
a₀
r₂
−
r₁
2
=
4 − 2 × 1
3 − 2
aₙ
=
A
×
r₁
n
+
B
×
r₂
n
454
=
−1
×
2
5
+
2
×
3
5
Assumptions
•
Each term is c₁ times the term before plus c₂ times the one before that, from a₀ and a₁.
•
Trying aₙ = rⁿ gives the characteristic equation r² = c₁r + c₂; its two roots are r₁ < r₂.
•
With two different real roots, every solution is aₙ = Ar₁ⁿ + Br₂ⁿ; a₀ and a₁ fix A and B.
•
The page needs c₁² + 4c₂ > 0; a repeated root has its own page.
Step-by-step
WE KNOW
c₁ = 5, c₂ = −6, a₀ = 1, a₁ = 4, n = 5
FIND
smaller root (r₁), larger root (r₂), constant A (A), constant B (B), term n (aₙ)
Step 1 · Find smaller root (r₁)
Use r₁ = (c₁ − √(c₁² + 4 × c₂)) ÷ 2
Write
r
2
=
c₁r
+
c₂
as
r
2
−
c₁r
−
c₂
=
0
and
take
the
quadratic
formula
with
the
minus
sign.
r₁
=
c₁
−
√
c₁
2
+ 4 ×
c₂
2
r₁
=
(5
−
√(
5
2
+
4
×
(−6)))
÷
2
r₁
=
(5
−
√(25
+
4
×
(−6)))
÷
2
r₁
=
(5
−
√(25
+
(−24)))
÷
2
r₁
=
5 −
√
1
2
r₁
=
5 − 1
2
r₁
=
4
2
r₁
=
2
Step 2 · Find larger root (r₂)
Use r₂ = (c₁ + √(c₁² + 4 × c₂)) ÷ 2
The plus sign gives the larger root.
r₂
=
c₁
+
√
c₁
2
+ 4 ×
c₂
2
r₂
=
(5
+
√(
5
2
+
4
×
(−6)))
÷
2
r₂
=
(5
+
√(25
+
4
×
(−6)))
÷
2
r₂
=
(5
+
√(25
+
(−24)))
÷
2
r₂
=
5 +
√
1
2
r₂
=
5 + 1
2
r₂
=
6
2
r₂
=
3
Step 3 · Find constant A (A)
Use A = (r₂ × a₀ − a₁) ÷ (r₂ − r₁)
Put
n
=
0
and
n
=
1
in
the
solution:
A
+
B
=
a₀
and
Ar₁
+
Br₂
=
a₁
.
Take
r₂
times
the
first,
minus
the
second.
A
=
3 × 1 − 4
3 − 2
A
=
−1
Step 4 · Find constant B (B)
Use B = (a₁ − r₁ × a₀) ÷ (r₂ − r₁)
Take
the
second
equation
minus
r₁
times
the
first:
B
(
r₂
−
r₁
)
=
a₁
−
r₁
a₀
.
B
=
4 − 2 × 1
3 − 2
B
=
2
Step 5 · Find term n (aₙ)
Use aₙ = A × r₁ⁿ + B × r₂ⁿ
Put
n
into
the
closed
form:
no
need
to
work
out
every
term
before
it.
aₙ
=
−1
×
2
5
+
2
×
3
5
aₙ = −1 × 32 + 2 × 243
aₙ = −32 + 486
aₙ = 454
Check
Put the numbers back in. Both sides should match.
2
=
(5
−
√(
5
2
+
4
×
(−6)))
÷
2
✓
3
=
(5
+
√(
5
2
+
4
×
(−6)))
÷
2
✓
−1
=
3 × 1 − 4
3 − 2
✓
2
=
4 − 2 × 1
3 − 2
✓
454
=
−1
×
2
5
+
2
×
3
5
✓
Topic check
See what you know: 5 questions on this topic
New questions each time. Pass to mark it complete.