6 | Recurrence equations

Question 1

What techniques are there to solve recurrence equations?

Answer 1

• Technique of the characteristic equation
• Technique of change of variable
• (In)Homogeneous recurrences

Question 2

Technique of the characteristic equation: for what type of equation?

Answer 2

• Linear: the unknowns do not form monomials of degree higher
  than 1
• Homogenous: the sum equals 0
• With constant coefficients: 𝑎_𝑖, 0 ≤ 𝑖 ≤ 𝑘 are constants

Question 3

Technique of the characteristic equation:

𝑎₀𝑡_𝑛 + 𝑎₁𝑡_𝑛−1 + ⋯ + 𝑎_𝑘𝑡_𝑛−𝑘 = 0

First step?

Answer 3

Find characteristic polynomial of the recurrence (replace t_n = xⁿ and divide by x^n-k):

𝑝(𝑥) = 𝑎₀𝑥^𝑘 + 𝑎₁𝑥^𝑘−1 + ⋯ + 𝑎_𝑘

Question 4

Technique of the characteristic equation:

𝑎₀𝑡_𝑛 + 𝑎₁𝑡_𝑛−1 + ⋯ + 𝑎_𝑘𝑡_𝑛−𝑘 = 0

Step after finding characteristic polynomial?

Answer 4

Find roots: (x:p(x) = 0), if we have l roots which repeat m₁, m_l times:

t_n = ∑_1<=i<=l ∑_{0<=j<=mi- 1} c_(i,j)n^jr_iⁿ

To solve, expand and find c_(i,j) in system of linear equations.
BUT: time complexity can be read off without that step.

Question 5

Technique of the characteristic equation:

If 𝒙 = 𝒓_𝒊 is a ____of 𝒑(𝒙) then ____ is a solution to the recurrence.

Answer 5

If 𝒙 = 𝒓_𝒊 is a root of 𝒑(𝒙) then 𝒓_𝒊^𝒏 is a solution to the recurrence.

Question 6

Technique of the characteristic equation:

characteristic polynomial of the recurrence

All roots of 𝑝(𝑥) can be ______

Some root of 𝑝(𝑥) can appear _______________

(examples - research)

Answer 6

All roots of 𝑝(𝑥) can be different.

Some root of 𝑝(𝑥) can appear more than once.

Question 7

Technique of the characteristic equation - homogeneous

𝑎₀𝑡_𝑛 + 𝑎₁𝑡_𝑛−1 + ⋯ + 𝑎_𝑘𝑡_𝑛−𝑘 = 0

For which the characteristic polynomial of the recurrence p(x) has all roots, then:

t_n =

Answer 7

t_n = ∑_1<=i<=k c_ir_iⁿ

Question 8

Technique of the characteristic equation

Example 1 - Solve:

𝑓_𝑛 − 𝑓_𝑛−1 − 𝑓_𝑛−2 = 0

Given 𝑓₀ = 0, 𝑓₁ = 1

Question 9

Technique of the characteristic equation

Example 2 - Solve:

t_𝑛 − 3t_𝑛−1 − 4t_𝑛−2 = 0

Given t₀ = 0, t₁ = 5

Question 10

Technique of the characteristic equation

Example 3 - Solve:

t_𝑛 − 5t_𝑛−1 − 8t_𝑛−2 - 4t_𝑛−3 = 0

Given t₀ = 0, t₁ = 1, t₂ = 2

Question 11

Technique of the characteristic equation:

How to use it for inhomogeneous equations?

Answer 11

Try to get rid of the constant term 𝑏^𝑛𝑝(𝑛) by multiplication with a factor of the equation for other values of 𝑛

–> Obtain a homogeneous equation

Question 12

Technique of the characteristic equation:

inhomogeneous equation?

Answer 12

𝑎₀𝑡_𝑛 + 𝑎₁𝑡_𝑛−1 + ⋯ + 𝑎_𝑘𝑡_𝑛−𝑘 = 𝑏^𝑛𝑝(𝑛)

Question 13

Technique of the characteristic equation:

inhomogeneous equations

𝑎₀𝑡_𝑛 + 𝑎₁𝑡_𝑛−1 + ⋯ + 𝑎_𝑘𝑡_𝑛−𝑘 = 𝑏^𝑛𝑝(𝑛)

characteristic polynomial?

Answer 13

𝑎₀𝑡_𝑛 + 𝑎₁𝑡_𝑛−1 + ⋯ + 𝑎_𝑘𝑡_𝑛−𝑘 = 𝑏^𝑛𝑝(𝑛)

Has characteristic polynomial:

(𝑎₀𝑥^𝑘 + 𝑎₁𝑥^𝑘−1 + ⋯ + 𝑎_𝑘)(x - b)^{d + 1}

where 𝑑 is the degree of the polynomial 𝑝(𝑛)!
(careful consideration of initial conditions)

Question 14

Technique of the characteristic equation:

inhomogeneous equations

𝑎₀𝑡_𝑛 + 𝑎₁𝑡_𝑛−1 + ⋯ + 𝑎_𝑘𝑡_𝑛−𝑘 = 𝑏^𝑛𝑝(𝑛)

General solution approach?

Answer 14

t_n = a₁t_n-1 + … + g(n)
–>
g(n) = t_n + a₁t_n-1 + …. [I]
g(n-1) = t_n-1 _ a₁t_n-2 + … [II]

[I] - [II], repeat until 0 = t_n + … (homogeneous equation)

Question 15

Technique of the characteristic equation

Inhomogeneous

Example 4 - Solve:

t_𝑛 − 2t_𝑛−1 = 3ⁿ, n >= 0

Question 16

Technique of the characteristic equation

Inhomogeneous

Example 5 - Solve:

t_𝑛 − 2t_𝑛−1 = (n + 5)3ⁿ, n >= 1

Question 17

Change of variable

Example 6 - Solve:

T(n) = 4T(n/2) + n², if n is a power of 2, n >= 2

Question 18

Master Theorem

General form of equation that it works for

Answer 18

T(n) = lT(n/b) + cn^k, if n/n₀ is a power of b, n >= n₀

Question 19

Master Theorem

change of variable:

n = ?

Answer 19

𝑛 = 𝑏^𝑖𝑛₀

Question 20

Master Theorem

T(n) = lT(n/b) + cn^k, if n/n₀ is a power of b, n >= n₀

Yields?

Answer 20

Yielding 𝑡_𝑖 = 𝑙𝑡_𝑖−1 + 𝑐𝑛₀^𝑘𝑏^𝑖𝑘

Question 21

Master theorem

l < b^k

T(n) is in ….?

Answer 21

T(𝑛) ∈ Θ(𝑛^𝑘)

Question 22

Master theorem

l = b^k

T(n) is in ….?

Answer 22

T(𝑛) ∈ Θ(𝑛^𝑘logn)

Question 23

Master theorem

l > b^k

T(n) is in ….?

Answer 23

T(𝑛) ∈ Θ(𝑛^log_bl)