Skip to content

WA4. Recurrence Relations

Question 1

1. What is the production of rabbits in the nth year of a rabbit farm whose production is generated by homogeneous recurrence relation \(a_n = 11a_{n-1}-30a_{n-2}\)? Solve the recurrence relation using the method of characteristic roots, with initial production of rabbits \(a_0=0\) and \(a_1=1\)

  • According to (Levin, 2021, p.173), the plan for the solution is to find the characteristic equation, solve it for the characteristic roots, and then use the initial conditions to find the general formula for the sequence.

  • Find the characteristic equation of the recurrence relation:

\[ \begin{aligned} 11a_{n-1}-30a_{n-2} &= a_n \\ 11a_{n-1}-30a_{n-2} - a_n &= 0 \\ -11a_{n-1}+30a_{n-2} + a_n &= 0 \\ a &= -11 \\ b &= 30 \\ \end{aligned} \]
  • The characteristic equation is \(r^2-11r+30=0\), we solve it for the characteristic roots:
\[ \begin{aligned} r^2-11r+30 &= 0 \\ (r-6)(r-5) &= 0 \\ r1 &= 5 \\ r2 &= 6 \\ \end{aligned} \]
  • Let’s put the roots into the equation and find the constants from the initial conditions:
  • We got the general formula \(a_n = c_1(5)^n + c_2(6)^n\), let’s find \(c_1\) and \(c_2\) using the initial conditions.
  • we start by substituting \(n=0\) and \(n=1\) in the general formula and then solve the system of equations.
\[ \begin{aligned} a_0 &= c_1(5)^0 + c_2(6)^0 \\ &= c_1 + c_2 = 0 \text{ \_\_\_\_(1)} \\ a_1 &= c_1(5)^1 + c_2(6)^1 \\ &= 5c_1 + 6c_2 = 1 \\ &= 5c_1 + 6c_2 - 1 = 0 \text{ \_\_\_\_\_(2)} \\ \end{aligned} \]
  • Let’s solve the system of equations (1) and (2) to find \(c_1\) and \(c_2\) we find the \(c_1=-1\) and \(c_2=1\).
  • The final solution then would be:
\[ \begin{aligned} a_n &= -1(5)^n + 1(6)^n \\ &= -5^n + 6^n \\ \end{aligned} \]

Question 2

2. Solve the below non-homogeneous recurrence relation using the iteration method: \(a_n = a_{n-1}+2, n \geq 1, a_0=2\)

  • According to (LRvin, 2021, p.170), the plan is to find the first few terms of the sequence and then look for a pattern. The pattern will be used to guess a formula for the sequence. The guess will be verified by induction.

  • Let’s find the first few terms of the pattern:

\[ \begin{aligned} a_0 &= 2 \\ a_1 &= a_0 + 2 \\ a_2 &= a_1 + 2 = a_0 + 2 + 2 \\ a_3 &= a_2 + 2 = a_0 + 2 + 2 + 2 \\ a_4 &= a_3 + 2 = a_0 + 2 + 2 + 2 + 2 \\ a_5 &= a_4 + 2 = a_0 + 2 + 2 + 2 + 2 + 2 \\ ... \\ ... \\ a_n &= a_{n-1} + 2 = a_0 + 2 + 2 + 2 + 2 + 2 + ... + 2 \\ &= a_0 + 2n \\ &= 2 + 2n \end{aligned} \]
  • Let’s verify the solution by induction:
  • The Base case: \(n=0\): \(a_0 = 2 + 2(0) = 2\).
  • Assume that the formula is true for \(n=k\), that is \(a_k = 2 + 2k\), let’s prove that it is true for \(n=k+1\):
\[ \begin{aligned} a_{k+1} &= a_k + 2 \\ &= 2 + 2k + 2 \\ &= 2 + 2(k+1) \\ &= 2 + 2n \\ \end{aligned} \]

Question 3

3. Show that \(a_n =4^n\) is a solution of the recurrence relation obtained to produce the cars manufactured by a company in the nth month of the year \(a_n = 8a_{n-1}-16a_{n-2}\)

  • According to (Levin, 2021, p.360), the plan is to start from the left-hand side of the equation assuming that \(a_n = 4^n\) and then simplify the equation until we reach the right-hand side of the equation.
\[ \begin{aligned} 4^n &= 8a_{n-1}-16a_{n-2} \\ &= 8(4^{n-1})-16(4^{n-2}) \\ &= 4^{n-2}(8(4)-16) \\ &= 4^{n-2}(32-16) \\ &= 4^{n-2}(16) \\ &= 4^{n-2}(4^2) \\ &= 4^{n-2+2} \\ &= 4^n \end{aligned} \]
  • As we see, we actually reached the left-hand side of the equation, so we proved that \(a_n = 4^n\) is a solution of the recurrence relation.
  • The trick in the previous solution was to take the \(4^{n-2}\) out of the equation and then simplify the rest of the equation.

References

  • Doerr, A., & Levasseur, K. (2022). Applied discrete structures (3rd ed.). licensed under CC BY-NC-SA. https://discretemath.org/ads/chapter_7.html. Chapter 8: Recursion and Recurrence Relations.
  • Levin, O. (2021). Discrete mathematics: An open introduction (3rd ed.). licensed under CC 4.0. Chapter 2: Sequences.