Front Matter

0Introduction and also 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

\beginequation*a_n = 5a_n-1 - 6a_n-2.\endequation*

What sequence perform you obtain if the initial problems are \(a_0 = 1\text,\) \(a_1 = 2\text?\) offer a closed formula for this sequence.

You are watching: The number which best completes the sequence below is: 1 5 17 53 161

What sequence do you gain if the initial conditions are \(a_0 = 1\text,\) \(a_1 = 3\text?\) give a close up door formula.

What if \(a_0 = 2\) and \(a_1 = 5\text?\) discover a close up door formula.

We have seen the it is often simpler to discover recursive meanings than closed formulas. Lucky for us, there are a few techniques for converting recursive interpretations to closeup of the door formulas. Doing therefore is referred to as solving a recurrence relation. Recall that the recurrence relation is a recursive definition without the early stage conditions. For example, the recurrence relation because that the Fibonacci sequence is \(F_n = F_n-1 + F_n-2\text.\) (This, along with the initial conditions \(F_0 = 0\) and \(F_1 = 1\) give the whole recursive definition for the sequence.)

Example2.4.1

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


Solution

Finding the recurrence relation would certainly be much easier if we had some context because that the problem (like the Tower that Hanoi, for example). Alas, we have only the sequence. Remember, the recurrence relation tells you how to get from previous terms to future terms. What is going on here? We might look in ~ the differences between terms: \(4, 12, 36, 108, \ldots\text.\) notification that these are farming by a variable of 3. Is the initial sequence together well? \(1\cdot 3 = 3\text,\) \(5 \cdot 3 = 15\text,\) \(17 \cdot 3 = 51\) and so on. It appears that we always end up v 2 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\text.\)


We space going to try to solve this recurrence relations. By this we mean something very comparable to resolving differential equations: we want to find a role of \(n\) (a close up door formula) i m sorry satisfies the recurrence relation, and the early condition. 2 Recurrence relationships are occasionally called difference equations since they can explain the difference in between terms and also this highlights the relationship to differential equations further. Just like for differential equations, recognize a solution could be tricky, yet checking that the equipment is correct is easy.

Example2.4.2

Check the \(a_n = 2^n + 1\) is a equipment to the recurrence relationship \(a_n = 2a_n-1 - 1\) v \(a_1 = 3\text.\)


Solution

First, it is simple to check the initial condition: \(a_1\) should be \(2^1 + 1\) follow to our closed formula. Indeed, \(2^1 + 1 = 3\text,\) i beg your pardon is what we want. To examine that ours proposed equipment satisfies the recurrence relation, try plugging it in.

\beginalign*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 a solution.


Sometimes we can be clever and solve a recurrence relation by inspection. We generate the sequence using the recurrence relation and also keep monitor of what we space doing so the we can see exactly how to jump to finding just the \(a_n\) term. Here are two examples of exactly how you can do that.

Telescoping describes the phenomenon when many terms in a big sum cancel out - for this reason the amount “telescopes.” for example:

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

because every third term look at like: \(2 + -2 = 0\text,\) and then \(3 + -3 = 0\) and also so on.

We deserve to use this actions to fix recurrence relations. Here is an example.

Example2.4.3

Solve the recurrence relationship \(a_n = a_n-1 + n\) v initial term \(a_0 = 4\text.\)


Solution

To acquire a feel for the recurrence relation, write out the first few terms the the sequence: \(4, 5, 7, 10, 14, 19, \ldots\text.\) Look in ~ the difference between terms. \(a_1 - a_0 = 1\) and \(a_2 - a_1 = 2\) and so on. The key thing below is the the difference between terms is \(n\text.\) We have the right to write this explicitly: \(a_n - a_n-1 = n\text.\) of course, we might have arrived at this conclusion straight from the recurrence relationship by individually \(a_n-1\) indigenous both sides.

Now use this equation over and over again, changing \(n\) every time:

\beginalign*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 every these equations together. Top top the right-hand side, we acquire the sum \(1 + 2 + 3 + \cdots + n\text.\) We currently know this have the right to be simplified to \(\fracn(n+1)2\text.\) What wake up on the left-hand side? we get

