Front Matter

0Review and Preliminaries

1Counting

2Sequences

3Symbolic Logic and also Proofs

4Graph Theory

5Additional Topics

Backmatter


Authored in PreTeXt
*

Section2.4Solving Recurrence Relations

¶Investigate!21

Consider the recurrence relation

eginequation*a_n = 5a_n-1 - 6a_n-2.endequation*

What sequence do you obtain if the initial conditions are (a_0 = 1 ext,) (a_1 = 2 ext?) Give a closed formula for this sequence.

You are watching: Find the solution to each of these recurrence relations with the given initial conditions

What sequence execute you gain if the initial problems are (a_0 = 1 ext,) (a_1 = 3 ext?) Give a closed formula.

What if (a_0 = 2) and (a_1 = 5 ext?) Find a closed formula.

We have viewed that it is frequently easier to find recursive interpretations than closed formulas. Lucky for us, there are a few techniques for converting recursive meanings to closed formulas. Doing so is dubbed fixing a recurrence relation. Recall that the recurrence relation is a recursive definition without the initial problems. For instance, the recurrence relation for the Fibonacci sequence is (F_n = F_n-1 + F_n-2 ext.) (This, along with the initial conditions (F_0 = 0) and also (F_1 = 1) offer the whole recursive definition for the sequence.)

Example2.4.1

Find a recurrence relation and also initial problems for (1, 5, 17, 53, 161, 485ldots ext.)


Solution

Finding the recurrence relation would be simpler if we had some context for the problem (choose the Tower of Hanoi, for example). Alas, we have actually just the sequence. Remember, the recurrence relation tells you just how to gain from previous terms to future terms. What is going on here? We might look at the differences between terms: (4, 12, 36, 108, ldots ext.) Notice that these are growing by a aspect of 3. Is the original sequence as well? (1cdot 3 = 3 ext,) (5 cdot 3 = 15 ext,) (17 cdot 3 = 51) and also so on. It shows up that we constantly finish up via 2 much less than the next term. Aha!

So (a_n = 3a_n-1 + 2) is our recurrence relation and also the initial condition is (a_0 = 1 ext.)


We are going to attempt to solve these recurrence relationships. By this we intend somepoint extremely equivalent to addressing differential equations: we desire to uncover a function of (n) (a closed formula) which satisfies the recurrence relation, and also the initial condition. 2 Recurrence relations are sometimes referred to as difference equations considering that they deserve to define the difference in between terms and this highlights the relation to differential equations further. As with for differential equations, finding a solution could be tricky, but checking that the solution is correct is straightforward.

Example2.4.2

Check that (a_n = 2^n + 1) is a solution to the recurrence relation (a_n = 2a_n-1 - 1) via (a_1 = 3 ext.)


Solution

First, it is easy to examine the initial condition: (a_1) must be (2^1 + 1) according to our closed formula. Indeed, (2^1 + 1 = 3 ext,) which is what we want. To check that our proposed solution satisfies the recurrence relation, attempt plugging it in.

eginalign*2a_n-1 - 1 amp = 2(2^n-1 + 1) - 1 \amp = 2^n + 2 - 1 \amp = 2^n +1\amp = a_n.endalign*

That"s what our recurrence relation says! We have actually a solution.


Sometimes we have the right to be clever before and resolve a recurrence relation by inspection. We generate the sequence utilizing the recurrence relation and also save track of what we are doing so that we have the right to check out just how to jump to finding simply the (a_n) term. Here are two examples of how you could do that.

Telescoping describes the phenomenon as soon as many type of terms in a huge amount cancel out - so the amount “telescopes.” For example:

eginequation*(2 - 1) + (3 - 2) + (4 - 3) + cdots + (100 - 99) + (101 - 100) = -1 + 101endequation*

because eincredibly third term looks like: (2 + -2 = 0 ext,) and also then (3 + -3 = 0) and so on.

We can use this behavior to solve recurrence relationships. Here is an instance.

Example2.4.3

Solve the recurrence relation (a_n = a_n-1 + n) through initial term (a_0 = 4 ext.)


Solution

To obtain a feel for the recurrence relation, create out the first few regards to the sequence: (4, 5, 7, 10, 14, 19, ldots ext.) Look at the difference between terms. (a_1 - a_0 = 1) and also (a_2 - a_1 = 2) and so on. The essential point here is that the distinction in between terms is (n ext.) We have the right to write this explicitly: (a_n - a_n-1 = n ext.) Of course, we can have came down on this conclusion directly from the recurrence relation by subtracting (a_n-1) from both sides.

