Steply

Second-order recurrences

Discrete Math · 20 problems, easy to harder

▶ Watch the first one solved

How we do it

  1. Everything on one side
  2. The characteristic equation
  3. Solve it
  4. The general form
  5. Use the start values
  6. Check

The steps for Solve a_n = 5a_(n-1) - 6a_(n-2), a_0 = 2, a_1 = 5. Every solution names its steps, so you always know what comes next.

Worked examples

Solve a_n = 5a_(n-1) - 6a_(n-2), a_0 = 2, a_1 = 5 Easy

The question

Question: solve aₙ = 5aₙ₋₁ − 6aₙ₋₂, with a₀ = 2 and a₁ = 5.

an = 5an − 1 − 6an − 2, a0 = 2, a1 = 5

1 Everything on one side

Move everything to one side.

Each term changes its sign when it moves.

an − 5an − 1 + 6an − 2 = 0

2 The characteristic equation

Powers are good at this: try aₙ = x to the n, for some number x.

try an = xn

Put x to the n in for aₙ, x to the n minus 1 for aₙ₋₁, and so on.

xn − 5xn − 1 + 6xn − 2 = 0

Divide everything by x to the n minus 2: the powers drop to 2, 1 and 0.

This is the characteristic equation.

x2 − 5x + 6 = 0
÷ xn − 2 on both sides

Careful!

Watch the signs.

The terms moved to the left, so their signs changed.

Careful: not x2 − 5x − 6 = 0 ✗

3 Solve it

Factor: we need two numbers that multiply to 6 and add to −5: −2 and −3.

(x − 2)(x − 3) = 0
(−2) × (−3) = 6, (−2) + (−3) = −5

So x = 2 or x = 3.

x = 2 or 3

4 The general form

Each root gives a power that works.

Any mix of them works too: A times 2 to the n, plus B times 3 to the n.

an = A × 2n + B × 3n

5 Use the start values

n = 0: every power to the 0 is 1.

So A + B = 2.

A + B = 2 ①

n = 1: 2A + 3B = 5.

2A + 3B = 5 ②

From equation 1: A = 2 − B.

A = 2 − B

Put it into equation 2.

2(2 − B) + 3B = 5

Open the bracket.

4 − 2B + 3B = 5

Like terms: B.

4 + B = 5

Take away 4 on both sides.

B = 1

And A = 2 minus B, that is 1.

A = 2 − 1 = 1

So aₙ = 2ⁿ + 3ⁿ.

an = 2n + 3n

6 Check

Check a₂.

The rule: 5 times 5, minus 6 times 2: 13.

rule: a2 = 5 × 5 − 6 × 2 = 13

The formula with n = 2 gives 13 too.

Right!

formula: a2 = 13

Let's look back.

First: everything on one side.

Then: the characteristic equation.

Then: solve it.

Then: the general form.

Then: use the start values.

Last: check.

Answer
an = 2n + 3n

▶ Watch it solved

Solve a_n = 2a_(n-1) + 3a_(n-2), a_0 = 2, a_1 = 2 Medium

The question

Question: solve aₙ = 2aₙ₋₁ + 3aₙ₋₂, with a₀ = 2 and a₁ = 2.

an = 2an − 1 + 3an − 2, a0 = 2, a1 = 2

1 Everything on one side

Move everything to one side.

Each term changes its sign when it moves.

an − 2an − 1 − 3an − 2 = 0

2 The characteristic equation

Powers are good at this: try aₙ = x to the n, for some number x.

try an = xn

Put x to the n in for aₙ, x to the n minus 1 for aₙ₋₁, and so on.

xn − 2xn − 1 − 3xn − 2 = 0

Divide everything by x to the n minus 2: the powers drop to 2, 1 and 0.

This is the characteristic equation.

x2 − 2x − 3 = 0
÷ xn − 2 on both sides

Careful!

Watch the signs.

The terms moved to the left, so their signs changed.

Careful: not x2 − 2x + 3 = 0 ✗

3 Solve it

Factor: we need two numbers that multiply to −3 and add to −2: 1 and −3.

(x + 1)(x − 3) = 0
1 × (−3) = −3, 1 + (−3) = −2

So x = −1 or x = 3.

x = −1 or 3

4 The general form

Each root gives a power that works.

Any mix of them works too: A times −1 to the n, plus B times 3 to the n.

an = A × (−1)n + B × 3n

5 Use the start values

n = 0: every power to the 0 is 1.

So A + B = 2.

A + B = 2 ①

n = 1: −1A + 3B = 2.

−A + 3B = 2 ②

From equation 1: A = 2 − B.

A = 2 − B

Put it into equation 2.

-1(2 − B) + 3B = 2

Open the bracket.

−2 + 1B + 3B = 2

Like terms: 4B.

−2 + 4B = 2

Take away −2 on both sides.

4B = 4

Divide by 4: B = 1.

B = 1

And A = 2 minus B, that is 1.

A = 2 − 1 = 1

So aₙ = (−1)ⁿ + 3ⁿ.

an = (−1)n + 3n

6 Check

Check a₂.

The rule: 2 times 2, plus 3 times 2: 10.

rule: a2 = 2 × 2 + 3 × 2 = 10

The formula with n = 2 gives 10 too.

Right!

formula: a2 = 10

Let's look back.

First: everything on one side.

Then: the characteristic equation.

Then: solve it.

Then: the general form.

Then: use the start values.

Last: check.

Answer
an = (−1)n + 3n

▶ Watch it solved

