Applications of Recurrence Relations
In our previous chapter we went through solutions to first order linear recurrence relations with constant coefficients of the form $t_n=r\times t_{n-1}+d$tn=r×tn−1+d.
To solve a recurrence relations means to find its explicit equation. Here is the table we came up with for recurrence relations and their explicit equations where the first term is $t_0=a$t0=a.
| Recurrence Relation | Explicit Equation | |
| Arithmetic Recurrence Relation | $t_n=t_{n-1}+d$tn=tn−1+d | $t_n=a+d(n-1)$tn=a+d(n−1) |
| Geometric Recurrence Relation | $t_n=r\times t_{n-1}$tn=r×tn−1 | $t_n=ar^{n-1}$tn=arn−1 |
| First Order Linear (Constant Coefficients) | $t_n=r\times t_{n-1}+d$tn=r×tn−1+d | $t_n=\left(ar^{n-1}\right)+\left[\frac{d\left(r^{n-1}-1\right)}{r-1}\right]$tn=(arn−1)+[d(rn−1−1)r−1] |
Now it's time to apply these ideas to further scenarios in the real world.
Patterns occur everywhere that can be described by recurrence relations. The most common types of recurrence relations seen in the real world are arithmetic and geometric series.
Whenever you see a pattern that keeps adding or subtracting the same quantity, it will have an arithmetic recurrence relations.
Whenever you see a pattern that keeps growing or shrinking by the same proportion, it will have a geometric recurrence relation.
Worked Examples
Question 1
When gravity can no longer overcome air resistance, an object falling to earth reaches terminal velocity. For a skydiver with their parachute closed, the terminal velocity is about $56$56 m/s.
Emilio is a professional skydiver. On a particular skydive, he reaches terminal velocity $3$3 km above the earth.
a) How high will Emilio be above the earth after $14$14 seconds?
b) Write a recurrence relation for $h_n$hn, Emilio's height $n$n seconds after he reaches terminal velocity.
c) Solve the recurrence relation to find the explicit equation for $h_n$hn.
d) To safely land, Emilio must release his parachute no lower than $700$700 m off the ground. What is the latest possible whole number of seconds $n$n when Emilio could do this?
Solution
a) Emilio is falling $56$56 metres every second, so after $14$14 seconds he will have fallen $14\times56=784$14×56=784 metres. In other words, he has fallen $784$784 m below his starting height of $3$3 km.
This positions him $3000-784=2216$3000−784=2216 m above the earth, or $2.216$2.216 km.
b) Notice that the pattern here involves continually subtracting $56$56 m from Emilio's height. This means we can describe the pattern by an arithmetic recurrence relation.
Emilio's height $h_n$hn is always $56$56 m below his height $h_{n-1}$hn−1 from one second ago. Therefore, we have the following arithmetic recurrence relation.
$h_n=h_{n-1}-56$hn=hn−1−56
c) Remember that for arithmetic recurrence relations of the form $t_n=t_{n-1}+d$tn=tn−1+d the explicit equation will be $t_n=a+d\left(n-1\right)$tn=a+d(n−1).
Because Emilio reaches terminal velocity at a height of $3$3 km, the first term of the series is his height after $1$1 second. We calculate this in metres as $h_1=3000-56=2944$h1=3000−56=2944. Our difference $d$d is $-56$−56. Hence, our explicit equation for $h_n=h_{n-1}-56$hn=hn−1−56 will be $h_n=2944+\left(-56\right)\left(n-1\right)$hn=2944+(−56)(n−1) which we can simplify to:
$h_n=2944-56\left(n-1\right)$hn=2944−56(n−1)
d) Given the explicit equation we have just found, we want to find the value of $n$n at $h_n=700$hn=700. We don't expect this to be an exact whole number, but it will tell us between what two whole values of $n$n Emilio reaches this height.
So, let's set $h_n=700$hn=700 and solve for $n$n.
| $700$700 | $=$= | $2944-56\left(n-1\right)$2944−56(n−1) |
| $56\left(n-1\right)$56(n−1) | $=$= | $2944-700$2944−700 |
| $56\left(n-1\right)$56(n−1) | $=$= | $2244$2244 |
| $n-1$n−1 | $=$= | $\frac{2244}{56}$224456 |
| $n-1$n−1 | $=$= | $\frac{561}{14}$56114 |
| $n$n | $=$= | $\frac{561}{14}+1$56114+1 |
| $n$n | $=$= | $41.07$41.07 to 2 d.p. |
This tells us that at $h_n=700$hn=700, between $41$41 and $42$42 seconds have passed. At $41$41 seconds, Emilio can still safely deploy his parachute. At $42$42 seconds, it will be too late.
Therefore, Emilio should deploy his parachute at $n=41$n=41 seconds.
Question 2
Many horror stories involve zombie outbreaks. Suppose a zombie outbreak were to occur on Planet Earth. $13$13 zombies are unleashed and when they bite humans, the humans immediately turn into zombies. The zombie population triples every hour.
a) What will the zombie population be after $5$5 hours?
b) Write a recurrence relation for $Z_n$Zn, the zombie population $n$n hours after the outbreak.
c) Solve to find the explicit equation for $Z_n$Zn.
d) If the $13$13 zombies are unleashed at midnight, and the earth's population is $7.5$7.5 billion, what hour is it right after the earth's population has been wiped out?
Solution
a) We start with $13$13 zombies, and after one hour this has tripled to $13\times3=39$13×3=39 zombies. So, after $5$5 hours the population will have tripled five times, giving a zombie population of $13\times3\times3\times3\times3\times3=3159$13×3×3×3×3×3=3159.
b) The zombie population is continually growing by the same proportion, and so we can describe it by a geometric recurrence relation.
Since, the zombie population is just three times the population one hour ago, we have the following relation:
$Z_n=3\times Z_{n-1}$Zn=3×Zn−1
c) Recall that for a geometric recurrence relation $t_n=r\times t_{n-1}$tn=r×tn−1 the explicit equation is $t_n=ar^{n-1}$tn=arn−1 where $a$a is the first term.
At $n=1$n=1, after one hour, the zombie population has tripled to $39$39, and this is our first term $Z_1$Z1. The rate $r$r is $3$3, since the population is tripling. Therefore, we get the following explicit equation.
$Z_n=39\times3^{n-1}$Zn=39×3n−1
d) We want to find the value of $n$n at $Z_n=7500000000$Zn=7500000000. We substitute this value into our explicit equation and solve for $n$n.
| $7500000000$7500000000 | $=$= | $39\times3^{n-1}$39×3n−1 |
| $3^{n-1}$3n−1 | $=$= | $\frac{7500000000}{39}$750000000039 |
To make $n-1$n−1 the subject, we will have to use logarithms. We apply the logarithm, base $3$3, to both sides.
| $\log_33^{n-1}$log33n−1 | $=$= | $\log_3\frac{7500000000}{39}$log3750000000039 |
And if we recall our log laws that states that $\log_bb^n=n$logbbn=n, we get:
| $n-1$n−1 | $=$= | $\log_3\frac{7500000000}{39}$log3750000000039 |
| $n$n | $=$= | $\log_3\frac{7500000000}{39}+1$log3750000000039+1 |
| $n$n | $=$= | $18.36$18.36 to 2 d.p. |
In other words, after $18$18 hours, the world population will be on the brink of extinction, and after $19$19 hours, it will be totally wiped out.
$12$12 hours after midnight is midday, and $19$19 hours after midnight is $7$7 p.m.
If you are unfamiliar with logarithms, you could have guessed and checked certain values in your calculator to find the amount of hours it took for this to happen.
This kind of example shows how quickly geometric progressions can escalate. It takes the zombie population less than $24$24 hours to wipe out the human population of earth!
Further Examples
Question 3
For a photo, the staff at a company have been arranged such that there are $9$9 people in the front row and each row has $2$2 more people than in the row in front of it.
Write a recursive rule for $a_n$an, the number of people in the $n$nth row, in terms of $a_{n-1}$an−1 and an initial condition for $a_1$a1.
Write both parts on the same line separated by a comma.
Write a formula for $a_n$an in terms of $n$n.
How many people are in the $10$10th row?
Question 4
A basketball is dropped onto the ground from a height of $15$15 feet.
On each bounce, the ball reaches a maximum height of $55%$55% of its previous maximum height.
Write a recursive rule for $a_n$an, the height of the ball on the nth bounce, in terms of $a_{n-1}$an−1 and an initial condition $a_0$a0.
Write both parts on the same line separated by a comma.
Write a formula for $a_n$an, for the height reached on the $n$nth bounce in terms of $n$n.
How high does the basketball reach after the $5$5th bounce?
Give your answer to two decimal places.