Now usage this equation over and also over aacquire, transforming (n) each time:

eginalign*a_1 - a_0 amp = 1\a_2 - a_1 amp = 2\a_3 - a_2 amp = 3\vdots quad amp quad vdots\a_n - a_n-1 amp = n.endalign*

Add all these equations together. On the right-hand side, we obtain the amount (1 + 2 + 3 + cdots + n ext.) We currently know this have the right to be simplified to (fracn(n+1)2 ext.) What happens on the left-hand side? We get

eginequation*(a_1 - a_0) + (a_2 - a_1) + (a_3 - a_2) + cdots (a_n-1 - a_n-2)+ (a_n - a_n-1).endequation*

This amount telescopes. We are left via only the (-a_0) from the first equation and the (a_n) from the last equation. Putting this all together we have actually (-a_0 + a_n = fracn(n+1)2) or (a_n = fracn(n+1)2 + a_0 ext.) But we recognize that (a_0 = 4 ext.) So the solution to the recurrence relation, topic to the initial condition is

eginequation*a_n = fracn(n+1)2 + 4.endequation*

(Now that we understand that, we should notification that the sequence is the result of including 4 to each of the triangular numbers.)


The over example reflects a means to resolve recurrence relationships of the form (a_n = a_n-1 + f(n)) where (sum_k = 1^n f(k)) has a well-known closed formula. If you recompose the recurrence relation as (a_n - a_n-1 = f(n) ext,) and also then include up all the different equations through (n) varying between 1 and also (n ext,) the left-hand also side will constantly provide you (a_n - a_0 ext.) The right-hand also side will be (sum_k = 1^n f(k) ext,) which is why we should understand the closed formula for that sum.

However before, telescoping will not assist us with a recursion such as (a_n = 3a_n-1 + 2) given that the left-hand side will certainly not telescope. You will certainly have (-3a_n-1)"s but only one (a_n-1 ext.) However before, we have the right to still be clever if we usage iteration.

We have already watched an example of iteration as soon as we found the closed formula for arithmetic and also geometric sequences. The concept is, we iterate the procedure of finding the next term, starting via the known initial condition, up until we have actually (a_n ext.) Then we simplify. In the arithmetic sequence example, we streamlined by multiplying (d) by the variety of times we add it to (a) once we gain to (a_n ext,) to acquire from (a_n = a + d + d + d + cdots + d) to (a_n = a + dn ext.)

To view how this works, let"s go with the very same example we provided for telescoping, yet this time use iteration.

Example2.4.4

Use iteration to deal with the recurrence relation (a_n = a_n-1 + n) with (a_0 = 4 ext.)


Solution

Again, begin by creating down the recurrence relation as soon as (n = 1 ext.) This time, don"t subtract the (a_n-1) terms to the other side:

eginequation*a_1 = a_0 + 1.endequation*

Now (a_2 = a_1 + 2 ext,) yet we recognize what (a_1) is. By substitution, we get

eginequation*a_2 = (a_0 + 1) + 2.endequation*

Now go to (a_3 = a_2 + 3 ext,) using our recognized worth of (a_2 ext:)

eginequation*a_3 = ((a_0 + 1) + 2) + 3.endequation*

We notification a pattern. Each time, we take the previous term and also include the present index. So

eginequation*a_n = ((((a_0 + 1) +2)+3)+cdots + n-1) + n.endequation*

Regrouping terms, we alert that (a_n) is simply (a_0) plus the sum of the integers from (1) to (n ext.) So, because (a_0 = 4 ext,)

eginequation*a_n = 4 + fracn(n+1)2.endequation*

Of course in this situation we still required to know formula for the amount of (1,ldots,n ext.) Let"s try iteration via a sequence for which telescoping doesn"t occupational.

Example2.4.5

Solve the recurrence relation (a_n = 3a_n-1 + 2) subject to (a_0 = 1 ext.)


Solution

Again, we iteprice the recurrence relation, building up to the index (n ext.)

eginalign*a_1 amp = 3a_0 + 2\a_2 amp = 3(a_1) + 2 = 3(3a_0 + 2) + 2\a_3 amp = 3 + 2 = 3<3(3a_0 + 2) + 2> + 2\vdots amp qquad vdots qquad qquad vdots\a_n amp = 3(a_n-1) + 2 = 3(3(3(3cdots(3a_0 + 2) + 2) + 2)cdots + 2)+ 2.endalign*