Solve a_n = 4a_(n-1) - 4a_(n-2), a_0 = 1, a_1 = 4 Harder

The question

Question: solve aₙ = 4aₙ₋₁ − 4aₙ₋₂, with a₀ = 1 and a₁ = 4.

an = 4an − 1 − 4an − 2, a0 = 1, a1 = 4

1 Everything on one side

Move everything to one side.

Each term changes its sign when it moves.

an − 4an − 1 + 4an − 2 = 0

2 The characteristic equation

Powers are good at this: try aₙ = x to the n, for some number x.

try an = xn

Put x to the n in for aₙ, x to the n minus 1 for aₙ₋₁, and so on.

xn − 4xn − 1 + 4xn − 2 = 0

Divide everything by x to the n minus 2: the powers drop to 2, 1 and 0.

This is the characteristic equation.

x2 − 4x + 4 = 0
÷ xn − 2 on both sides

Careful!

Watch the signs.

The terms moved to the left, so their signs changed.

Careful: not x2 − 4x − 4 = 0 ✗

3 Solve it

Factor: we need two numbers that multiply to 4 and add to −4: −2 and −2.

(x − 2)² = 0
(−2) × (−2) = 4, (−2) + (−2) = −4

Both brackets are the same: one root, 2, twice.

x = 2 (twice)

4 The general form

With one root twice, the second part gets an extra n: A times 2 to the n, plus B times n times 2 to the n.

an = A × 2n + B × n × 2n

5 Use the start values

n = 0: the n in front makes the B part 0.

So A = 1.

A = 1 ①

n = 1: 2A + 2B = 4.

2A + 2B = 4 ②

Put A = 1 in.

2 + 2B = 4

Take away 2.

2B = 2

Divide by 2: B = 1.

B = 1

So aₙ = 2ⁿ + n × 2ⁿ.

an = 2n + n × 2n

6 Check

Check a₂.

The rule: 4 times 4, minus 4 times 1: 12.

rule: a2 = 4 × 4 − 4 × 1 = 12

The formula with n = 2 gives 12 too.

Right!

formula: a2 = 12

Let's look back.

First: everything on one side.

Then: the characteristic equation.

Then: solve it.

Then: the general form.

Then: use the start values.

Last: check.

Answer
an = 2n + n × 2n

▶ Watch it solved

Practice

Try each one, then open the answer. Stuck? Open the problem to watch every step.

Easy

  1. solve a_n = 5a_(n-1) - 6a_(n-2), a_0 = 2, a_1 = 5
    Answer
    an = 2n + 3n
  2. solve a_n = 6a_(n-1) - 8a_(n-2), a_0 = 2, a_1 = 6
    Answer
    an = 2n + 4n
  3. solve a_n = 7a_(n-1) - 10a_(n-2), a_0 = 3, a_1 = 9
    Answer
    an = 2 × 2n + 5n
  4. solve a_n = 8a_(n-1) - 15a_(n-2), a_0 = 2, a_1 = 8
    Answer
    an = 3n + 5n
  5. solve a_n = 8a_(n-1) - 12a_(n-2), a_0 = 2, a_1 = 8
    Answer
    an = 2n + 6n

Medium

  1. solve a_n = 2a_(n-1) + 3a_(n-2), a_0 = 2, a_1 = 2
    Answer
    an = (−1)n + 3n
  2. solve a_n = 7a_(n-1) - 12a_(n-2), a_0 = 0, a_1 = 1
    Answer
    an = −3n + 4n
  3. solve a_n = a_(n-1) + 6a_(n-2), a_0 = 0, a_1 = 5
    Answer
    an = −(−2)n + 3n
  4. solve a_n = a_(n-1) + 2a_(n-2), a_0 = 0, a_1 = 3
    Answer
    an = −(−1)n + 2n
  5. solve a_n = 5a_(n-1) - 6a_(n-2), a_0 = 1, a_1 = 4
    Answer
    an = −2n + 2 × 3n
  6. solve a_n = 2a_(n-1) + 8a_(n-2), a_0 = 2, a_1 = 2
    Answer
    an = (−2)n + 4n
  7. solve a_n = 9a_(n-1) - 20a_(n-2), a_0 = 2, a_1 = 9
    Answer
    an = 4n + 5n
  8. solve a_n = 3a_(n-1) + 4a_(n-2), a_0 = 2, a_1 = 3
    Answer
    an = (−1)n + 4n
  9. solve a_n = a_(n-1) + 12a_(n-2), a_0 = 2, a_1 = 1
    Answer
    an = (−3)n + 4n
  10. solve a_n = -a_(n-1) + 6a_(n-2), a_0 = 2, a_1 = -1
    Answer
    an = (−3)n + 2n

Harder

  1. solve a_n = 4a_(n-1) - 4a_(n-2), a_0 = 1, a_1 = 4
    Answer
    an = 2n + n × 2n
  2. solve a_n = 6a_(n-1) - 9a_(n-2), a_0 = 1, a_1 = 6
    Answer
    an = 3n + n × 3n
  3. solve a_n = -4a_(n-1) - 4a_(n-2), a_0 = 1, a_1 = 0
    Answer
    an = (−2)n − n × (−2)n
  4. solve a_n = 8a_(n-1) - 16a_(n-2), a_0 = 2, a_1 = 12
    Answer
    an = 2 × 4n + n × 4n
  5. solve a_n = 10a_(n-1) - 25a_(n-2), a_0 = 1, a_1 = 10
    Answer
    an = 5n + n × 5n