\beginequation*(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 sum telescopes. We room left with only the \(-a_0\) from the very first equation and also the \(a_n\) native the critical equation. Placing this all with each other we have \(-a_0 + a_n = \fracn(n+1)2\) or \(a_n = \fracn(n+1)2 + a_0\text.\) yet we know that \(a_0 = 4\text.\) for this reason the systems to the recurrence relation, topic to the initial problem is

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

(Now the we understand that, us should notice that the succession is the result of adding 4 to every of the triangular numbers.)


The above example mirrors a way to settle recurrence relationships of the type \(a_n = a_n-1 + f(n)\) where \(\sum_k = 1^n f(k)\) has a well-known closed formula. If girlfriend rewrite the recurrence relation together \(a_n - a_n-1 = f(n)\text,\) and then add up all the different equations through \(n\) ranging in between 1 and also \(n\text,\) the left-hand side will always give girlfriend \(a_n - a_0\text.\) The right-hand side will certainly be \(\sum_k = 1^n f(k)\text,\) which is why we require to know the close up door formula for the sum.

However, telescoping will certainly not aid us with a recursion such as \(a_n = 3a_n-1 + 2\) because the left-hand side will not telescope. Friend will have \(-3a_n-1\)"s but only one \(a_n-1\text.\) However, we have the right to still it is in clever if we use iteration.

We have currently seen an example of iteration as soon as we found the closed formula for arithmetic and geometric sequences. The idea is, we iterate the process of detect the next term, starting with the recognized initial condition, up till we have \(a_n\text.\) Then us simplify. In the arithmetic sequence example, we streamlined by multiply \(d\) by the variety of times we include it come \(a\) when we gain to \(a_n\text,\) to gain from \(a_n = a + d + d + d + \cdots + d\) to \(a_n = a + dn\text.\)

To see how this works, let"s go through the same instance we supplied for telescoping, however this time usage iteration.

Example2.4.4

Use iteration to solve the recurrence relationship \(a_n = a_n-1 + n\) v \(a_0 = 4\text.\)


Solution

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

\beginequation*a_1 = a_0 + 1.\endequation*

Now \(a_2 = a_1 + 2\text,\) however we recognize what \(a_1\) is. By substitution, us get

\beginequation*a_2 = (a_0 + 1) + 2.\endequation*

Now walk to \(a_3 = a_2 + 3\text,\) making use of our known value of \(a_2\text:\)

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

We an alert a pattern. Every time, us take the previous ax and include the present index. So

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

Regrouping terms, we an alert that \(a_n\) is just \(a_0\) to add the sum of the integers from \(1\) to \(n\text.\) So, since \(a_0 = 4\text,\)

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

Of course in this case we still required to know formula for the amount of \(1,\ldots,n\text.\) Let"s shot iteration v a sequence because that which telescoping doesn"t work.

Example2.4.5

Solve the recurrence relationship \(a_n = 3a_n-1 + 2\) subject to \(a_0 = 1\text.\)


Solution

Again, us iterate the recurrence relation, structure up come the index \(n\text.\)

\beginalign*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(3\cdots(3a_0 + 2) + 2) + 2)\cdots + 2)+ 2.\endalign*

It is challenging to check out what is keep going here since we have to distribute all those 3"s. Let"s shot again, this time simple a little as us go.

\beginalign*a_1 \amp = 3a_0 + 2\\a_2 \amp = 3(a_1) + 2 = 3(3a_0 + 2) + 2 = 3^2a_0 + 2\cdot 3 + 2\\a_3 \amp = 3 + 2 = 3<3^2a_0 + 2\cdot 3 + 2> + 2 = 3^3 a_0 + 2 \cdot 3^2 + 2 \cdot 3 + 2\\\vdots \amp \qquad\quad \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 + 2\cdot 3^n-1 + 2 \cdot 3^n-2 + \cdots + 2\cdot 3 + 2.\endalign*