It is challenging to view what is happening right here bereason we have to distribute all those 3"s. Let"s try again, this time simplifying a little bit as we go.

eginalign*a_1 amp = 3a_0 + 2\a_2 amp = 3(a_1) + 2 = 3(3a_0 + 2) + 2 = 3^2a_0 + 2cdot 3 + 2\a_3 amp = 3 + 2 = 3<3^2a_0 + 2cdot 3 + 2> + 2 = 3^3 a_0 + 2 cdot 3^2 + 2 cdot 3 + 2\vdots amp qquadquad vdots hspace2in vdots\a_n amp = 3(a_n-1) + 2 = 3(3^n-1a_0 + 2 cdot 3^n-2 + cdots +2)+ 2\amp qquad qquad = 3^n a_0 + 2cdot 3^n-1 + 2 cdot 3^n-2 + cdots + 2cdot 3 + 2.endalign*

Now we simplify. (a_0 = 1 ext,) so we have (3^n + langle extstuff angle ext.) Keep in mind that all the various other terms have a 2 in them. In truth, we have a geometric sum through first term (2) and also prevalent proportion (3 ext.) We have seen just how to simplify (2 + 2cdot 3 + 2 cdot 3^2 + cdots + 2cdot 3^n-1 ext.) We acquire (frac2-2cdot 3^n-2) which simplifies to (3^n - 1 ext.) Putting this in addition to the initially (3^n) term offers our closed formula:

eginequation*a_n = 2cdot 3^n - 1.endequation*

Iteration have the right to be messy, yet when the recurrence relation only describes one previous term (and possibly some attribute of (n)) it can occupational well. However, trying to iterate a recurrence relation such as (a_n = 2 a_n-1 + 3 a_n-2) will be way also complicated. We would certainly have to save track of two sets of previous terms, each of which were expressed by two previous terms, and also so on. The size of the formula would certainly grow greatly (double each time, in fact). Luckily tbelow happens to be a technique for solving recurrence relations which functions incredibly well on relationships like this.

SubsectionThe Characteristic Root Technique

Suppose we desire to deal with a recurrence relation expressed as a combination of the 2 previous terms, such as (a_n = a_n-1 + 6a_n-2 ext.) In various other words, we desire to find a role of (n) which satisfies (a_n - a_n-1 - 6a_n-2 = 0 ext.) Now iteration is as well complicated, yet think just for a second what would certainly happen if we did iteprice. In each step, we would certainly, among other things, multiply a previous iteration by 6. So our closed formula would certainly incorporate (6) multiplied some variety of times. Thus it is reasonable to guess the solution will contain components that look geometric. Perhaps the solution will take the form (r^n) for some constant (r ext.)

The nice point is, we understand exactly how to check whether a formula is actually a solution to a recurrence relation: plug it in. What happens if we plug in (r^n) right into the recursion above? We get

eginequation*r^n - r^n-1 - 6r^n-2 = 0.endequation*

Now deal with for (r ext:)

eginequation*r^n-2(r^2 - r - 6) = 0,endequation*

so by factoring, (r = -2) or (r = 3) (or (r = 0 ext,) although this does not assist us). This tells us that (a_n = (-2)^n) is a solution to the recurrence relation, as is (a_n = 3^n ext.) Which one is correct? They both are, unless we specify initial problems. Notice we could additionally have actually (a_n = (-2)^n + 3^n ext.) Or (a_n = 7(-2)^n + 4cdot 3^n ext.) In reality, for any type of (a) and (b ext,) (a_n = a(-2)^n + b 3^n) is a solution (try plugging this right into the recurrence relation). To uncover the values of (a) and also (b ext,) usage the initial conditions.

This points us in the direction of an extra general strategy for solving recurrence connections. Notice we will certainly always be able to factor out the (r^n-2) as we did over. So we really just care about the other part. We call this other component the characteristic equation for the recurrence relation. We are interested in finding the roots of the characteristic equation, which are dubbed (surprise) the characteristic roots.

Characteristic Roots

Given a recurrence relation (a_n + alpha a_n-1 + eta a_n-2 = 0 ext,) the characteristic polynomial is

eginequation*x^2 + alpha x + etaendequation*

providing the characteristic equation:

eginequation*x^2 + alpha x + eta = 0.endequation*

