A recurrence relation defines each term of a sequence using one or more earlier terms. It is a powerful way to describe patterns that grow step by step, such as savings accounts, population models, computer algorithms, and counting problems. Instead of giving a direct formula for a_n, a recurrence gives a rule for moving from known terms to future terms.
Initial conditions are essential because they tell the recurrence where to start.
Many important recurrences can be solved by looking for structure in the rule. First-order linear recurrences often unfold into arithmetic or geometric patterns, while second-order linear recurrences can often be solved with a characteristic equation. The Fibonacci sequence is a famous example where each term depends on the two previous terms.
Solving a recurrence helps predict faraway terms without computing every step one at a time.
Understanding Math: Recurrence Relations
A useful first step is to make a small table of terms. Write the starting value or values, then apply the rule carefully one line at a time. This exposes common errors with signs, index numbers, and the first term used in the calculation.
For example, a balance that gains a fixed amount each week behaves differently from a balance that is multiplied by the same factor each week. The first has steady additive change. The second has percentage growth or decay.
Looking at successive differences can reveal the first pattern. Looking at successive ratios can reveal the second, provided the terms are not zero.
Some recurrence rules include an extra input at every step. A savings balance may be multiplied by one plus the interest rate, then receive a regular deposit. This is not purely geometric because the deposit changes the pattern each month.
One way to handle such a rule is to find its equilibrium value. An equilibrium is a value that stays unchanged when put into the rule.
After subtracting that value from every term, the remaining sequence often becomes geometric. This idea matters in models of heating, drug concentration, loan repayments, and populations with a steady outside supply or loss.
When each term depends on two earlier terms, the behavior can be richer. A second order rule needs two starting values because there are two independent pieces of information to track. The characteristic equation method works by testing an exponential pattern.
Its solutions, called roots, determine the shape of the final formula. Two different roots give a combination of two exponential patterns. A repeated root needs an extra factor involving the term number.
Complex roots can create repeating swings, which helps explain why some models oscillate instead of simply growing or shrinking. Students should check a proposed formula against both starting values and the recurrence rule, not only against a few later terms.
Recurrences appear whenever a process has memory. In computer science, an algorithm may solve a large task by breaking it into smaller tasks. Its running time can be described by a recurrence.
In probability, the chance of being in a state after several moves can depend on earlier states. In counting, a sequence can track the number of ways to tile a strip, climb steps, or form strings under restrictions. A closed formula is useful for estimating a distant term, but repeated calculation is often better for a short list or for a rule that changes over time.
Keep track of the domain too. A rule intended for whole numbered days may make no sense for negative term numbers. Real models have limits, since unlimited growth eventually meets constraints such as space, money, or available resources.
Key Facts
- A recurrence relation defines a_n using earlier terms such as a_{n-1} or a_{n-2}.
- Initial conditions such as a_0 = 3 or a_1 = 5 are needed to determine a unique sequence.
- Arithmetic recurrence: a_n = a_{n-1} + d gives a_n = a_0 + nd.
- Geometric recurrence: a_n = r a_{n-1} gives a_n = a_0 r^n.
- For a_n = c_1 a_{n-1} + c_2 a_{n-2}, try a_n = r^n to get r^2 = c_1 r + c_2.
- Fibonacci recurrence: F_0 = 0, F_1 = 1, and F_n = F_{n-1} + F_{n-2}.
Vocabulary
- Recurrence relation
- An equation that defines a sequence term using one or more previous terms.
- Initial condition
- A starting value that allows a recurrence relation to produce a specific sequence.
- Closed form
- A formula for a_n that depends directly on n rather than on earlier terms.
- Characteristic equation
- An algebraic equation found by substituting a_n = r^n into a linear recurrence.
- Fibonacci sequence
- A sequence in which each term after the first two is the sum of the two previous terms.
Common Mistakes to Avoid
- Forgetting the initial conditions makes the answer incomplete because the same recurrence can describe many different sequences.
- Starting the index at the wrong value gives shifted terms because a_0, a_1, and a_2 are not interchangeable.
- Treating every recurrence like a geometric sequence is wrong because only recurrences of the form a_n = r a_{n-1} have a constant ratio.
- Using the characteristic equation without checking its roots can lead to an incorrect closed form because repeated roots require a different pattern.
Practice Questions
- 1 Given a_0 = 4 and a_n = a_{n-1} + 7, find a_1, a_2, a_3, and a formula for a_n.
- 2 Given b_0 = 3 and b_n = 2b_{n-1}, find b_1 through b_5 and write a closed form for b_n.
- 3 Explain why the recurrence F_n = F_{n-1} + F_{n-2} needs two initial conditions, while a_n = 5a_{n-1} needs only one.