Now us simplify. \(a_0 = 1\text,\) therefore we have actually \(3^n + \langle\textstuff\rangle\text.\) note that every the various other terms have actually a 2 in them. In fact, we have actually a geometric sum with first term \(2\) and common ratio \(3\text.\) We have actually seen how to leveling \(2 + 2\cdot 3 + 2 \cdot 3^2 + \cdots + 2\cdot 3^n-1\text.\) We get \(\frac2-2\cdot 3^n-2\) i m sorry simplifies to \(3^n - 1\text.\) placing this together with the first \(3^n\) term offers our closeup of the door formula:

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

Iteration deserve to be messy, yet when the recurrence relation only refers come one previous ax (and probably some role of \(n\)) it can work well. However, trying come iterate a recurrence relationship such together \(a_n = 2 a_n-1 + 3 a_n-2\) will be way too complicated. We would should keep monitor of 2 sets of vault terms, each of which to be expressed by two previous terms, and so on. The size of the formula would grow tremendously (double every time, in fact). Luckily over there happens to it is in a method for resolving recurrence connections which works really well ~ above relations prefer this.

SubsectionThe Characteristic source Technique

Suppose we desire to fix a recurrence relationship expressed as a mix of the two previous terms, such as \(a_n = a_n-1 + 6a_n-2\text.\) In various other words, we want to uncover a function of \(n\) which satisfies \(a_n - a_n-1 - 6a_n-2 = 0\text.\) currently iteration is too complicated, yet think just for a 2nd what would take place if us did iterate. In every step, we would, amongst other things, multiply a previous iteration by 6. For this reason our close up door formula would encompass \(6\) multiply some variety of times. For this reason it is reasonable come guess the systems will contain parts that look at geometric. Maybe the equipment will take it the form \(r^n\) for some constant \(r\text.\)

The nice thing is, we know how to examine whether a formula is in reality a solution to a recurrence relation: plug it in. What happens if we plug in \(r^n\) into the recursion above? we get

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

Now resolve for \(r\text:\)

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

so by factoring, \(r = -2\) or \(r = 3\) (or \(r = 0\text,\) although this walk not assist us). This tells us that \(a_n = (-2)^n\) is a solution to the recurrence relation, together is \(a_n = 3^n\text.\) which one is correct? castle both are, unless we specify initial conditions. Notification we could also have \(a_n = (-2)^n + 3^n\text.\) Or \(a_n = 7(-2)^n + 4\cdot 3^n\text.\) In fact, for any \(a\) and \(b\text,\) \(a_n = a(-2)^n + b 3^n\) is a systems (try plugging this right into the recurrence relation). To uncover the values of \(a\) and \(b\text,\) use the initial conditions.

This points us in the direction of a an ext general an approach for addressing recurrence relations. Notification we will always be may be to factor out the \(r^n-2\) together we did above. So us really only care about the various other part. We call this other component the characteristic equation because that the recurrence relation. We are interested in finding the root of the characteristics equation, i beg your pardon are called (surprise) the properties roots.

Characteristic Roots

provided a recurrence relationship \(a_n + \alpha a_n-1 + \beta a_n-2 = 0\text,\) the properties polynomial is

\beginequation*x^2 + \alpha x + \beta\endequation*

giving the characteristics equation:

\beginequation*x^2 + \alpha x + \beta = 0.\endequation*

If \(r_1\) and also \(r_2\) are two unique roots that the characteristic polynomial (i.e, services to the characteristic equation), climate the equipment to the recurrence relation is

\beginequation*a_n = ar_1^n + br_2^n,\endequation*

where \(a\) and \(b\) room constants determined by the early stage conditions.

Example2.4.6

Solve the recurrence relationship \(a_n = 7a_n-1 - 10 a_n-2\) through \(a_0 = 2\) and \(a_1 = 3\text.\)


Rewrite the recurrence relationship \(a_n - 7a_n-1 + 10a_n-2 = 0\text.\) Now type the characteristics equation:

\beginequation*x^2 - 7x + 10 = 0\endequation*

and settle for \(x\text:\)

