The Central Idea
Suppose a sequence begins
\[ 5,\ 8,\ 11,\ 14,\ 17,\ldots \]We can describe this sequence in at least two useful ways.
An explicit definition gives each term directly from its index:
\[ \boxed{a_n=3n+2,\qquad n\geq1}. \]A recursive definition gives a starting value and tells us how to obtain each new term from an earlier one:
\[ \boxed{ a_1=5,\qquad a_n=a_{n-1}+3\quad(n\geq2) }. \]Both definitions generate the same sequence.
Two Ways to Describe the Same Pattern
The explicit rule
\[ a_n=3n+2 \]emphasizes the relationship between the index \(n\) and the term \(a_n\).
The recursive rule
\[ a_n=a_{n-1}+3 \]emphasizes the relationship between neighboring terms.
These are different representations of the same underlying sequence.
What Is an Explicit Definition?
An explicit definition gives a formula that allows a term to be calculated directly from its index.
For example,
\[ a_n=4n-1 \]defines a sequence explicitly.
If we want the tenth term, we substitute
\[ n=10. \]Then
\[ a_{10}=4(10)-1 \] \[ =40-1 \] \[ =\boxed{39}. \]We did not need to calculate the first nine terms.
Explicit Means Direct Access
The major advantage of an explicit formula is that it provides direct access to a term.
Suppose
\[ a_n=2n^2+1. \]To calculate the hundredth term, simply evaluate
\[ a_{100}=2(100)^2+1. \]Therefore,
\[ a_{100}=20001. \]Earlier terms do not need to be known.
Example: Generate Terms from an Explicit Rule
Let
\[ a_n=5n-2,\qquad n\geq1. \]Then
\[ a_1=5(1)-2=3, \] \[ a_2=5(2)-2=8, \] \[ a_3=5(3)-2=13, \]and
\[ a_4=5(4)-2=18. \]Thus the sequence begins
\[ \boxed{3,\ 8,\ 13,\ 18,\ldots}. \]Explicit Rules Can Take Many Forms
Explicit sequence formulas are not limited to linear expressions.
Examples include
\[ a_n=n^2, \] \[ b_n=2^n, \] \[ c_n=\frac{1}{n}, \] \[ d_n=(-1)^n, \]and
\[ e_n=\frac{n+1}{2n-1}. \]In each case, knowing the index is enough to calculate the corresponding term.
What Is a Recursive Definition?
A recursive definition defines terms using one or more earlier terms.
For example,
\[ a_1=4 \]and
\[ a_n=a_{n-1}+5 \qquad(n\geq2) \]define a sequence recursively.
Begin with
\[ a_1=4. \]Then
\[ a_2=a_1+5=9, \] \[ a_3=a_2+5=14, \] \[ a_4=a_3+5=19. \]Therefore,
\[ \boxed{4,\ 9,\ 14,\ 19,\ldots}. \]A Recursive Definition Has Two Essential Parts
A recursive sequence generally requires:
- one or more initial conditions;
- a recurrence relation.
For example,
\[ a_1=7 \]is an initial condition, while
\[ a_n=a_{n-1}+4 \]is the recurrence relation.
Together they determine
\[ 7,\ 11,\ 15,\ 19,\ldots \]Initial Conditions
An initial condition supplies the starting information needed to begin a recursive process.
Suppose we are given only
\[ a_n=a_{n-1}+3. \]This tells us how consecutive terms are related, but it does not tell us where the sequence starts.
The sequences
\[ 1,\ 4,\ 7,\ 10,\ldots \]and
\[ 20,\ 23,\ 26,\ 29,\ldots \]both satisfy the recurrence
\[ a_n=a_{n-1}+3. \]An initial condition identifies which sequence is intended.
The Recurrence Relation
A recurrence relation describes how later terms depend on earlier terms.
For example,
\[ a_n=2a_{n-1} \]tells us to double the previous term.
If
\[ a_1=3, \]then
\[ a_2=2(3)=6, \] \[ a_3=2(6)=12, \] \[ a_4=2(12)=24. \]Thus,
\[ \boxed{3,\ 6,\ 12,\ 24,\ldots}. \]Why the Index Restriction Is Included
A recursive rule often includes a condition such as
\[ n\geq2. \]For example,
\[ a_1=5,\qquad a_n=a_{n-1}+4\quad(n\geq2). \]The recurrence begins at \(n=2\) because calculating \(a_2\) requires the already known value \(a_1\).
The index restriction tells us where the recursive rule becomes valid.
Recursive Definitions Build Forward
A recursive sequence is normally generated step by step.
Suppose
\[ a_1=2,\qquad a_n=3a_{n-1}+1. \]Then
\[ a_2=3(2)+1=7, \] \[ a_3=3(7)+1=22, \] \[ a_4=3(22)+1=67. \]Therefore,
\[ \boxed{2,\ 7,\ 22,\ 67,\ldots}. \]Each calculation becomes input for the next.
Recursion Is Iteration
A recursive definition creates an iterative process.
If
\[ a_n=f(a_{n-1}), \]then the same transformation \(f\) is repeatedly applied:
\[ a_1 \longrightarrow a_2 \longrightarrow a_3 \longrightarrow a_4 \longrightarrow\cdots \]This connection between recursion and iteration will later become important in algorithms, dynamical systems, numerical methods, and convergence.
One Previous Term
Some recurrence relations depend only on the immediately preceding term.
For example,
\[ a_n=a_{n-1}+6 \]uses one previous term.
Likewise,
\[ a_n=\frac12a_{n-1} \]uses one previous term.
Such recurrences require one suitable initial value to begin the process.
More Than One Previous Term
A recurrence may depend on several earlier terms.
The familiar Fibonacci recurrence is
\[ F_n=F_{n-1}+F_{n-2}. \]Because two earlier terms are needed, two initial values must be supplied.
For example,
\[ F_1=1,\qquad F_2=1. \]Then
\[ F_3=1+1=2, \] \[ F_4=2+1=3, \] \[ F_5=3+2=5. \]Thus,
\[ 1,\ 1,\ 2,\ 3,\ 5,\ldots \]Why Two Initial Values Are Needed
Consider
\[ a_n=a_{n-1}+a_{n-2}. \]To calculate \(a_3\), we need both
\[ a_2 \]and
\[ a_1. \]Therefore, one starting value is not enough.
In general, the required initial conditions must supply enough information to begin the recurrence.
Recursive Rules Can Be Nonlinear
Recursion is not limited to addition or multiplication by a constant.
For example,
\[ a_1=2,\qquad a_n=(a_{n-1})^2-1. \]Then
\[ a_2=2^2-1=3, \] \[ a_3=3^2-1=8, \] \[ a_4=8^2-1=63. \]Thus,
\[ \boxed{2,\ 3,\ 8,\ 63,\ldots}. \]Recursive processes can produce very rapid or complicated behavior.
Recursive Rules Can Depend on the Index Too
A recurrence relation may involve both earlier terms and the current index.
For example,
\[ a_1=1,\qquad a_n=a_{n-1}+n. \]Then
\[ a_2=1+2=3, \] \[ a_3=3+3=6, \] \[ a_4=6+4=10, \] \[ a_5=10+5=15. \]Therefore,
\[ \boxed{1,\ 3,\ 6,\ 10,\ 15,\ldots}. \]Explicit and Recursive Definitions Emphasize Different Structure
Consider
\[ 2,\ 5,\ 8,\ 11,\ldots \]The explicit form
\[ a_n=3n-1 \]emphasizes the relationship between \(n\) and \(a_n\).
The recursive form
\[ a_1=2,\qquad a_n=a_{n-1}+3 \]emphasizes the constant change from one term to the next.
The first viewpoint is global. The second is local and stepwise.
Explicit Form Gives a Global Description
An explicit rule describes the entire sequence through one relationship between index and value.
If
\[ a_n=7n+4, \]then the formula immediately connects every permitted \(n\) with its corresponding term.
We can jump directly from
\[ n=500 \]to
\[ a_{500}=3504. \]No intermediate terms are required.
Recursive Form Gives a Local Description
A recursive rule describes how one part of a sequence relates to nearby parts.
For example,
\[ a_n=a_{n-1}+7 \]tells us that every term is \(7\) greater than the previous term.
This local relationship can make a sequence's step-by-step structure immediately visible.
Example: From Explicit to Recursive
Consider the explicit sequence
\[ a_n=4n+3,\qquad n\geq1. \]The first term is
\[ a_1=4(1)+3=7. \]Compare consecutive terms:
\[ a_n-a_{n-1}. \]Since
\[ a_{n-1}=4(n-1)+3 \] \[ =4n-1, \]we have
\[ a_n-a_{n-1} = (4n+3)-(4n-1) \] \[ =4. \]Therefore, an equivalent recursive definition is
\[ \boxed{ a_1=7,\qquad a_n=a_{n-1}+4\quad(n\geq2) }. \]Checking the Conversion
Starting from
\[ a_1=7, \]the recurrence
\[ a_n=a_{n-1}+4 \]produces
\[ a_2=11, \] \[ a_3=15, \] \[ a_4=19. \]The explicit formula gives
\[ a_2=4(2)+3=11, \] \[ a_3=4(3)+3=15, \] \[ a_4=4(4)+3=19. \]The two representations agree.
Example: Multiplicative Recursion
Consider
\[ 3,\ 6,\ 12,\ 24,\ 48,\ldots \]Each term is twice the previous term.
A recursive definition is
\[ \boxed{ a_1=3,\qquad a_n=2a_{n-1}\quad(n\geq2) }. \]An explicit definition is
\[ \boxed{a_n=3\cdot2^{n-1}}. \]The recursive form highlights repeated multiplication, while the explicit form gives direct access to any term.
Why \(n-1\) Appears in the Explicit Formula
In
\[ 3,\ 6,\ 12,\ 24,\ldots, \]the first term is already \(3\).
To reach the second term, we multiply by \(2\) once.
To reach the third term, we multiply by \(2\) twice.
To reach the \(n\)th term, we multiply by \(2\)
\[ n-1 \]times.
Therefore,
\[ a_n=3\cdot2^{n-1}. \]Recursive Expansion
One way to understand a recurrence is to repeatedly substitute earlier terms into it.
Suppose
\[ a_n=2a_{n-1} \]and
\[ a_1=3. \]Then
\[ a_n=2a_{n-1}. \]Since
\[ a_{n-1}=2a_{n-2}, \]we obtain
\[ a_n=2^2a_{n-2}. \]Continuing this process gives
\[ a_n=2^{n-1}a_1. \]Because \(a_1=3\),
\[ \boxed{a_n=3\cdot2^{n-1}}. \]Recursion Can Reveal Accumulation
Suppose
\[ a_1=2,\qquad a_n=a_{n-1}+n. \]Expand recursively:
\[ a_n=a_{n-1}+n. \]But
\[ a_{n-1}=a_{n-2}+(n-1). \]Therefore,
\[ a_n = a_{n-2}+(n-1)+n. \]Continuing backward reveals that the term accumulates successive contributions.
This idea leads naturally toward finite sums and sigma notation.
Not Every Recursive Rule Is Easy to Make Explicit
Some recursive sequences can be converted into simple explicit formulas.
Others cannot be converted so easily.
For example,
\[ a_{n}=a_{n-1}^2+1 \]may be simple to compute recursively, but a convenient elementary formula giving \(a_n\) directly may not be available.
A recursive definition is therefore not merely an inferior version of an explicit formula. In many problems, recursion is the natural representation.
Not Every Explicit Formula Is Easy to Discover
A sequence may have a compact explicit formula even when the pattern is easier to notice recursively.
For example,
\[ 4,\ 7,\ 10,\ 13,\ 16,\ldots \]immediately suggests
\[ a_n=a_{n-1}+3. \]From this pattern we can then derive
\[ a_n=4+3(n-1) \]and simplify:
\[ \boxed{a_n=3n+1}. \]Recursive structure often helps us discover explicit structure.
Recursion in Algorithms
Recursive definitions closely resemble algorithms.
Suppose
\[ a_0=1 \]and
\[ a_n=2a_{n-1}+1. \]An algorithm for generating terms could be described as:
- start with \(1\);
- multiply the current value by \(2\);
- add \(1\);
- record the result;
- repeat.
This produces
\[ 1,\ 3,\ 7,\ 15,\ 31,\ldots \]Recurrences therefore connect algebraic notation with computational procedures.
Recursive Definitions and State
A recursive process must remember enough information from earlier steps to calculate the next step.
For
\[ a_n=2a_{n-1}+1, \]only the previous value must be retained.
For
\[ a_n=a_{n-1}+a_{n-2}, \]the previous two values must be retained.
In computational language, these remembered values form part of the process's state.
Recursive Definitions Must Be Well Founded
A useful recursive definition must eventually lead back to known starting information.
Consider
\[ a_n=a_{n-1}+2 \]with no initial value.
To find \(a_5\), we need \(a_4\).
To find \(a_4\), we need \(a_3\), and so on.
Without a known starting value, the calculation never becomes determined.
Common Error: Omitting the Initial Condition
A student writes
\[ a_n=a_{n-1}+5 \]and claims that this uniquely defines a sequence.
It does not.
We still need a starting value such as
\[ a_1=2. \]Then the complete recursive definition becomes
\[ \boxed{ a_1=2,\qquad a_n=a_{n-1}+5\quad(n\geq2) }. \]Common Error: Applying the Recurrence at the Wrong Index
Suppose
\[ a_1=6,\qquad a_n=a_{n-1}+4\quad(n\geq2). \]The recurrence is used beginning with \(n=2\).
Thus,
\[ a_2=a_1+4. \]Trying to apply the rule at \(n=1\) would require
\[ a_0, \]which has not been defined.
Common Error: Confusing \(a_n\) with \(a_{n-1}\)
Suppose
\[ a_1=4,\qquad a_n=2a_{n-1}. \]To calculate \(a_2\), use
\[ a_2=2a_1. \]Therefore,
\[ a_2=8. \]The recurrence does not say
\[ a_2=2a_2. \]The subscript \(n-1\) deliberately refers to the preceding index.
Common Error: Forgetting Which Terms Are Already Known
Consider
\[ a_1=2,\qquad a_2=5, \]with
\[ a_n=a_{n-1}+a_{n-2}. \]To calculate \(a_3\), use the two known values:
\[ a_3=a_2+a_1 \] \[ =5+2 \] \[ =7. \]Then \(a_3\) becomes available when calculating \(a_4\):
\[ a_4=a_3+a_2 \] \[ =7+5 \] \[ =12. \]Common Error: Assuming Explicit Means Simpler
An explicit formula is convenient when direct access to a distant term is needed.
But that does not mean an explicit representation is always simpler or more informative.
Some processes are naturally defined by repeated steps, and the recursive rule may reveal the mechanism more clearly than any direct formula.
The useful representation depends on the question being asked.
Common Error: Assuming Recursive Means Random
A recursive sequence is not unpredictable merely because later values depend on earlier ones.
Once the initial conditions and recurrence relation are fixed, a deterministic recursive sequence has determined terms.
For example,
\[ a_1=1,\qquad a_n=2a_{n-1}+3 \]uniquely determines
\[ 1,\ 5,\ 13,\ 29,\ 61,\ldots \]Comparing the Two Representations
| Explicit Definition | Recursive Definition |
|---|---|
| Gives \(a_n\) directly from \(n\) | Gives \(a_n\) from earlier terms |
| Allows direct calculation of distant terms | Usually builds terms in order |
| Emphasizes index-to-value structure | Emphasizes term-to-term structure |
| May not show the step pattern immediately | Often makes the step pattern obvious |
| Usually needs a domain or index range | Usually needs initial conditions and an index range |
A Reliable Procedure for Using an Explicit Definition
- Identify the formula for \(a_n\).
- Identify the allowed indices.
- Determine the index of the desired term.
- Substitute that index for \(n\).
- Simplify the resulting expression.
- Check that the index belongs to the sequence's domain.
A Reliable Procedure for Using a Recursive Definition
- Identify the initial condition or conditions.
- Identify the recurrence relation.
- Check where the recurrence begins.
- Use the known terms to calculate the next term.
- Record the new value.
- Use that new value when calculating later terms.
- Repeat until the desired term is reached.
Example: Full Explicit Workflow
Let
\[ a_n=3n^2-2n+4,\qquad n\geq1. \]Find \(a_6\).
Substitute
\[ n=6. \]Then
\[ a_6=3(6)^2-2(6)+4. \]Calculate:
\[ a_6=3(36)-12+4 \] \[ =108-12+4 \] \[ =\boxed{100}. \]Example: Full Recursive Workflow
Let
\[ a_1=3,\qquad a_n=2a_{n-1}-1\quad(n\geq2). \]Find \(a_5\).
Begin with
\[ a_1=3. \]Then
\[ a_2=2(3)-1=5, \] \[ a_3=2(5)-1=9, \] \[ a_4=2(9)-1=17, \]and
\[ a_5=2(17)-1=33. \]Therefore,
\[ \boxed{a_5=33}. \]Example: A Two-Term Recurrence
Let
\[ a_1=2,\qquad a_2=3, \]and
\[ a_n=a_{n-1}+2a_{n-2} \qquad(n\geq3). \]Then
\[ a_3=a_2+2a_1 \] \[ =3+2(2) \] \[ =7. \]Next,
\[ a_4=a_3+2a_2 \] \[ =7+2(3) \] \[ =13. \]Then
\[ a_5=a_4+2a_3 \] \[ =13+2(7) \] \[ =27. \]Thus,
\[ \boxed{2,\ 3,\ 7,\ 13,\ 27,\ldots}. \]Practice 1: Explicit Evaluation
Let
\[ a_n=7n-4,\qquad n\geq1. \]Find
\[ a_{12}. \]Practice 2: Generate from an Explicit Rule
Let
\[ b_n=n^2+2,\qquad n\geq1. \]Write the first five terms.
Practice 3: Recursive Generation
Let
\[ a_1=4,\qquad a_n=a_{n-1}+6\quad(n\geq2). \]Write the first five terms.
Practice 4: Multiplicative Recursion
Let
\[ a_1=5,\qquad a_n=3a_{n-1}\quad(n\geq2). \]Find
\[ a_4. \]Practice 5: Index-Dependent Recurrence
Let
\[ a_1=2,\qquad a_n=a_{n-1}+n\quad(n\geq2). \]Find the first five terms.
Practice 6: Two Previous Terms
Let
\[ a_1=1,\qquad a_2=4, \]and
\[ a_n=a_{n-1}+a_{n-2} \qquad(n\geq3). \]Find
\[ a_6. \]Practice 7: Write a Recursive Definition
Write a recursive definition for
\[ 8,\ 13,\ 18,\ 23,\ 28,\ldots \]assuming the first term is \(a_1\).
Practice 8: Write an Explicit Definition
The sequence
\[ 4,\ 7,\ 10,\ 13,\ldots \]begins at \(n=1\).
Write an explicit formula for \(a_n\).
Practice 9: Identify the Missing Information
A sequence is described by
\[ a_n=2a_{n-1}+1. \]Explain why this does not yet determine a unique sequence.
Practice 10: Compare Representations
Consider
\[ a_n=5n-2,\qquad n\geq1. \]Write an equivalent recursive definition.
Practice Answers
Practice 1
\[ a_{12}=7(12)-4 \] \[ =84-4 \] \[ =\boxed{80}. \]Practice 2
\[ b_1=3, \] \[ b_2=6, \] \[ b_3=11, \] \[ b_4=18, \]and
\[ b_5=27. \]Therefore,
\[ \boxed{3,\ 6,\ 11,\ 18,\ 27}. \]Practice 3
Begin with \(a_1=4\) and repeatedly add \(6\):
\[ \boxed{4,\ 10,\ 16,\ 22,\ 28}. \]Practice 4
\[ a_2=3(5)=15, \] \[ a_3=3(15)=45, \] \[ a_4=3(45)=135. \]Therefore,
\[ \boxed{a_4=135}. \]Practice 5
\[ a_1=2, \] \[ a_2=2+2=4, \] \[ a_3=4+3=7, \] \[ a_4=7+4=11, \] \[ a_5=11+5=16. \]Thus,
\[ \boxed{2,\ 4,\ 7,\ 11,\ 16}. \]Practice 6
\[ a_3=4+1=5, \] \[ a_4=5+4=9, \] \[ a_5=9+5=14, \] \[ a_6=14+9=23. \]Therefore,
\[ \boxed{a_6=23}. \]Practice 7
Each term is \(5\) greater than the previous term.
\[ \boxed{ a_1=8,\qquad a_n=a_{n-1}+5\quad(n\geq2) }. \]Practice 8
The first term is \(4\), and the common increase is \(3\).
\[ a_n=4+3(n-1). \]Simplify:
\[ \boxed{a_n=3n+1}. \]Practice 9
The recurrence tells us how to obtain a term from the preceding term, but no starting value has been supplied.
An initial condition such as
\[ a_1=3 \]is required to determine a particular sequence.
Practice 10
First find the initial term:
\[ a_1=5(1)-2=3. \]Consecutive terms differ by \(5\).
Therefore,
\[ \boxed{ a_1=3,\qquad a_n=a_{n-1}+5\quad(n\geq2) }. \]What to Remember
An explicit definition calculates a sequence term directly from its index:
\[ \boxed{a_n=f(n)}. \]A recursive definition calculates later terms from earlier terms:
\[ \boxed{a_n=f(a_{n-1},a_{n-2},\ldots)}. \]- Explicit rules give direct access to individual terms.
- Recursive rules reveal step-by-step relationships.
- Recursive definitions usually require initial conditions.
- A recurrence relation tells how later terms are generated.
- The index range tells where the rule applies.
- Some sequences have useful forms of both definitions.
- Some sequences are more naturally described recursively.
- Recursion is closely connected with iteration and algorithms.
The key distinction is:
\[ \boxed{ \text{explicit: index }\longrightarrow\text{ term} } \]versus
\[ \boxed{ \text{recursive: earlier terms }\longrightarrow\text{ later terms}. } \]Where We Go Next
Explicit and recursive notation gives us two complementary ways to describe sequence structure. We can now apply those ideas to one of the simplest and most important sequence families: sequences whose consecutive terms differ by a constant amount.
The next lesson, Arithmetic Sequences, develops arithmetic sequences from their common difference, derives both recursive and explicit formulas, and connects those formulas to linear relationships and discrete graphs.