Steply

Solving recurrences

Discrete Math · 20 problems, easy to harder

▶ Watch the first one solved

How we do it

  1. First terms
  2. The number that stays the same
  3. The distance from it
  4. The formula
  5. Check

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

Worked examples

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

The question

Question: solve aₙ = 5aₙ₋₁, starting with a₀ = 2.

an = 5an − 1, a0 = 2

Solve means: find a formula for aₙ, so we can get any term without the ones before.

solve = a formula for an

1 First terms

First, a few terms.

Each one comes from the one before.

We start with a₀ = 2.

start
2

Then 5 times 2.

5 × 2

That is 10.

And so on.

10
5 × 10
50
5 × 50
250
5 × 250
1250

2 Times 5 each time

The rule only multiplies by 5 each time.

× 5 each time

Careful!

Times 5 again and again is a power of 5, not adding.

Careful: not an = 2 + 5n ✗

3 The formula

So aₙ is 2 times 5 to the n.

an = 2 × 5n

4 Check

Check n = 3 with the formula: it gives 250.

n = 3: formula gives 250

The table says 250 too.

Right!

table: a3 = 250

Let's look back.

First: first terms.

Then: times 5 each time.

Then: the formula.

Last: check.

Answer
an = 2 × 5n

▶ Watch it solved

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

The question

Question: solve aₙ = 2aₙ₋₁ + 1, starting with a₀ = 1.

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

Solve means: find a formula for aₙ, so we can get any term without the ones before.

solve = a formula for an

1 First terms

First, a few terms.

Each one comes from the one before.

We start with a₀ = 1.

start
1

Then 2 times 1, plus 1.

2 × 1 + 1

That is 3.

And so on.

3
2 × 3 + 1
7
2 × 7 + 1
15
2 × 15 + 1
31

2 The number that stays the same

Is there a number that the rule keeps the same?

Call it c.

If a term were c, the next would be 2c + 1, and it must be c again.

c = 2c + 1

Careful!

c is on both sides.

We solve for it like any equation.

Careful: not c = 2 + 1 = 3 ✗

Take away 2c on both sides.

c − 2c = 1

c minus 2c is −c.

−c = 1

Divide by −1: c = −1.

c = −1

Check it: 2 times −1, plus 1 is −1 again.

check: 2 × (−1) + 1 = −1 ✓

3 The distance from it

Now the distance from c: each term plus 1.

Look at the new column: 2, 4, 8, 16, 32.

Each one is 2 times the one before.

The distance from c grows by times 2.

× 2 each time

4 The formula

The distance starts at 2 and is multiplied by 2 each step: 2 times 2 to the n.

an + 1 = 2 × 2n

Take away 1 on both sides.

an = 2 × 2n − 1

2 is one more 2, so the powers join: 2 times 2 to the n is 2 to the n + 1.

= 2n + 1 − 1

5 Check

Check n = 3 with the formula: it gives 15.

n = 3: formula gives 15

The table says 15 too.

Right!

table: a3 = 15

Let's look back.

First: first terms.

Then: the number that stays the same.

Then: the distance from it.

Then: the formula.

Last: check.

Answer
= 2n + 1 − 1

▶ Watch it solved

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

The question

Question: solve aₙ = 2aₙ₋₁ + 1, starting with a₁ = 1.

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

Solve means: find a formula for aₙ, so we can get any term without the ones before.

solve = a formula for an

1 First terms

First, a few terms.

Each one comes from the one before.

We start with a₁ = 1.

start
1

Then 2 times 1, plus 1.

2 × 1 + 1

That is 3.

And so on.

3
2 × 3 + 1
7
2 × 7 + 1
15
2 × 15 + 1
31

2 The number that stays the same

Is there a number that the rule keeps the same?

Call it c.

If a term were c, the next would be 2c + 1, and it must be c again.

c = 2c + 1

Careful!

c is on both sides.

We solve for it like any equation.

Careful: not c = 2 + 1 = 3 ✗

Take away 2c on both sides.

c − 2c = 1

c minus 2c is −c.

−c = 1

Divide by −1: c = −1.

c = −1

Check it: 2 times −1, plus 1 is −1 again.

check: 2 × (−1) + 1 = −1 ✓

3 The distance from it

Now the distance from c: each term plus 1.

Look at the new column: 2, 4, 8, 16, 32.

Each one is 2 times the one before.

The distance from c grows by times 2.

× 2 each time

4 The formula

The distance starts at 2 and is multiplied by 2 each step: 2 times 2 to the n − 1.

an + 1 = 2 × 2n − 1

Take away 1 on both sides.

an = 2 × 2n − 1 − 1

2 is one more 2, so the powers join: 2 times 2 to the n − 1 is 2 to the n.

= 2n − 1

5 Check

Check n = 4 with the formula: it gives 15.

n = 4: formula gives 15

The table says 15 too.

Right!

table: a4 = 15

Let's look back.

First: first terms.

Then: the number that stays the same.

Then: the distance from it.

Then: the formula.

Last: check.

Answer
= 2n − 1

▶ 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), a_0 = 2
    Answer
    an = 2 × 5n
  2. solve a_n = 3a_(n-1), a_0 = 4
    Answer
    an = 4 × 3n
  3. solve a_n = a_(n-1) + 4, a_1 = 3
    Answer
    = 4n − 1
  4. solve a_n = a_(n-1) - 3, a_0 = 20
    Answer
    an = 20 − 3n
  5. solve a_n = 2a_(n-1), a_1 = 3
    Answer
    an = 3 × 2n − 1

Medium

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

Harder

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