\beginequation*(x - 2) (x - 5) = 0\endequation*

so \(x = 2\) and also \(x = 5\) space the properties roots. We thus know the the solution to the recurrence relationship will have actually the form

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

To uncover \(a\) and also \(b\text,\) plugin \(n =0\) and also \(n = 1\) to acquire a system of 2 equations with two unknowns:

\beginalign*2 \amp = a 2^0 + b 5^0 = a + b\\3 \amp = a 2^1 + b 5^1 = 2a + 5b\endalign*

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

\beginequation*a_n = \frac732^n - \frac13 3^n.\endequation*

Perhaps the most well known recurrence relation is \(F_n = F_n-1 + F_n-2\text,\) which in addition to the initial problems \(F_0 = 0\) and also \(F_1= 1\) specifies the Fibonacci sequence. But notification that this is specifically the type of recurrence relationship on i beg your pardon we deserve to use the characteristic root technique. As soon as you do, the only thing that alters is the the properties equation does not factor, for this reason you must use the quadratic formula to uncover the characteristics roots. In fact, law so provides the third most well known irrational number, \(\varphi\text,\) the golden ratio.

Before leaving the characteristic source technique, we have to think around what might happen once you solve the properties equation. We have actually an example over in i m sorry the characteristics polynomial has actually two unique roots. This roots can be integers, or possibly irrational number (requiring the quadratic formula to discover them). In these cases, we understand what the equipment to the recurrence relationship looks like.

However, that is possible for the characteristic polynomial come only have actually one root. This can take place if the characteristics polynomial components as \((x - r)^2\text.\) that is tho the case that \(r^n\) would be a equipment to the recurrence relation, but we won"t be able to find solutions for all initial problems using the general kind \(a_n = ar_1^n + br_2^n\text,\) because we can"t distinguish between \(r_1^n\) and \(r_2^n\text.\) We space in luck though:

Characteristic Root an approach for repeated Roots

Suppose the recurrence relationship \(a_n = \alpha a_n-1 + \beta a_n-2\) has a properties polynomial with just one root \(r\text.\) then the systems to the recurrence relationship is

\beginequation*a_n = ar^n + bnr^n\endequation*

where \(a\) and \(b\) room constants determined by the early conditions.

Notice the extra \(n\) in \(bnr^n\text.\) This permits us to resolve for the constants \(a\) and also \(b\) indigenous the early conditions.

Example2.4.7

Solve the recurrence relation \(a_n = 6a_n-1 - 9a_n-2\) with initial problems \(a_0 = 1\) and \(a_1 = 4\text.\)


The characteristics polynomial is \(x^2 - 6x + 9\text.\) We fix the properties equation

\beginequation*x^2 - 6x + 9 = 0\endequation*

by factoring:

\beginequation*(x - 3)^2 = 0\endequation*

so \(x =3\) is the only characteristic root. Because of this we know that the equipment to the recurrence relation has the form

\beginequation*a_n = a 3^n + bn3^n\endequation*

for some constants \(a\) and \(b\text.\) currently use the early conditions:

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

Since \(a = 1\text,\) we find that \(b = \frac13\text.\) as such the solution to the recurrence relationship is

\beginequation*a_n = 3^n + \frac13n3^n.\endequation*

Although we will not think about examples more complex than these, this properties root technique can be applied to much more complex recurrence relations. For example, \(a_n = 2a_n-1 + a_n-2 - 3a_n-3\) has actually characteristic polynomial \(x^3 - 2 x^2 - x + 3\text.\) Assuming you see exactly how to variable such a degree 3 (or more) polynomial you can easily find the properties roots and also as such fix the recurrence relationship (the solution would look like \(a_n = ar_1^n + br_2^n + cr_3^n\) if there to be 3 distinctive roots). The is also possible to resolve recurrence relationships of the type \(a_n = \alpha a_n-1 + \beta a_n-2 + C\) because that some consistent \(C\text.\) that is also feasible (and acceptable) because that the characteristic root to be complicated numbers.

SubsectionExercises

¶1

