Skip to main content
Mathematics LibreTexts

5.1: Recurrance Relations

  • Page ID
  • \( \newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } \) \( \newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}} \)\(\newcommand{\id}{\mathrm{id}}\) \( \newcommand{\Span}{\mathrm{span}}\) \( \newcommand{\kernel}{\mathrm{null}\,}\) \( \newcommand{\range}{\mathrm{range}\,}\) \( \newcommand{\RealPart}{\mathrm{Re}}\) \( \newcommand{\ImaginaryPart}{\mathrm{Im}}\) \( \newcommand{\Argument}{\mathrm{Arg}}\) \( \newcommand{\norm}[1]{\| #1 \|}\) \( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\) \( \newcommand{\Span}{\mathrm{span}}\) \(\newcommand{\id}{\mathrm{id}}\) \( \newcommand{\Span}{\mathrm{span}}\) \( \newcommand{\kernel}{\mathrm{null}\,}\) \( \newcommand{\range}{\mathrm{range}\,}\) \( \newcommand{\RealPart}{\mathrm{Re}}\) \( \newcommand{\ImaginaryPart}{\mathrm{Im}}\) \( \newcommand{\Argument}{\mathrm{Arg}}\) \( \newcommand{\norm}[1]{\| #1 \|}\) \( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\) \( \newcommand{\Span}{\mathrm{span}}\)\(\newcommand{\AA}{\unicode[.8,0]{x212B}}\)

    As we’ll see in the next section, a differential equation looks like this: \(\frac{dP}{dt} = 0.03 \cdot P\). What I want to first talk about though are recurrence relations. Let me introduce these with a magic trick.

    Magic Trick

    Pick a number between 1 and 100, and I’m going to guess it. But not before we mix it up a bit.

    1. Take your number and divide by five, and round to the nearest whole number.
    2. Then add \(36\) to the result.
    3. Repeat steps (1) and (2) twice more, for a total of three iterations.

    Done? I bet you ended with the number 45. Are you amazed?

    This trick is based off the recurrence relation \(f_{t+1} = \frac{1}{5} f_t + 36\). Think of \(f_t\) as the previous value, and \(f_{t+1}\) as the new value. How do you get from one to another? Well, ignoring the rounding, you divide by \(5\) and add \(36\), and that’s exactly what \(f_{t+1} = \frac{1}{5} f_t + 36\) is telling you to do. In order to use such a equation, we need an initial value or \(f_0\). In the trick, this was the original number you picked. Let’s create a graph with the initial value \(f_0 = 100\):


    As you can see, this recurrence relation quickly converges to \(f_t = 45\) by the time \(t = 3\). That’s why the trick works! If we started somewhere else, the graph looks much the same and it converges to 45 anyway.

    However, recurrence relations are useful for more than just magic tricks.


    Let \(h_t\) be the biomass of a forest in year \(t\). Suppose it expands by \(1\%\) each year, but also loses \(2000\) metric tonnes to logging. What might be a recurrence relation that explains this situation?

    Well, since this is a recurrence relation, we want to relate the quantity under consideration, \(h_t\) to its value the next year, which is \(h_{t+1}\). So it will look something like

    \(h_{t+1} = 1.5 h_t + 16\)

    but those aren’t the right values yet — just want to have some idea of where this is going.

    The first thing we need to encode is the expansion by \(1\%\). We can take \(1\%\), or \(0.01\) and multiply by \(h_t\) like so: \(0.01 h_t\). But the old forest is still there (except for the logging, which we’ll worry about in a second), so let’s add \(h_t\) as well: \(0.01 h_t + h_t\). If we factor out \(h_t\), we get

    \[\begin{align*} 0.01 h_t + h_t & = h_t(0.01 + 1) \\ & = h_t(1.01) \\ & = 1.01 h_t \end{align*}\]

    This is the growth by \(1\%\). What about that logging? Well, that’s not a percent change, so we’ll just subtract the \(2000\) to represent the loss of biomass. So our final recurrence relation is–>

    \(h_{t+1} = 1.01 h_t - 2000\)

    What happens to the forest in the long run according to your recurrence relation?

    Well, let’s play with it a bit and see what happens. But before we can do that, we need an initial value \(h_0\). Let’s guess something. Since we are losing \(2000\) a year, we’ll need a much bigger number than \(2000\). Let’s just guess that \(h_0\) is \(50,\!000\) metric tonnes.
    Now we can compute several \(h_t\) values:

    \[\begin{align*} h_0 & = 50000 \\ h_1 & = 1.01(50000)-2000 = 48500 \\ h_2 & = 1.01(48500) - 2000 = 46985 \\ h_3 & = 1.01(46985) - 2000 \approx 45500 \\ \end{align*}\]

    We can see that the biomass is going down — not a good sign for the forest. We can speed these calculations up quite a bit in excel. If you do that, you can see that the forest will be totally gone in by \(h_{29}\), in less than thirty years. However, that’s not a full answer, since it may depend on how much biomass we start with. Suppose it’s a larger forest with \(h_0 = 300,\!000\). Then we see

    \[\begin{align*} h_0 & = 300000 \\ h_1 & = 1.01(300000)-2000 = 301000 \\ h_2 & = 1.01(301000) - 2000 = 302010 \\ h_3 & = 1.01(302010) - 2000 \approx 303000 \\ \end{align*}\]

    And the forest just grows from there.

    Let’s see an even more complicated example.

    Life Cycle of Cutthroat Trout

    Recurrence relations can model the life of plant and animals species as they move from one stage of life to the next. For example, let \(f^0_t\), \(f^1_t\), \(f^2_t\), \(f^3_t\), \(f^4_t\), \(f^{5+}_t\) be the amount of cutthroat trout (oncorhynchus clarkii) in southwest Montana of age \(0\), \(1\), \(2\), \(3\), \(4\), and \(5\) or more respectively. Here, \(t\) is a measured in years starting from some \(t = 0\). Then according to, these quantities follow the recurrence relation

    \[\begin{align*} f^0_{t+1} & = 5.23 f^3_t + 18.0 f^4_t + 24.55 f^{5+}_t \\ f^1_{t+1} & = 0.277 f^0_t \\ f^2_{t+1} & = 0.3405 f^1_t \\ f^3_{t+1} & = 0.4675 f^2_t \\ f^4_{t+1} & = 0.4675 f^3_t \\ f^{5+}_{t+1} & = 0.4675 f^4_t + 0.4675 f^{5+}_t \\ \end{align*}\]

    Explain what each number in these recurrence relations mean.

    My goodness, that’s a complicated mess of symbols. But with a little patience, we can figure it out I think.

    Let’s start with the line \(f^1_{t+1} = 0.277 f^0_t\). We know from the problem statement that \(f^0_t\) are the trout of age 0 at year \(t\). The quantity \(f^1_{t+1}\) is the amount of one year old trout at year \(t+1\). This equation is relating the number of \(0\) year olds with the number of \(1\) year olds a year later. What it is saying is \(0.277\) times the number of zero year olds gives you the number of one year olds a year later. In other words, this equation is giving a \(27.7\%\) survival rate from age zero to age one.
    From here, we can now easily decode several other equations. \(f^2_{t+1} = 0.3405 f^1_t\) gives a \(34.05\%\) survival rate from age one to age two. The similar we find \(46.75\%\) survival rate from age two to age three, and the same rate from age three to age four. The equation \(f^{5+}_{t+1} = 0.4675 f^4_t + 0.4675 f^{5+}_t\) is a bit more complicated, since trout of age 5+ come from the age 4 trout, but also the age 5+ stay within that category, so there are two ways to get there. Both of these involve a \(46.75\%\) survival rate.
    Notice these survival rates are pretty low by human standards. However, there is some good news for the species: look at the first equation \(f^0_{t+1} = 5.23 f^3_t + 18.0 f^4_t + 24.55 f^{5+}_t\). What do you make of this? That’s right — these are the new baby trout! As you can see, there are a lot of new babies that help balance the low survival rates we noticed before. In particular, each three year old produces roughly 5 new offspring, each four year old produces on average 18 new offspring, and an average 5+ year old produces almost 25 offspring.

    Starting with \(f^0_0 = 1500\), \(f^1_0 = 375\), \(f^2_0 = 125\), \(f^3_0 = 65\), \(f^4_0 = 30\), and \(f^{5+}_0 = 50\), create a graph that shows how the population of the cutthroat trout changes over time. What does the graph show?

    I created this graph in Excel (see the file “cutthroat-life-cycle.xlsx” for the formulas and data):


    And here are just the last four stages to get a better look at these ones:


    As we can see, the population seems to be fairly stable. One thing that stands out to me is how many age zero and age one fish there are compared to other groups.

    This page titled 5.1: Recurrance Relations is shared under a CC BY 4.0 license and was authored, remixed, and/or curated by Tyler Seacrest via source content that was edited to the style and standards of the LibreTexts platform; a detailed edit history is available upon request.