# 5.1: Recurrance Relations

- Page ID
- 88665

\( \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}}\)

\( \newcommand{\vectorA}[1]{\vec{#1}} % arrow\)

\( \newcommand{\vectorAt}[1]{\vec{\text{#1}}} % arrow\)

\( \newcommand{\vectorB}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } \)

\( \newcommand{\vectorC}[1]{\textbf{#1}} \)

\( \newcommand{\vectorD}[1]{\overrightarrow{#1}} \)

\( \newcommand{\vectorDt}[1]{\overrightarrow{\text{#1}}} \)

\( \newcommand{\vectE}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash{\mathbf {#1}}}} \)

\( \newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } \)

\( \newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}} \)

\(\newcommand{\avec}{\mathbf a}\) \(\newcommand{\bvec}{\mathbf b}\) \(\newcommand{\cvec}{\mathbf c}\) \(\newcommand{\dvec}{\mathbf d}\) \(\newcommand{\dtil}{\widetilde{\mathbf d}}\) \(\newcommand{\evec}{\mathbf e}\) \(\newcommand{\fvec}{\mathbf f}\) \(\newcommand{\nvec}{\mathbf n}\) \(\newcommand{\pvec}{\mathbf p}\) \(\newcommand{\qvec}{\mathbf q}\) \(\newcommand{\svec}{\mathbf s}\) \(\newcommand{\tvec}{\mathbf t}\) \(\newcommand{\uvec}{\mathbf u}\) \(\newcommand{\vvec}{\mathbf v}\) \(\newcommand{\wvec}{\mathbf w}\) \(\newcommand{\xvec}{\mathbf x}\) \(\newcommand{\yvec}{\mathbf y}\) \(\newcommand{\zvec}{\mathbf z}\) \(\newcommand{\rvec}{\mathbf r}\) \(\newcommand{\mvec}{\mathbf m}\) \(\newcommand{\zerovec}{\mathbf 0}\) \(\newcommand{\onevec}{\mathbf 1}\) \(\newcommand{\real}{\mathbb R}\) \(\newcommand{\twovec}[2]{\left[\begin{array}{r}#1 \\ #2 \end{array}\right]}\) \(\newcommand{\ctwovec}[2]{\left[\begin{array}{c}#1 \\ #2 \end{array}\right]}\) \(\newcommand{\threevec}[3]{\left[\begin{array}{r}#1 \\ #2 \\ #3 \end{array}\right]}\) \(\newcommand{\cthreevec}[3]{\left[\begin{array}{c}#1 \\ #2 \\ #3 \end{array}\right]}\) \(\newcommand{\fourvec}[4]{\left[\begin{array}{r}#1 \\ #2 \\ #3 \\ #4 \end{array}\right]}\) \(\newcommand{\cfourvec}[4]{\left[\begin{array}{c}#1 \\ #2 \\ #3 \\ #4 \end{array}\right]}\) \(\newcommand{\fivevec}[5]{\left[\begin{array}{r}#1 \\ #2 \\ #3 \\ #4 \\ #5 \\ \end{array}\right]}\) \(\newcommand{\cfivevec}[5]{\left[\begin{array}{c}#1 \\ #2 \\ #3 \\ #4 \\ #5 \\ \end{array}\right]}\) \(\newcommand{\mattwo}[4]{\left[\begin{array}{rr}#1 \amp #2 \\ #3 \amp #4 \\ \end{array}\right]}\) \(\newcommand{\laspan}[1]{\text{Span}\{#1\}}\) \(\newcommand{\bcal}{\cal B}\) \(\newcommand{\ccal}{\cal C}\) \(\newcommand{\scal}{\cal S}\) \(\newcommand{\wcal}{\cal W}\) \(\newcommand{\ecal}{\cal E}\) \(\newcommand{\coords}[2]{\left\{#1\right\}_{#2}}\) \(\newcommand{\gray}[1]{\color{gray}{#1}}\) \(\newcommand{\lgray}[1]{\color{lightgray}{#1}}\) \(\newcommand{\rank}{\operatorname{rank}}\) \(\newcommand{\row}{\text{Row}}\) \(\newcommand{\col}{\text{Col}}\) \(\renewcommand{\row}{\text{Row}}\) \(\newcommand{\nul}{\text{Nul}}\) \(\newcommand{\var}{\text{Var}}\) \(\newcommand{\corr}{\text{corr}}\) \(\newcommand{\len}[1]{\left|#1\right|}\) \(\newcommand{\bbar}{\overline{\bvec}}\) \(\newcommand{\bhat}{\widehat{\bvec}}\) \(\newcommand{\bperp}{\bvec^\perp}\) \(\newcommand{\xhat}{\widehat{\xvec}}\) \(\newcommand{\vhat}{\widehat{\vvec}}\) \(\newcommand{\uhat}{\widehat{\uvec}}\) \(\newcommand{\what}{\widehat{\wvec}}\) \(\newcommand{\Sighat}{\widehat{\Sigma}}\) \(\newcommand{\lt}{<}\) \(\newcommand{\gt}{>}\) \(\newcommand{\amp}{&}\) \(\definecolor{fillinmathshade}{gray}{0.9}\)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.

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

- Take your number and divide by five, and round to the nearest whole number.
- Then add \(36\) to the result.
- 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.

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\)

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.

\[\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.

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.