Maths Recurrence Relations

Recurrence Relations Overview

• A recurrence relation is a formula that defines each term of a sequence based on its previous terms.

Basic Structure

• Given starting value, the formula is typically written as:
  $u<em>{n+1} = f(u</em>n)$
• Where:
  • $u_n$ is the current term
  • $u_{n+1}$ is the next term
  • $f$ is a function that relates $u<em>n$ to $u</em>{n+1}$

Examples of Simple Recurrence Relations

• Consider a simple case where
  • If the starting value $u<em>0 = 2$: $u</em>{1} = 2 imes 2 + 3$
  • Calculation:
    • $2 imes 2 = 4$
    • $4 + 3 = 7$
  • Therefore, $u_1 = 7$
• For the next term using the earlier result:
  • $u<em>{2} = 2 imes u</em>{1} + 3 = 2 imes 7 + 3 = 14 + 3 = 17$

Properties of Recurrence Relations

• Recurrence relations can lead to:
  • Values that continually increase (e.g., doubling and adding a constant).
  • Values that stabilize or approach a limit (e.g., limits exist when certain conditions apply).

Conditions for Stability and Limits

1. If the multiplier (constant before $u_n$) is between -1 and 1, the sequence approaches a limit.
   • Example: If $a$ (multiplier of $u_n$) is $0.5$, then as $n$ approaches infinity, the sequence approaches a value.
2. If the multiplier is greater than 1 or less than -1, the sequence diverges to infinity or negative infinity, respectively.
3. If the recurrence relation fluctuates between positive and negative without stabilizing, it may bounce around a certain range without settling.

Example of Calculation with Limit

• For $a = 0.5$ and $b = 8$, the limit formula is:
  $L = \frac{b}{1-a}$
• Calculation:
  • Applying to our example:
    $L = \frac{8}{1-0.5} = \frac{8}{0.5} = 16$
• This shows that the sequence will stabilize around 16 regardless of starting value, provided you follow the recurrence relation.

Complex Examples and Applications

• The farmer scenario illustrates how you can set up a recurrence relation based on loss and replenishment of livestock:
  • Formula example:
    $u<em>{n+1} = 0.87u</em>n + 300$
• Nature of calculation is essentially about persistence, ensuring you maintain and adjust the livestock number.

General Examples

1. For a sheep farmer losing 13% of his flock:

   • Initial value: $u_0 = 2000$
   • Recurrence: $u<em>{n+1} = 0.87u</em>n + 300$
   • After 10 years (compute sequentially to find $u_{10}$)

2. Island population scenario with 18% exit:

   • Initial Population: $u_0 = 8000$
   • Recurrence: $u<em>{n+1} = 0.82u</em>n + 250$

3. For pruned rose bushes:

   • Initial Height: $u_0 = 1.5$
   • Recurrence involving pruning and growth:
     $u<em>{n+1} = 0.65u</em>n + 0.25$

Conclusion

• Recurrence relations are powerful modeling tools useful in various scenarios from livestock management to population modeling. By identifying the recurrence base and analyzing the properties, students can predict future behaviors of sequenced events.
• Always ensure that when determining limits, the coefficients of the recurrence relationships maintain conditions specified (% values between -1 and 1) for stable results.