Find the next two terms in \((a_n)_n\ge 0\) beginning \(3, 5, 11, 21, 43, 85\ldots.\text.\) Then offer a recursive meaning for the sequence. Finally, use the characteristics root an approach to find a closeup of the door formula because that the sequence.


171 and also 341. \(a_n = a_n-1 + 2a_n-2\) through \(a_0 = 3\) and also \(a_1 = 5\text.\) closeup of the door formula: \(a_n = \frac832^n + \frac13(-1)^n\text.\) To discover this deal with the characteristics polynomial, \(x^2 - x - 2\text,\) to acquire characteristic roots \(x = 2\) and also \(x=-1\text.\) Then deal with the system

\beginalign*3 \amp = a + b\\5 \amp = 2a - b\endalign*

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

\beginalign*a_1 - a_0 \amp = 2^1\\a_2 - a_1 \amp = 2^2\\a_3 - a_2 \amp = 2^3\\\vdots\amp \vdots \\a_n - a_n-1 \amp = 2^n\endalign*

which sums to \(a_n - a_0 = 2^n+1 - 2\) (using the multiply-shift-subtract method from Section 2.2 because that the right-hand side). Substituting \(a_0 = 5\) and also solving because that \(a_n\) completes the solution.


We case \(a_n = 4^n\) works. Plug the in: \(4^n = 3(4^n-1) + 4(4^n-2)\text.\) This works - simply simplify the right-hand side.


4

Find the systems to the recurrence relation \(a_n = 3a_n-1 + 4a_n-2\) through initial state \(a_0 = 2\) and also \(a_1 = 3\text.\)


5

Find the equipment to the recurrence relation \(a_n = 3a_n-1 + 4a_n-2\) through initial state \(a_0 = 5\) and also \(a_1 = 8\text.\)

6

Solve the recurrence relationship \(a_n = 2a_n-1 - a_n-2\text.\)

What is the equipment if the early terms room \(a_0 = 1\) and also \(a_1 = 2\text?\)

What perform the initial terms must be in order for \(a_9 = 30\text?\)

For i beg your pardon \(x\) are there initial state which do \(a_9 = x\text?\)

7

Solve the recurrence relationship \(a_n = 3a_n-1 + 10a_n-2\) with initial terms \(a_0 = 4\) and \(a_1 = 1\text.\)

8

Suppose that \(r^n\) and also \(q^n\) space both services to a recurrence relation of the kind \(a_n = \alpha a_n-1 + \beta a_n-2\text.\) Prove the \(c\cdot r^n + d \cdot q^n\) is also a solution to the recurrence relation, for any kind of constants \(c, d\text.\)

9

Think ago to the miracle candy maker at your ar grocery store. Expect that the very first time a 4 minutes 1 is put into the maker 1 Skittle come out. The 2nd time, 4 Skittles, the 3rd time 16 Skittles, the 4th time 64 Skittles, etc.

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

Check your systems for the close up door formula by resolving the recurrence relation making use of the Characteristic source technique.

10

You have access to \(1 \times 1\) tiles i beg your pardon come in 2 various colors and also \(1\times 2\) tiles i beg your pardon come in 3 various colors. We desire to number out how many different \(1 \times n\) route designs we have the right to make out of these tiles.

Find a recursive meaning for the sequence \(a_n\) of courses of length \(n\text.\)

Solve the recurrence relation using the Characteristic root technique.

11

Let \(a_n\) be the variety of \(1 \times n\) brick designs you deserve to make utilizing \(1 \times 1\) squares obtainable in 4 colors and also \(1 \times 2\) dominoes accessible in 5 colors.

First, uncover a recurrence relation to explain the problem. Define why the recurrence relation is correct (in the context of the problem).

See more: Which Of The Following Statements About A Cash Dividend Are True? Select All That Apply.

Write out the first 6 regards to the sequence \(a_1, a_2, \ldots\text.\)

Solve the recurrence relation. That is, find a closed formula because that \(a_n\text.\)

12

Consider the recurrence relationship \(a_n = 4a_n-1 - 4a_n-2\text.\)

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