If (r_1) and (r_2) are two distinctive roots of the characteristic polynomial (i.e, remedies to the characteristic equation), then the solution to the recurrence relation is

eginequation*a_n = ar_1^n + br_2^n,endequation*

wbelow (a) and (b) are constants figured out by the initial problems.

Example2.4.6

Solve the recurrence relation (a_n = 7a_n-1 - 10 a_n-2) via (a_0 = 2) and also (a_1 = 3 ext.)


Recreate the recurrence relation (a_n - 7a_n-1 + 10a_n-2 = 0 ext.) Now form the characteristic equation:

eginequation*x^2 - 7x + 10 = 0endequation*

and resolve for (x ext:)

eginequation*(x - 2) (x - 5) = 0endequation*

so (x = 2) and also (x = 5) are the characteristic roots. We therefore know that the solution to the recurrence relation will certainly have the form

eginequation*a_n = a 2^n + b 5^n.endequation*

To discover (a) and (b ext,) plug in (n =0) and also (n = 1) to obtain a system of 2 equations via two unknowns:

eginalign*2 amp = a 2^0 + b 5^0 = a + b\3 amp = a 2^1 + b 5^1 = 2a + 5bendalign*

Solving this system offers (a = frac73) and also (b = -frac13) so the solution to the recurrence relation is

eginequation*a_n = frac732^n - frac13 3^n.endequation*

Perhaps the many well known recurrence relation is (F_n = F_n-1 + F_n-2 ext,) which in addition to the initial conditions (F_0 = 0) and also (F_1= 1) specifies the Fibonacci sequence. But notice that this is precisely the type of recurrence relation on which we have the right to use the characteristic root method. When you carry out, the just point that transforms is that the characteristic equation does not aspect, so you have to usage the quadratic formula to discover the characteristic roots. In reality, doing so provides the 3rd most famed irrational number, (varphi ext,) the gold ratio.

Before leaving the characteristic root strategy, we have to think around what can take place as soon as you deal with the characteristic equation. We have an example above in which the characteristic polynomial has actually 2 distinct roots. These roots can be integers, or probably irrational numbers (requiring the quadratic formula to find them). In these instances, we know what the solution to the recurrence relation looks favor.

However, it is feasible for the characteristic polynomial to only have actually one root. This can take place if the characteristic polynomial components as ((x - r)^2 ext.) It is still the instance that (r^n) would be a solution to the recurrence relation, however we won"t be able to uncover options for all initial problems making use of the basic form (a_n = ar_1^n + br_2^n ext,) because we can not identify in between (r_1^n) and also (r_2^n ext.) We are in luck though:

Characteristic Root Technique for Repeated Roots

Suppose the recurrence relation (a_n = alpha a_n-1 + eta a_n-2) has a characteristic polynomial via only one root (r ext.) Then the solution to the recurrence relation is

eginequation*a_n = ar^n + bnr^nendequation*

wright here (a) and (b) are constants identified by the initial problems.

Notice the additional (n) in (bnr^n ext.) This enables us to deal with for the constants (a) and also (b) from the initial conditions.

Example2.4.7

Solve the recurrence relation (a_n = 6a_n-1 - 9a_n-2) via initial problems (a_0 = 1) and also (a_1 = 4 ext.)


The characteristic polynomial is (x^2 - 6x + 9 ext.) We resolve the characteristic equation

eginequation*x^2 - 6x + 9 = 0endequation*

by factoring:

eginequation*(x - 3)^2 = 0endequation*

so (x =3) is the only characteristic root. Therefore we understand that the solution to the recurrence relation has actually the form

eginequation*a_n = a 3^n + bn3^nendequation*

for some constants (a) and (b ext.) Now usage the initial conditions:

eginalign*a_0 = 1 amp = a 3^0 + bcdot 0 cdot 3^0 = a\a_1 = 4 amp = acdot 3 + bcdot 1 cdot3 = 3a + 3b.endalign*

Since (a = 1 ext,) we uncover that (b = frac13 ext.) As such the solution to the recurrence relation is

eginequation*a_n = 3^n + frac13n3^n.endequation*

