Question

Suppose that there are two goats on an island initially. The number of goats on the island doubles every year by natural reproduction, and some goats are either added or removed each year.

a) Construct a recurrence relation for the number of goats on the island at the start of the \(n\)th year, assuming that during each year an extra \(100\) goats are put on the island.

b) Solve the recurrence relation from part (a) to find the number of goats on the island at the start of the \(n\)th year.

c) Construct a recurrence relation for the number of goats on the island at the start of the \(n\)th year, assuming that \(n\) goats are removed during the \(n\)th year for cach \(n \ge 3\).

d) Solve the recurrence relation in part (c) for the number of goats on the island at the start of the \(n\)th year.

Short answer

(a) \({a_n} = 2{a_{n - 1}} + 100,{a_1} = 2\)

(b) \({a_n} = 51 \cdot {2^n} - 100\)

(c)\({a_n} = 2{a_{n - 1}} - nn \ge 2,{a_1} = 2,{a_2} = 4\)

(d) \({a_n} = \left\{ {\begin{array}{*{20}{c}}{1,}&{{\rm{ if }}n = 1}\\{n + 2,}&{{\rm{ if }}n > 1}\end{array}} \right.\)

Step-by-step solution

Linear Homogeneous Recurrence Relations with Constant Coefficients definition

Let\({c_1}\)and\({c_2}\)be real numbers. Suppose that\({r^2} - {c_1}r - {c_2} = 0\)has two distinct roots\({r_1}\)and\({r_2}\). Then the sequence\(\left\{ {{a_n}} \right\}\)is a solution of the recurrence relation\({a_n} = {c_1}{a_{n - 1}} + {c_2}{a_{n - 2}}\)if and only if\({a_n} = {\alpha _1}r_1^n + {\alpha _2}r_2^n\)for\(n = 0,1,2, \ldots \), where\({\alpha _1}\)and\({\alpha _2}\)are constants.

Use Recurrence Relations for part (a)

(a) Let\({a_n}\)represent the number of goats on the island at the start of the\(n\)th year.

\(2{a_{n - 1}}\)

Second case An extra 100 goats are put on the island each year.

100

Add all number of pairs for each case:

\({a_n} = 2{a_{n - 1}} + 100\)

Initial conditions

At the beginning of the first year, there are 2 goats.

\({a_1} = 2\)

Since no goats are removed during the second year either, the number of goats only doubles:

\({a_2} = 2{a_1} = 2(2) = 4\)

Use Recurrence Relations for part (b)

(b) Roots Characteristic equation

Let \({a_n} = r\) and \({a_{n - 1}} = 1\) (other functions of\(n\) are considered to be 0 )

\(r = 2\)

Solution homogeneous linear recurrence relation

The solution of the recurrence relation is then of the form \({a_n} = {\alpha _1}r_1^n + {\alpha _2}nr_1^n + \ldots + {\alpha _k}{n^{k - 1}}r_1^n\) with\({r_1}\) a root with multiplicity \(k\) of the characteristic equation.

\(a_n^{(h)} = \alpha \cdot {2^n}\)

Thus the solution of the homogeneous recurrence relation is \(a_n^{(h)} = \alpha \cdot {2^n}\)

Particular Solution

\(F(n) = 100 = 100 \cdot {1^n}\)

If \(F(n) = \left( {{b_t}{n^t} + {b_{t - 1}}{n^{t - 1}} + \ldots + {b_1}n + {b_0}} \right){s^n}\) and \(s\) is not \({\bf{a}}\) root of the characteristic equation, then \(\left( {{p_t}{n^t} + {p_{t - 1}}{n^{t - 1}} + \ldots + {p_1}n + {p_0}} \right){s^n}\) is the particular solution.

If \(F(n) = \left( {{b_t}{n^t} + {b_{t - 1}}{n^{t - 1}} + \ldots + {b_1}n + {b_0}} \right){s^n}\) and \(s\) is \({\bf{a}}\) root of the characteristic equation with multiplicity \(m\), then \({n^m}\left( {{p_t}{n^t} + {p_{t - 1}}{n^{t - 1}} + \ldots + {p_1}n + {p_0}} \right){s^n}\) is the particular solution.

1 is not a root of the characteristic equation:

\(a_n^{(p)} = {p_0} \cdot {1^n} = {p_0}\)

The particular solution needs to satisfy the recurrence relation:

\({a_n}{\rm{ }} = 2{a_{n - 1}} + 100{p_0}{\rm{ }} = 2{p_0} + 100 - {p_0} = 100{p_0} = - 100\)

The particular solution then becomes:

\(a_n^{(p)} = {p_0} = - 100\)

Use Recurrence Relations for part (c)

The solution of the nonhomogeneous linear recurrence relation is the sum of the homogeneous\(a_n^{(h)}\)and particular solution\(a_n^{(p)}\)

\({a_n} = a_n^{(h)} + a_n^{(p)} = \alpha \cdot {2^n} - 100\)

Evaluate\({a_n} = \alpha \cdot {2^n} - 100\)at\(n = 1\) :

\(2 = {a_1}{\rm{ }} = 2\alpha - 100{\rm{ }}102{\rm{ }} = 2\alpha {\rm{ Add }}100{\rm{ to each side }}51{\rm{ }} = \alpha {\rm{ Divide each side by }}2\)

The solution of the nonhomogeneous linear recurrence relation then becomes:

\({a_n} = \alpha \cdot {2^n} - 100 = 51 \cdot {2^n} - 100\)

Let\({a_n}\)represent the number of goats on the island at the start of the\(n\)th year.

\(2{a_{n - 1}}\)

Second case\(n\)goats are removed during the\(n\)th year:

\( - n\)

Add all number of pairs for each case:

\({a_n} = 2{a_{n - 1}} - n{\rm{ when }}n \ge 3{a_n} = 2{a_{n - 1}} - n{\rm{ when }}n \ge 3\)

Initial conditions

At the beginning of the first year, there are 2 goats.

\({a_1} = 2\)

After one month, no goats are removed and thus the number of goats are simply doubled.

\({a_2} = 2{a_1} = 2 \cdot 2 = 4\)

Use Recurrence Relations for part (d)

(d) Let\({a_n} = r\)and\({a_{n - 1}} = 1\)(other functions of\(n\)are considered to be 0 )

\(r = 2\)

Solution homogeneous linear recurrence relation

The solution of the recurrence relation is then of the form\({a_n} = {\alpha _1}r_1^n + {\alpha _2}nr_1^n + \ldots + {\alpha _k}{n^{k - 1}}r_1^n\)with\({r_1}\)a root with multiplicity\(k\)of the characteristic equation.

\(a_n^{(h)} = \alpha \cdot {2^n}\)

Thus the solution of the homogeneous recurrence relation is\({x^5}{y^8}a_n^{(h)} = \alpha \cdot {2^n}\)

Particular Solution

\(F(n) = n = n \cdot {1^n}\)

If\(F(n) = \left( {{b_t}{n^t} + {b_{t - 1}}{n^{t - 1}} + \ldots + {b_1}n + {b_0}} \right){s^n}\)and\(s\)is not a root of the characteristic equation, then\(\left( {{p_t}{n^t} + {p_{t - 1}}{n^{t - 1}} + \ldots + {p_1}n + {p_0}} \right){s^n}\) is the particular solution.

If\(F(n) = \left( {{b_t}{n^t} + {b_{t - 1}}{n^{t - 1}} + \ldots + {b_1}n + {b_0}} \right){s^n}\)and\(s\)is\({\bf{a}}\)root of the characteristic equation with multiplicity\({m_{{\rm{, then }}}}{n^m}\left( {{p_t}{n^t} + {p_{t - 1}}{n^{t - 1}} + \ldots + {p_1}n + {p_0}} \right){s^n}\)is the particular solution.

1 is not a root of the characteristic equation:\(a_n^{(p)} = \left( {{p_1}n + {p_0}} \right) \cdot {1^n} = {p_1}n + {p_0}\).

The particular solution needs to satisfy the recurrence relation:

\(\begin{array}{l}{a_n} = 2{a_{n - 1}} - n{p_1}n + {p_0}\\{a_n} = 2{p_1}(n - 1) + 2{p_0} - n{p_1}n + {p_0}\\{a_n} = \left( {2{p_1} - 1} \right)n + \left( { - 2{p_1} + 2{p_0}} \right)0\\{a_n} = \left( {{p_1} - 1} \right)n + \left( { - 2{p_1} + {p_0}} \right){\rm{ }}\end{array}\)

All Coefficients have to be equal to:\(0{p_1} - 1 = 0 - 2{p_1} + {p_0} = 0{\rm{ }}\)

Solve the equations\({p_1} = 1{p_0} = 2{p_1} = 2(1) = 2\)

The particular solution then becomes:

\(a_n^{(p)} = {p_1}n + {p_0} = n + 2\)

Solution nonhomogeneous linear recurrence relation

The solution of the nonhomogeneous linear recurrence relation is the sum of the homogeneous\(a_n^{(h)}\)and particular solution\(a_n^{(p)}\)

\({a_n} = a_n^{(h)} + a_n^{(p)} = \alpha \cdot {2^n} + n + 2\)

Evaluate\({a_n} = \alpha \cdot {2^n} + n + 2\)at\(n = 2\)

\(4 = {a_2} = {2^2}\alpha + 2 + 24 = {a_2} = 4\alpha + 4\)

Combine like terms\(0 = 4\alpha {\rm{ }}\)

Subtract from to each side\(0 = \alpha \)

Divide\(3\)each side by\(2\)

The solution of the nonhomogeneous linear recurrence relation then becomes.

\({a_n} = \alpha \cdot {2^n} + n + 2 = 0 \cdot {2^n} + n + 2 = n + 2n \ge 2\)

Note that this solution only holds when\(n \ge 2\) as we used\(n = 2\)as initial condition. We then need to add that the solution is 2 when\(n = 1\).

\({a_n} = \left\{ {\begin{array}{*{20}{c}}{1,}&{{\rm{ if }}n = 1}\\{n + 2,}&{{\rm{ if }}n > 1}\end{array}} \right.\)