Although we will certainly not take into consideration examples even more complex than these, this characteristic root strategy can be used to much more facility recurrence relationships. For instance, (a_n = 2a_n-1 + a_n-2 - 3a_n-3) has actually characteristic polynomial (x^3 - 2 x^2 - x + 3 ext.) Assuming you check out how to factor such a level 3 (or more) polynomial you have the right to easily discover the characteristic roots and as such solve the recurrence relation (the solution would look favor (a_n = ar_1^n + br_2^n + cr_3^n) if there were 3 distinct roots). It is also possible to deal with recurrence relationships of the develop (a_n = alpha a_n-1 + eta a_n-2 + C) for some continuous (C ext.) It is likewise possible (and also acceptable) for the characteristic roots to be facility numbers.

SubsectionExercises

¶1

Find the next 2 terms in ((a_n)_nge 0) start (3, 5, 11, 21, 43, 85ldots. ext.) Then provide a recursive meaning for the sequence. Finally, use the characteristic root strategy to discover a closed formula for the sequence.


171 and also 341. (a_n = a_n-1 + 2a_n-2) with (a_0 = 3) and also (a_1 = 5 ext.) Closed formula: (a_n = frac832^n + frac13(-1)^n ext.) To uncover this fix the characteristic polynomial, (x^2 - x - 2 ext,) to get characteristic roots (x = 2) and (x=-1 ext.) Then solve the system

eginalign*3 amp = a + b\5 amp = 2a - bendalign*

(a_n = 3 + 2^n+1 ext.) We need to use telescoping or iteration below. For example, telescoping gives

eginalign*a_1 - a_0 amp = 2^1\a_2 - a_1 amp = 2^2\a_3 - a_2 amp = 2^3\vdotsamp vdots \a_n - a_n-1 amp = 2^nendalign*

which sums to (a_n - a_0 = 2^n+1 - 2) (utilizing the multiply-shift-subtract technique from Section 2.2 for the right-hand side). Substituting (a_0 = 5) and solving for (a_n) completes the solution.


We claim (a_n = 4^n) functions. Plug it in: (4^n = 3(4^n-1) + 4(4^n-2) ext.) This works - just simplify the right-hand side.


4

Find the solution to the recurrence relation (a_n = 3a_n-1 + 4a_n-2) with initial terms (a_0 = 2) and (a_1 = 3 ext.)


5

Find the solution to the recurrence relation (a_n = 3a_n-1 + 4a_n-2) via initial terms (a_0 = 5) and also (a_1 = 8 ext.)

6

Solve the recurrence relation (a_n = 2a_n-1 - a_n-2 ext.)

What is the solution if the initial terms are (a_0 = 1) and (a_1 = 2 ext?)

What do the initial terms should be in order for (a_9 = 30 ext?)

For which (x) are tbelow initial terms which make (a_9 = x ext?)

7

Solve the recurrence relation (a_n = 3a_n-1 + 10a_n-2) through initial terms (a_0 = 4) and also (a_1 = 1 ext.)

8

Suppose that (r^n) and (q^n) are both remedies to a recurrence relation of the create (a_n = alpha a_n-1 + eta a_n-2 ext.) Prove that (ccdot r^n + d cdot q^n) is also a solution to the recurrence relation, for any kind of constants (c, d ext.)

9

Think earlier to the magical candy machine at your area grocery save. Suppose that the initially time a quarter is put into the machine 1 Skittle comes out. The second time, 4 Skittles, the 3rd time 16 Skittles, the fourth time 64 Skittles, etc.

Find both a recursive and also closed formula for just how many Skittles the nth customer gets.

Check your solution for the closed formula by solving the recurrence relation using the Characteristic Root strategy.

10

You have actually accessibility to (1 imes 1) tiles which come in 2 different colors and (1 imes 2) tiles which come in 3 different colors. We want to figure out just how many different (1 imes n) course deindications we can make out of these tiles.

Find a recursive interpretation for the sequence (a_n) of courses of length (n ext.)

Solve the recurrence relation utilizing the Characteristic Root strategy.

11

Let (a_n) be the number of (1 imes n) tile deindicators you deserve to make utilizing (1 imes 1) squares easily accessible in 4 colors and also (1 imes 2) dominoes easily accessible in 5 colors.

First, uncover a recurrence relation to define the trouble. Explain why the recurrence relation is correct (in the context of the problem).

See more: Wrecking Ball Lip Sync - Anne Hathaway'S Wrecking Ball Vs

Write out the initially 6 terms of the sequence (a_1, a_2, ldots ext.)

Solve the recurrence relation. That is, find a closed formula for (a_n ext.)

12

Consider the recurrence relation (a_n = 4a_n-1 - 4a_n-2 ext.)

Find the general solution to the recurrence relation (beware the recurring root).